## On a problem of Erdős and Lovász. II. $n(r)=O(r)$

HTML articles powered by AMS MathViewer

- by Jeff Kahn
- J. Amer. Math. Soc.
**7**(1994), 125-143 - DOI: https://doi.org/10.1090/S0894-0347-1994-1224593-5
- PDF | Request permission

## Abstract:

We prove a linear upper bound on the function $n(r) = {\text {min}}\{ \left | {\mathcal {H}} \right |:\mathcal {H}$ an $r$-uniform, intersecting hypergraph with $\tau (\mathcal {H}) = r\}$, thus settling a longstanding problem of Erdös and Lovász.## References

- Edward A. Bender and E. Rodney Canfield,
*The asymptotic number of labeled graphs with given degree sequences*, J. Combinatorial Theory Ser. A**24**(1978), no. 3, 296–307. MR**505796**, DOI 10.1016/0097-3165(78)90059-6 - Frédéric Bien,
*Constructions of telephone networks by group representations*, Notices Amer. Math. Soc.**36**(1989), no. 1, 5–22. MR**972207** - Aart Blokhuis,
*More on maximal intersecting families of finite sets*, J. Combin. Theory Ser. A**44**(1987), no. 2, 299–303. MR**879687**, DOI 10.1016/0097-3165(87)90036-7 - Béla Bollobás,
*A probabilistic proof of an asymptotic formula for the number of labelled regular graphs*, European J. Combin.**1**(1980), no. 4, 311–316. MR**595929**, DOI 10.1016/S0195-6698(80)80030-8 - Béla Bollobás,
*The independence ratio of regular graphs*, Proc. Amer. Math. Soc.**83**(1981), no. 2, 433–436. MR**624948**, DOI 10.1090/S0002-9939-1981-0624948-6 - Endre Boros, Zoltán Füredi, and Jeff Kahn,
*Maximal intersecting families and affine regular polygons in $\textrm {PG}(2,q)$*, J. Combin. Theory Ser. A**52**(1989), no. 1, 1–9. MR**1008155**, DOI 10.1016/0097-3165(89)90057-5 - R. C. Bose, S. S. Shrikhande, and E. T. Parker,
*Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture*, Canadian J. Math.**12**(1960), 189–203. MR**122729**, DOI 10.4153/CJM-1960-016-5 - S. Chowla, P. Erdős, and E. G. Straus,
*On the maximal number of pairwise orthogonal Latin squares of a given order*, Canadian J. Math.**12**(1960), 204–208. MR**122730**, DOI 10.4153/CJM-1960-017-2 - P. Dembowski,
*Finite geometries*, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Springer-Verlag, Berlin-New York, 1968. MR**0233275**, DOI 10.1007/978-3-642-62012-6
S. J. Dow, D. A. Drake, Z. Füredi, and J. A. Larson, - Jack Edmonds,
*Maximum matching and a polyhedron with $0,1$-vertices*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 125–130. MR**183532**, DOI 10.6028/jres.069B.013 - P. Erdős,
*On the combinatorial problems which I would most like to see solved*, Combinatorica**1**(1981), no. 1, 25–42. MR**602413**, DOI 10.1007/BF02579174 - P. Erdős and L. Lovász,
*Problems and results on $3$-chromatic hypergraphs and some related questions*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627. MR**0382050** - P. Frankl and V. Rödl,
*Near perfect coverings in graphs and hypergraphs*, European J. Combin.**6**(1985), no. 4, 317–326. MR**829351**, DOI 10.1016/S0195-6698(85)80045-7 - Zoltán Füredi,
*On maximal intersecting families of finite sets*, J. Combin. Theory Ser. A**28**(1980), no. 3, 282–289. MR**570210**, DOI 10.1016/0097-3165(80)90071-0 - Zoltán Füredi,
*Matchings and covers in hypergraphs*, Graphs Combin.**4**(1988), no. 2, 115–206. MR**943753**, DOI 10.1007/BF01864160 - Jeff Kahn,
*On a problem of Erdős and Lovász: random lines in a projective plane*, Combinatorica**12**(1992), no. 4, 417–423. MR**1194732**, DOI 10.1007/BF01305234
—, *Unsolved problems*, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974, pp. 278–287. MR**0360374**
M. Pinsker, - Nicholas Pippenger and Joel Spencer,
*Asymptotic behavior of the chromatic index for hypergraphs*, J. Combin. Theory Ser. A**51**(1989), no. 1, 24–42. MR**993646**, DOI 10.1016/0097-3165(89)90074-5 - Vojtěch Rödl,
*On a packing and covering problem*, European J. Combin.**6**(1985), no. 1, 69–78. MR**793489**, DOI 10.1016/S0195-6698(85)80023-8
J. Spencer, lecture notes, M.I.T., 1987.
- W. T. Tutte,
*The factorization of linear graphs*, J. London Math. Soc.**22**(1947), 107–111. MR**23048**, DOI 10.1112/jlms/s1-22.2.107 - Richard M. Wilson,
*Concerning the number of mutually orthogonal Latin squares*, Discrete Math.**9**(1974), 181–198. MR**345845**, DOI 10.1016/0012-365X(74)90148-4

*A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size*, Congr. Numer.

**48**(1985), 47-48.

*On a theorem of Frankl and Rödl*, in preparation. —,

*Recent results on some not-so-recent hypergraph matching and covering problems*, Proc. 1st Int’l Conference on Extremal Problems for Finite Sets, Visegrád, June 1991 (to appear).

*On the complexity of a concentrator*, Proc. 7th Int’l. Teletraffic Conference, Stockholm, 1973, pp. 318/1-318/4.

## Bibliographic Information

- © Copyright 1994 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**7**(1994), 125-143 - MSC: Primary 05B40; Secondary 05C35, 05C65
- DOI: https://doi.org/10.1090/S0894-0347-1994-1224593-5
- MathSciNet review: 1224593