Structural results for conditionally intersecting families and some applications

DOI10.37236/8894MaRDI QIDQ2185223zbMATH OpenOpenAlexFDO

Authors Xizhi Liu

Publication date 4 June 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

Erdős-Ko-Rado theoremextremal set theoryintersecting sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: Let $kgedge3$ be fixed. Let $mathcalF$ be a $k$-uniform family on $[n]$. Then $mathcalF$ is $(d,s)$-conditionally intersecting if it does not contain $d$ sets with union of size at most $s$ and empty intersection. Answering a question of Frankl, we present some structural results for families that are $(d,s)$-conditionally intersecting with $sge2k+d-3$, and families that are $(k,2k)$-conditionally intersecting. As applications of our structural results, we present some new proofs to the upper bounds for the size of the following $k$-uniform families on $[n]$. (a) $(d,2k+d-3)$-conditionally intersecting families with $nge3k^5$. (b) $(k,2k)$-conditionally intersecting families with $nge{k}^2/(k-1)$. (c) Nonintersecting $(3,2k)$-conditionally intersecting families with $$. Our results for $(c)$ confirms a conjecture of Mammoliti and Britz for the case $d=3$.

Review text

Summary: Let \(k\geqslant d\geqslant 3\) be fixed. Let \(\mathcal{F}\) be a \(k\)-uniform family on \([n]\). Then \(\mathcal{F}\) is \((d,s)\)-conditionally intersecting if it does not contain \(d\) sets with union of size at most \(s\) and empty intersection. Answering a question of \textit{P. Frankl} [Discrete Math. 340, No. 5, 1039--1041 (2017; Zbl 1357.05108)], we present some structural results for families that are \((d,s)\)-conditionally intersecting with \(s\geqslant 2k+d-3\), and families that are \((k,2k)\)-conditionally intersecting. As applications of our structural results we present some new proofs to the upper bounds for the size of the following \(k\)-uniform families on \([n]\): (a) \((d,2k+d-3)\)-conditionally intersecting families with \(n\geqslant 3k^5\); (b) \((k,2k)\)-conditionally intersecting families with \(n\geqslant k^2/(k-1)\); (c) Nonintersecting \((3,2k)\)-conditionally intersecting families with \(n\geqslant 3k\binom{2k}{k} \). Our results for \((c)\) confirms a conjecture of \textit{A. Mammoliti} and \textit{T. Britz} [SIAM J. Discrete Math. 32, No. 3, 2361--2380 (2018; Zbl 1396.05112)] for the case \(d=3\).

Recommendations

• On Mubayi's conjecture and conditionally intersecting sets
• Intersecting k-uniform families containing all the k-subsets of a given set
• The structure of maximal non-trivial \(d\)-wise intersecting uniform families with large sizes
• Some results on intersecting families of subsets
• Non-trivial \(d\)-wise intersecting families

Cites work

• d-cluster-free sets with a given matching number
• A new generalization of the Erdős-Ko-Rado theorem
• A structural result for 3-graphs
• An intersection theorem for four sets
• Erdős--Ko--Rado for three sets
• Families of sets with intersecting clusters
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On generalized graphs
• On Mubayi's conjecture and conditionally intersecting sets
• On Sperner families satisfying an additional condition
• Unavoidable subhypergraphs: \(\mathbf a\)-clusters

Cited in

(3)

• Structure and supersaturation for intersecting families
• The structure of large intersecting families
• On Mubayi's conjecture and conditionally intersecting sets

This page was built for publication: Structural results for conditionally intersecting families and some applications

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