Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn transversal and 2-packing numbers in uniform linear systems
58
0
0.0
(
0
)
Added by
Christian Rubio-Montiel PhD
Publication date
2019
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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 enough $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 first 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 asymptotically-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 for 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 $.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
