On a problem of Erdős and Lovász. II. $n(r)=O(r)$
HTML articles powered by AMS MathViewer
- by Jeff Kahn PDF
- J. Amer. Math. Soc. 7 (1994), 125-143 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
- E. A. Bender and E. R. Canfield, The asymptotic number of labelled graphs with given degree sequences, J. Combin. Theory Ser. A 24 (1978), 296-307.
F. Bien, Constructions of telephone networks by group representations, Notices Amer. Math. Soc. 36 (1989), 5-22.
A. Blokhuis, More on maximal intersecting families of finite sets, J. Combin. Theory Ser. A 44 (1987), 299-303.
B. Bollobás, A probabilistic proof of an asymptotic formula for the number of regular graphs, European J. Combin. 1 (1980), 311-314.
—, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), 433-436.
E. Boros, Z. Füredi, and J. Kahn, Maximal intersecting families and affine regular polygons, J. Combin. Theory Ser. A 52 (1989), 1-9.
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, Canad. J. Math. 12 (1960), 189-203.
S. Chowla, P. Erdös, and E. Straus, On the maximal number of pairwise orthogonal Latin squares of a given order, Canad. J. Math. 12 (1960), 204-208.
P. Dembowski, Finite geometries, Springer, New York, 1968.
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.
J. Edmonds, Maximum matching and a polyhedron with $0,1$-vertices, J. Res. Nat. Bur. Standards B 69 (1965), 125-130.
P. Erdös, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25-42.
P. Erdös and L. Lovász, Problems and results on $3$-chromatic hypergraphs and some related questions, Colloq. Math. Soc. János Bolyai 10 (1974), 609-627.
P. Frankl and V. Rödl, Near-perfect coverings in graphs and hypergraphs, Europ. J. Combin. 6 (1985), 317-326.
Z. Füredi, On maximal intersecting families of finite sets, J. Combin. Theory A 28 (1980), 282-289.
—, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115-206.
J. Kahn, On a problem of Erdös and Lovász: random lines in a projective plane, Combinatorica 12 (1992), 417-423.
—, 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).
J.-C. Meyer, Hypergraph seminar (C. Berge and D. K. Ray-Chaudhuri, Eds.), Springer, Berlin, Heidelberg, and New York, 1974, pp. 285-286.
M. Pinsker, On the complexity of a concentrator, Proc. 7th Int’l. Teletraffic Conference, Stockholm, 1973, pp. 318/1-318/4.
N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A 51 (1989), 24-42.
V. Rödl, On a packing and covering problem, European J. Combin. 5 (1985), 69-78.
J. Spencer, lecture notes, M.I.T., 1987.
W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. (2) 22 (1947), 107-111.
R. M. Wilson, Concerning the number of mutually orthogonal Latin squares, Discrete Math. 9 (1974), 181-198.
Additional 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