Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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.
    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.
Similar Articles
  • Retrieve articles in Journal of the American Mathematical Society with MSC: 05B40, 05C35, 05C65
  • Retrieve articles in all journals with MSC: 05B40, 05C35, 05C65
Additional Information
  • © Copyright 1994 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 7 (1994), 125-143
  • MSC: Primary 05B40; Secondary 05C35, 05C65
  • DOI:
  • MathSciNet review: 1224593