On the arithmetic mean of the size of cross-union families

DOI10.1007/S10474-021-01138-6MaRDI QIDQ2043692zbMATH OpenOpenAlexFDO

Authors Peter Frankl

Publication date 3 August 2021

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10474-021-01138-6

zbMATH Keywords

cyclic permutationfinite setintersection

Mathematics Subject Classification ID

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

Review text

The celebrated Erdős-Ko-Rado theorem provides an upper bound on the size of an intersecting family; its generalization by \textit{L. Pyber} [J. Comb. Theory, Ser. A 43, 85--90 (1986; Zbl 0614.05001)] deals with the size of cross-intersecting families.\par The families \(\mathcal{F}_{0},\mathcal{F}_{1},\dots,\mathcal{F}_{s}\) of \(k\)-subsets of \([n]\) are cross-union if \(F_{0}\cup F_{1}\cup \dots\cup F_{s}\neq \lbrack n]\) for all choices of \(F_{i}\in \mathcal{F}_{i}.\) \textit{P. Frankl} and \textit{N. Tokushige} [Comb. Probab. Comput. 20, No. 5, 749--752 (2011; Zbl 1283.05259)] proved that for \(n\leq k(s+1)\) the geometric mean of \(\left\vert \mathcal{F}_{i}\right\vert \) is at most \(\binom{n-1}{k}\). It is conjectured that the same is true for the arithmetic mean for the range \(ks<n<k(s+1)\), \(s>s_{0}(k)\). As a support, the conjecture is proved in several cases.

Recommendations

• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• A size-sensitive inequality for cross-intersecting families
• An Erdős-Ko-Rado theorem for cross t-intersecting families
• Uniform s-Cross-Intersecting Families
• On the union of intersecting families

Cites work

• A new generalization of the Erdős-Ko-Rado theorem
• A new short proof of the EKR theorem
• A Short Proof for an Extension of the Erdős–Ko–Rado Theorem
• A simple proof of the Erdős-Chao Ko-Rado theorem
• Erdős-Ko-Rado from Kruskal-Katona
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Extremal Finite Set Theory
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• Improved bounds for Erdős' matching conjecture
• Intersection theorems for systems of finite sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Maximal number of subsets of a finite set No k of which are pairwise disjoint
• New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• Old and new applications of Katona's circle
• On r-cross intersecting families of sets
• On intersecting families of finite sets
• On Sperner families satisfying an additional condition
• On the Shannon capacity of a graph
• Regular bipartite graphs and intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets

Cited in

(2)

• A proof of Frankl's conjecture on cross-union families
• The maximum sum of sizes of non-empty pairwise cross-intersecting families

This page was built for publication: On the arithmetic mean of the size of cross-union families

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