Cross-intersecting sub-families of hereditary families

DOI10.1016/J.JCTA.2011.12.002MaRDI QIDQ765869zbMATH OpenOpenAlexFDO

Authors Peter Borg

Publication date 22 March 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

extremal set theoryintersecting familieshereditary familiescross-intersecting familiesChvátal's conjecture

Mathematics Subject Classification ID

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

Abstract: Families $mathcal{A}_1,mathcal{A}_2,\mathrm{...},mathcal{A}_k$ of sets are said to be emph{cross-intersecting} if for any $i$ and $j$ in $1,2,\mathrm{...},k$ with $ieqj$, any set in $mathcal{A}_i$ intersects any set in $mathcal{A}_j$. For a finite set $X$, let $2^X$ denote the emph{power set of $X$} (the family of all subsets of $X$). A family $mathcalH$ is said to be emph{hereditary} if all subsets of any set in $mathcalH$ are in $mathcalH$; so $mathcalH$ is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family $mathcalHeqemptyset$ of $2^X$ and any $kgeq|X|+1$, both the sum and product of sizes of $k$ cross-intersecting sub-families $mathcal{A}_1,mathcal{A}_2,\mathrm{...},mathcal{A}_k$ (not necessarily distinct or non-empty) of $mathcalH$ are maxima if $mathcal{A}_1=mathcal{A}_2=\mathrm{...}=mathcal{A}_k=mathcalS$ for some largest emph{star $mathcalS$ of $mathcalH$} (a sub-family of $mathcalH$ whose sets have a common element). We prove this for the case when $mathcalH$ is emph{compressed with respect to an element $x$ of $X$}, and for this purpose we establish new properties of the usual emph{compression operation}. For the product, we actually conjecture that the configuration $mathcal{A}_1=mathcal{A}_2=\mathrm{...}=mathcal{A}_k=mathcalS$ is optimal for any hereditary $mathcalH$ and any $kgeq2$, and we prove this for a special case too.

Recommendations

• On cross-intersecting uniform sub-families of hereditary families
• Cross-intersecting non-empty uniform subfamilies of hereditary families
• Cross-intersecting subfamilies of levels of hereditary families
• Extremal t -intersecting sub-families of hereditary families
• The maximum product of sizes of cross-intersecting families

Cites work

• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3477225 (Why is no real title available?)
• scientific article; zbMATH DE number 3506745 (Why is no real title available?)
• scientific article; zbMATH DE number 3619902 (Why is no real title available?)
• A new result on Chvátal's conjecture
• A short proof of a cross-intersection theorem of Hilton
• An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
• Cross-Intersecting Families of Partial Permutations
• Cross-intersecting families and primitivity of symmetric systems
• Cross-intersecting families of permutations
• Extremal t -intersecting sub-families of hereditary families
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Multiple cross-intersecting families of signed sets
• On Chvàtal's conjecture and a conjecture on families of signed sets
• Some results about the Chvatal conjecture
• The maximum sum and the maximum product of sizes of cross-intersecting families

Cited in

(13)

• On cross-intersecting uniform sub-families of hereditary families
• A refined result on cross-intersecting families
• Application of hypergraph Hoffman's bound to intersecting families
• The maximum product of sizes of cross-intersecting families
• The maximum product of weights of cross-intersecting families
• A note on the maximum product-size of non-trivial cross t-intersecting families
• The maximum sum and the maximum product of sizes of cross-intersecting families
• Extremal t -intersecting sub-families of hereditary families
• Cross-intersecting non-empty uniform subfamilies of hereditary families
• A cross‐intersection theorem for subsets of a set
• Cross-intersecting subfamilies of levels of hereditary families
• A sharp bound for the product of weights of cross-intersecting families
• Non-trivial intersecting uniform sub-families of hereditary families

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

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