Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-14T03:24:00.406Z Has data issue: false hasContentIssue false
  • English
  • Français

A near-exponential improvement of a bound of Erdős and Lovász on maximal intersecting families

Part of: Graph theory

Published online by Cambridge University Press:  04 June 2019

Peter Frankl
Peter Frankl*
Affiliation:
Alfred Rényi Institute of Mathematics, Hungarian Academy of Sciences, H-1053 Budapest, Retanoda u. 13-15, Hungary
*
Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Let m(k) denote the maximum number of edges in a non-extendable, intersecting k-graph. Erdős and Lovász proved that m(k) ≤ kk. For k ≥ 625 we prove m(k) < kk・e−k1/4/6.

MSC classification

Primary: 05C65: Hypergraphs
Secondary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 5 , September 2019 , pp. 733 - 739
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arman, A. and Retter, T. (2017) An upper bound for the size of a k-uniform intersecting family with covering number k. J. Combin. Theory Ser. A 147 18–26.CrossRefGoogle Scholar
Erdős , P. and Lovász, L. (1974) Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets: Proc. Colloq. Math. Soc. János Bolyai, Keszthely, Hungary, 1973, North-Holland, pp. 609–627.Google Scholar
Frankl, P., Ota, K. and Tokushige, N. (1996) Covers in uniform intersecting families and a counterexample to a conjecture of Lovász. J. Combin. Theory Ser. A 74 33–42.CrossRefGoogle Scholar
Gyárfás, A. (1977) Partition covers and blocking sets in hypergraphs (in Hungarian). Thesis, Studies of Computer and Automation Research Institute of Hungarian Academy of Sciences, 177.Google Scholar
Lovász, L. (1975) On the minimax theorems of combinatorics (in Hungarian). Mat. Lapok 26 209–264.Google Scholar
Tuza, Z. (1994) Inequalities for minimal covering sets in set systems of given rank. Discrete Appl. Math . 51 187–195.CrossRefGoogle Scholar