On a problem of Erdős and Lovász. II. 𝑛(𝑟)=𝑂(𝑟)

Kahn, Jeff

doi:10.1090/S0894-0347-1994-1224593-5

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

Author: Jeff Kahn
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

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 https://doi.org/10.1016/0097-3165%2878%2990059-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 https://doi.org/10.1016/0097-3165%2887%2990036-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 https://doi.org/10.1016/S0195-6698%2880%2980030-8
Béla Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), no. 2, 433–436. MR 624948, DOI https://doi.org/10.1090/S0002-9939-1981-0624948-6
Endre Boros, Zoltán Füredi, and Jeff Kahn, Maximal intersecting families and affine regular polygons in ${\rm PG}(2,q)$, J. Combin. Theory Ser. A 52 (1989), no. 1, 1–9. MR 1008155, DOI https://doi.org/10.1016/0097-3165%2889%2990057-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 https://doi.org/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 https://doi.org/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

S. J. Dow, D. A. Drake, Z. Füredi, and J. A. Larson, A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size, Congr. Numer. 48 (1985), 47-48.

Jack Edmonds, Maximum matching and a polyhedron with $0,1$-vertices, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125–130. MR 183532
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 https://doi.org/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), Vol. II, North-Holland, Amsterdam, 1975, pp. 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. 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 https://doi.org/10.1016/S0195-6698%2885%2980045-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 https://doi.org/10.1016/0097-3165%2880%2990071-0
Zoltán Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), no. 2, 115–206. MR 943753, DOI https://doi.org/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 https://doi.org/10.1007/BF01305234

---, 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).

Unsolved problems, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Springer, Berlin, 1974, pp. 278–287. Lecture Notes in Math., Vol. 411. MR 0360374

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

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 https://doi.org/10.1016/0097-3165%2889%2990074-5
Vojtěch Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78. MR 793489, DOI https://doi.org/10.1016/S0195-6698%2885%2980023-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 https://doi.org/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 https://doi.org/10.1016/0012-365X%2874%2990148-4