Cross-intersecting sub-families of hereditary families

DOI10.1016/J.JCTA.2011.12.002zbMATH Open1238.05266arXiv1103.3858OpenAlexW2041346411MaRDI QIDQ765869FDOQ765869

Authors: Peter Borg 

Publication date: 22 March 2012

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

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.

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

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

zbMATH Keywords

extremal set theoryintersecting familieshereditary familiescross-intersecting families[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Chv%EF%BF%BD%EF%BF%BDtal%27s+conjecture&go=Go Chv��tal's conjecture]

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• A refined result on cross-intersecting families
• On cross-intersecting uniform sub-families of hereditary 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

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)