Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Common Generalization of the Theorems of ErdH{o}s-Ko-Rado and Hilton-Milner
614
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $m$, $n$, and $k$ be integers satisfying $0 < k leq n < 2k leq m$. A family of sets $mathcal{F}$ is called an $(m,n,k)$-intersecting family if $binom{[n]}{k} subseteq mathcal{F} subseteq binom{[m]}{k}$ and any pair of members of $mathcal{F}$ have nonempty intersection. Maximum $(m,k,k)$- and $(m,k+1,k)$-intersecting families are determined by the theorems of ErdH{o}s-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, and $m$ sufficiently large.
rate research
Read More
A perfect matching of a complete graph $K_{2n}$ is a 1-regular subgraph that contains all the vertices. Two perfect matchings intersect if they share an edge. It is known that if $mathcal{F}$ is family of intersecting perfect matchings of $K_{2n}$, then $|mathcal{F}| leq (2(n-1) - 1)!!$ and if equality holds, then $mathcal{F} = mathcal{F}_{ij}$ where $ mathcal{F}_{ij}$ is the family of all perfect matchings of $K_{2n}$ that contain some fixed edge $ij$. We give a short algebraic proof of this result, resolving a question of Godsil and Meagher. Along the way, we show that if a family $mathcal{F}$ is non-Hamiltonian, that is, $m cup m ot cong C_{2n}$ for any $m,m in mathcal{F}$, then $|mathcal{F}| leq (2(n-1) - 1)!!$ and this bound is met with equality if and only if $mathcal{F} = mathcal{F}_{ij}$. Our results make ample use of a somewhat understudied symmetric commutative association scheme arising from the Gelfand pair $(S_{2n},S_2 wr S_n)$. We give an exposition of a few new interesting objects that live in this scheme as they pertain to our results.
Ever since the famous ErdH{o}s-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families of various combinatorial objects have been extensively investigated. Among them, studies about families of subsets, vector spaces and permutations are of particular concerns. Recently, the authors proposed a new quantitative intersection problem for families of subsets: For $mathcal{F}subseteq {[n]choose k}$, define its emph{total intersection number} as $mathcal{I}(mathcal{F})=sum_{F_1,F_2in mathcal{F}}|F_1cap F_2|$. Then, what is the structure of $mathcal{F}$ when it has the maximal total intersection number among all families in ${[n]choose k}$ with the same family size? In cite{KG2020}, the authors studied this problem and characterized extremal structures of families maximizing the total intersection number of given sizes. In this paper, we consider the analogues of this problem for families of vector spaces and permutations. For certain ranges of family size, we provide structural characterizations for both families of subspaces and families of permutations having maximal total intersection numbers. To some extent, these results determine the unique structure of the optimal family for some certain values of $|mathcal{F}|$ and characterize the relation between having maximal total intersection number and being intersecting. Besides, we also show several upper bounds on the total intersection numbers for both families of subspaces and families of permutations of given sizes.
The ErdH{o}s-Faber-Lov{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stabili
Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the ErdH{o}s-Posa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the ErdH{o}s-Posa property, and indeed even fails when $H$ is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.
An $r$-uniform hypergraph ($r$-graph for short) is called linear if every pair of vertices belong to at most one edge. A linear $r$-graph is complete if every pair of vertices are in exactly one edge. The famous Brown-ErdH{o}s-Sos conjecture states that for every fixed $k$ and $r$, every linear $r$-graph with $Omega(n^2)$ edges contains $k$ edges spanned by at most $(r-2)k+3$ vertices. As an intermediate step towards this conjecture, Conlon and Nenadov recently suggested to prove its natural Ramsey relaxation. Namely, that for every fixed $k$, $r$ and $c$, in every $c$-colouring of a complete linear $r$-graph, one can find $k$ monochromatic edges spanned by at most $(r-2)k+3$ vertices. We prove that this Ramsey version of the conjecture holds under the additional assumption that $r geq r_0(c)$, and we show that for $c=2$ it holds for all $rgeq 4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
