Cross-intersecting subfamilies of levels of hereditary families

DOI10.1016/J.DISC.2020.111900MaRDI QIDQ2185903zbMATH OpenOpenAlexFDO

Authors Peter Borg

Publication date 8 June 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cross-intersecting familieshereditary familyintersecting family

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Extremal set theory (05D05)

Abstract: A set $A$ $t$-intersects a set $B$ if $A$ and $B$ have at least $t$ common elements. Families $mathcal{A}_1,mathcal{A}_2,dots,mathcal{A}_k$ of sets are cross-$t$-intersecting if, for every $i$ and $j$ in $1,2,dots,k$ with $ieqj$, each set in $mathcal{A}_i$ $t$-intersects each set in $mathcal{A}_j$. An active problem in extremal set theory is to determine, for a given finite family $mathcalF$, the structure of $k$ cross-$t$-intersecting subfamilies whose sum or product of sizes is maximum. For a family $mathcalH$, the $r$-th level $mathcal{H}^{(r)}$ of $mathcalH$ is the family of all sets in $mathcalH$ of size $r$, and, for $sleqr$, $mathcal{H}^{(s)}$ is called a $(leqr)$-level of $mathcalH$. We solve the problem for any union $mathcalF$ of $(leqr)$-levels of any union $mathcalH$ of power sets of sets of size at least a certain integer $n_0$, where $n_0$ is independent of $mathcalH$ and $k$ but depends on $r$ and $t$ (dependence on $r$ is inevitable, but dependence on $t$ can be avoided). Our primary result asserts that there are only two possible optimal configurations for the sum. A special case was conjectured by Kamat in 2011. We also prove generalizations, whereby $mathcal{A}_1,mathcal{A}_2,dots,mathcal{A}_k$ are not necessarily contained in the same union of levels. Various ErdH{o}s-Ko-Rado-type results follow. The sum problem for a level of a power set was solved for $t=1$ by Hilton in 1977, and for any $t$ by Wang and Zhang in 2011.

Recommendations

• Cross-intersecting non-empty uniform subfamilies of hereditary families
• Extremal t -intersecting sub-families of hereditary families
• The maximum product of weights of cross-intersecting families
• The maximum product of sizes of cross-intersecting families
• The maximum sum and the maximum product of sizes of cross-intersecting families

Cites work

• A new result on Chvátal's conjecture
• A new short proof of the EKR theorem
• A short proof of a cross-intersection theorem of Hilton
• A simple proof of the Erdős-Chao Ko-Rado theorem
• An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
• Beyond the Erdős-Ko-Rado theorem
• Compression and Erdős-Ko-Rado graphs
• Cross-intersecting families and primitivity of symmetric systems
• Cross-Intersecting Families of Partial Permutations
• Cross-intersecting families of permutations
• Cross-intersecting sub-families of hereditary families
• Erdös-Ko-Rado theorems for a family of trees
• Erdös–Ko–Rado Theorem—22 Years Later
• Erdős-Ko-Rado from Kruskal-Katona
• Erdős-Ko-Rado theorems for chordal graphs and trees
• Erdős-Ko-Rado theorems for simplicial complexes
• Extremal t -intersecting sub-families of hereditary families
• Graphs with the Erdős-Ko-Rado property
• Homomorphisms of 3-chromatic graphs
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3621717 (Why is no real title available?)
• scientific article; zbMATH DE number 863493 (Why is no real title available?)
• Intersecting families of permutations
• INTERSECTING FAMILIES OF SEPARATED SETS
• Intersecting families of sets and permutations: a survey
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems for systems of finite sets
• Invitation to intersection problems for finite sets
• Multiple cross-intersecting families of signed sets
• New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• On Chvàtal's conjecture and a conjecture on families of signed sets
• On cross-intersecting families of independent sets in graphs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• The Erdős-Ko-Rado properties of various graphs containing singletons
• The exact bound in the Erdős-Ko-Rado theorem
• The maximum product of sizes of cross-intersecting families
• The maximum sum and the maximum product of sizes of cross-intersecting families

Cited in

(4)

• Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
• Extremal t -intersecting sub-families of hereditary families
• Cross-intersecting sub-families of hereditary families
• On cross-intersecting uniform sub-families of hereditary families

This page was built for publication: Cross-intersecting subfamilies of levels of hereditary families

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