اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn transversal and 2-packing numbers in uniform linear systems
58
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A linear system is a pair $(P,mathcal{L})$ where $mathcal{L}$ is a family of subsets on a ground finite set $P$, such that $|lcap l^prime|leq 1$, for every $l,l^prime in mathcal{L}$. The elements of $P$ and $mathcal{L}$ are called points and lines, respectively, and the linear system is called intersecting if any pair of lines intersect in exactly one point. A subset $T$ of points of $P$ is a transversal of $(P,mathcal{L})$ if $T$ intersects any line, and the transversal number, $tau(P,mathcal{L})$, is the minimum order of a transversal. On the other hand, a 2-packing set of a linear system $(P,mathcal{L})$ is a set $R$ of lines, such that any three of them have a common point, then the 2-packing number of $(P,mathcal{L})$, $ u_2(P,mathcal{L})$, is the size of a maximum 2-packing set. It is known that the transversal number $tau(P,mathcal{L})$ is bounded above by a quadratic function of $ u_2(P,mathcal{L})$. An open problem is to haracterize the families of linear systems which satisfies $tau(P,mathcal{L})leq lambda u_2(P,mathcal{L})$, for some $lambdageq1$. In this paper, we give an infinite family of linear systems $(P,mathcal{L})$ which satisfies $tau(P,mathcal{L})= u_2(P,mathcal{L})$ with smallest possible cardinality of $mathcal{L}$, as well as some properties of $r$-uniform intersecting linear systems $(P,mathcal{L})$, such that $tau(P,mathcal{L})= u_2(P,mathcal{L})=r$. Moreover, we state a characterization of $4$-uniform intersecting linear systems $(P,mathcal{L})$ with $tau(P,mathcal{L})= u_2(P,mathcal{L})=4$.
قيم البحث
اقرأ أيضاً
In this paper we study Turan and Ramsey numbers in linear triple systems, defined as $3$-uniform hypergraphs in which any two triples intersect in at most one vertex. A famous result of Ruzsa and Szemeredi is that for any fixed $c>0$ and large enou
gh $n$ the following Turan-type theorem holds. If a linear triple system on $n$ vertices has at least $cn^2$ edges then it contains a {em triangle}: three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called {em $s$-configurations}. The main tool is a generalization of the induced matching lemma from $aba$-patterns to more general ones. We slightly generalize $s$-configurations to {em extended $s$-configurations}. For these we cannot prove the corresponding Turan-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any $t$-coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail $C_{15}$ (configuration with blocks 123, 345, 561 and 147), are $t$-Ramsey for any $tgeq 1$. The most interesting one among them is the {em wicket}, $D_4$, formed by three rows and two columns of a $3times 3$ point matrix. In fact, the wicket is $1$-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket.
Let $G$ be a graph of order $n(G)$ and vertex set $V(G)$. Given a set $Ssubseteq V(G)$, we define the external neighbourhood of $S$ as the set $N_e(S)$ of all vertices in $V(G)setminus S$ having at least one neighbour in $S$. The differential of $S$
is defined to be $partial(S)=|N_e(S)|-|S|$. In this paper, we introduce the study of the $2$-packing differential of a graph, which we define as $partial_{2p}(G)=max{partial(S): Ssubseteq V(G) text{ is a }2text{-packing}}.$ We show that the $2$-packing differential is closely related to several graph parameters, including the packing number, the independent domination number, the total domination number, the perfect differential, and the unique response Roman domination number. In particular, we show that the theory of $2$-packing differentials is an appropriate framework to investigate the unique response Roman domination number of a graph without the use of functions. Among other results, we obtain a Gallai-type theorem, which states that $partial_{2p}(G)+mu_{_R}(G)=n(G)$, where $mu_{_R}(G)$ denotes the unique response Roman domination number of $G$. As a consequence of the study, we derive several combinatorial results on $mu_{_R}(G)$, and we show that the problem of finding this parameter is NP-hard. In addition, the particular case of lexicographic product graphs is discussed.
We study the problems of bounding the number weak and strong independent sets in $r$-uniform, $d$-regular, $n$-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the firs
t order term for all (fixed) $rge 3$, with $d$ and $n$ going to infinity. In the case of strong independent sets, for $r=3$, we provide an upper bound that is tight up to the second-order term, improving on a result of Ordentlich-Roth (2004). The tightness in the strong independent set case is established by an explicit construction of a $3$-uniform, $d$-regular, cross-edge free, linear hypergraph on $n$ vertices which could be of interest in other contexts. We leave open the general case(s) with some conjectures. Our proofs use the occupancy method introduced by Davies, Jenssen, Perkins, and Roberts (2017).
Given a collection of graphs $mathbf{G}=(G_1, ldots, G_m)$ with the same vertex set, an $m$-edge graph $Hsubset cup_{iin [m]}G_i$ is a transversal if there is a bijection $phi:E(H)to [m]$ such that $ein E(G_{phi(e)})$ for each $ein E(H)$. We give asy
mptotically-tight minimum degree conditions for a graph collection on an $n$-vertex set to have a transversal which is a copy of a graph $H$, when $H$ is an $n$-vertex graph which is an $F$-factor or a tree with maximum degree $o(n/log n)$.
For positive integers $ngeq kgeq t$, a collection $ mathcal{B} $ of $k$-subsets of an $n$-set $ X $ is called a $t$-packing if every $t$-subset of $ X $ appears in at most one set in $mathcal{B}$. In this paper, we give some upper and lower bounds fo
r the maximum size of $3$-packings when $n$ is sufficiently larger than $k$. In one case, the upper and lower bounds are equal, in some cases, they differ by at most an additive constant depending only on $k$ and in one case they differ by a linear bound in $ n $.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
