Abstract
Let \(n > k > 1\) be integers, \([n] = \{1, \ldots, n\}\) the standard \(n\)-element set and \({[n]\choose k}\) the collection of all its \(k\)-subsets. The families \(\mathcal F_0, \ldots, \mathcal F_s \subset {[n]\choose k}\) are said to be cross-union if \(F_0 \cup \cdots \cup F_s \neq [n]\) for all choices of \(F_i \in \mathcal F_i\). It is known [13] that for \(n \leq k(s + 1)\) the geometric mean of \(|\mathcal F_i|\) is at most \({n - 1\choose k}\). We conjecture that the same is true for the arithmetic mean for the range \(ks < n < k(s + 1)\), \(s > s_0(k)\) (Conjecture 8.1) and prove this in several cases. The proof for the case \(n = ks + 2\) relies on a novel approach, a combination of shifting and Katona’s cyclic permutation method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahlswede, R., Khachatrian, L.: The complete intersection theorem for systems of finite sets. European J. Combin. 18, 125–136 (1997)
D. E. Daykin, Erdős–Ko–Rado from Kruskal–Katona, J. Combin. Theory, Ser. A, 17 (1974), 254–255
Erdős, P.: A problem on independent \(r\)-tuples. Ann. Univ. Sci. Budapest. 8, 93–95 (1965)
P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2), 12 (1961), 313–320
P. Frankl, On Sperner families satisfying an additional condition, J. Combin. Theory, Ser. A, 20 (1976), 1–11
P. Frankl, On intersecting families of finite sets, J. Combin. Theory, Ser. A, 24 (1978), 146–161
P. Frankl, Erdős–Ko–Rado theorem with conditions on the maximal degree, J. Combin. Theory, Ser. A, 46 (1987), 252–263
P. Frankl, The shifting techniques in extremal set theory, in: Surveys in Combinatorics, 1987, LMS Lecture Note Series, 123, Cambridge University Press (1987), pp. 81–110
P. Frankl, Improved bounds for Erdős' Matching Conjecture, J. Combin. Theory, Ser. A, 120 (2013), 1068–1072
P. Frankl, Old and new applications of Katona's circle, submitted
P. Frankl and Z. Füredi, A new short proof of the EKR theorem, J. Combin. Theory, Ser. A, 119 (2012), 1388–1390
P. Frankl and A. B. Kupavskii, A short proof for an extension of the Erdős–Ko–Rado Theorem, in: Proceedings of Connections in Discrete Mathematics. A celebration of the work of Ron Graham, Cambridge University Press (2018), pp. 169–172
Frankl, P., Tokushige, N.: On \(r\)-cross intersecting families of sets. Combin. Probab. Comput. 20, 749–752 (2011)
Gerbner, D., Patkós, B.: Extremal Finite Set Theory. Chapman and Hall/CRC (2018)
A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2), 18 (1967), 369–384
Hurlbert, G., Kamat, V.: New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems. Discrete Math. 341, 1749–1754 (2018)
Katona, G.O.H.: Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hungar. 15, 329–337 (1964)
G. O. H. Katona, A simple proof of the Erdős–Chao Ko–Rado theorem, J. Combin. Theory, Ser. B, 13 (1972), 183–184
Kleitman, D.J.: Maximal number of subsets of a finite set no \(k\) of which are pairwise disjoint. J. Combin. Theory 5, 157–163 (1968)
A. Kupavskii and D. Zakharov, Regular bipartite graphs and intersecting families, J. Combin. Theory, Ser. A, 155 (2018), 180–189
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Information Theory 25, 1–7 (1979)
L. Pyber, A new generalization of the Erdős–Ko–Rado theorem, J. Combin. Theory, Ser. A, 43 (1986), 85–90
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926.
Rights and permissions
About this article
Cite this article
Frankl, P. On the arithmetic mean of the size of cross-union families. Acta Math. Hungar. 164, 312–325 (2021). https://doi.org/10.1007/s10474-021-01138-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-021-01138-6