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)$
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

A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size

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

On a theorem of Frankl and Rödl

Recent results on some not-so-recent hypergraph matching and covering problems

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

On the complexity of a concentrator

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
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