Size and structure of large (s,t)-union intersecting families

DOI10.37236/10490zbMATH Open1487.05263arXiv1903.02614OpenAlexW2922213563MaRDI QIDQ2138583FDOQ2138583

Authors: Ali Taherkhani 

Publication date: 12 May 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A family $F$ of sets is said to be intersecting if any two sets in $F$ have nonempty intersection. The celebrated Erd{H o}s-Ko-Rado theorem determines the size and structure of the largest intersecting family of $k$-sets on an $n$-set $X$. An $(s,t)$-union intersecting family is a family of $k$-sets on an $n$-set $X$ such that for any $A_1,ldots,A_{s+t}$ in this family, $left(cu{p}_{i=1}^s{A}_{i}ight)capleft(cu{p}_{i=1}^t{A}_{i+s}ight)eqvarnothing.$ Let $ell(F)$ be the minimum number of sets in $F$ such that by removing them the resulting subfamily is intersecting. In this paper, for sufficiently large $n$, we characterize the size and structure of $(s,t)$-union intersecting families with maximum possible size and $$. This allows us to find out the size and structure of some large and maximal $(s,t)$-union intersecting families. Our results are nontrivial extensions of some recent generalizations of the Erd{H o}s-Ko-Rado theorem such as the Han and Kohayakawa theorem 2017 which finds the structure of the third largest intersecting family, the Kostochka and Mubayi theorem 2017, and the more recent Kupavskii's theorem 2018 whose both results determine the size and structure of the $i$th largest intersecting family of $k$-sets for $ileqk+1$. In particular, we prove that a Hilton-Milner-type stability theorem holds for $(1,t)$-union intersecting families, that indeed, confirms a conjecture of Alishahi and Taherkhani 2018. We extend our results to $K_{s_1,ldots,s_{r+1}}$-free subgraphs of Kneser graphs. In fact, when $n$ is sufficiently large, we characterize the size and structure of large and maximal $K_{s_1,ldots,s_{r+1}}$-free subgraphs of Kneser graphs. In particular, when $s_1=cdots=s_{r+1}=1$ our result provides some stability results related to the famous Erd{H o}s matching conjecture.

Full work available at URL: https://arxiv.org/abs/1903.02614

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the union of intersecting families
• Union-intersecting set systems
• The structure of large intersecting families
• The maximum size of intersecting and union families of sets
• Beyond the Erdős matching conjecture

zbMATH Keywords

Hilton-Milner theoremKupavskii's theoremErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• On maximal paths and circuits of graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• On the structure of linear graphs
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• An Erdös-Ko-Rado theorem for direct products
• Transference for the Erdős-Ko-Rado theorem
• On a problem of K. Zarankiewicz
• The exact bound in the Erdős-Ko-Rado theorem
• An Erdős--Ko--Rado theorem for partial permutations
• Erdős-Ko-Rado-type theorems for colored sets
• On the stability of the Erdős-Ko-Rado theorem
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• A new short proof of the EKR theorem
• On Erdős' extremal problem on matchings in hypergraphs
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Erdös–Ko–Rado Theorem—22 Years Later
• On generalized graphs
• An extremal problem for two families of sets
• Almost Intersecting Families of Sets
• Intersection patterns of convex sets
• The size of a hypergraph and its matching number
• Improved bounds for Erdős' matching conjecture
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• On matchings in hypergraphs
• Union-intersecting set systems
• On intersecting families of finite sets
• The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family
• The structure of large intersecting families
• On the maximum number of edges in a hypergraph with given matching number
• Extremal \(G\)-free induced subgraphs of Kneser graphs
• Diversity of uniform intersecting families
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• Stability results for vertex Turán problems in Kneser graphs

Cited In (8)

• Degree versions of theorems on intersecting families via stability
• The structure of maximal non-trivial \(d\)-wise intersecting uniform families with large sizes
• The maximum size of 4-wise 2-intersecting and 4-wise 2-union families
• On the union of intersecting families
• The structure of large intersecting families
• Union-intersecting set systems
• The maximum size of intersecting and union families of sets
• On large intersecting subfamilies of uniform setfamilies

This page was built for publication: Size and structure of large \((s,t)\)-union intersecting families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138583)