Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
 Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(e) ISSN 0894-0347(p)

     

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

Author(s): Jeff Kahn
Journal: J. Amer. Math. Soc. 7 (1994), 125-143.
MSC: Primary 05B40; Secondary 05C35, 05C65
MathSciNet review: 1224593
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

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

References:

[1]
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. MR 0505796 (58:21793)

[2]
F. Bien, Constructions of telephone networks by group representations, Notices Amer. Math. Soc. 36 (1989), 5-22. MR 972207 (90a:90052)

[3]
A. Blokhuis, More on maximal intersecting families of finite sets, J. Combin. Theory Ser. A 44 (1987), 299-303. MR 879687 (88b:05006)

[4]
B. Bollobás, A probabilistic proof of an asymptotic formula for the number of regular graphs, European J. Combin. 1 (1980), 311-314. MR 595929 (82i:05045)

[5]
-, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), 433-436. MR 624948 (82m:05079)

[6]
E. Boros, Z. Füredi, and J. Kahn, Maximal intersecting families and affine regular polygons, J. Combin. Theory Ser. A 52 (1989), 1-9. MR 1008155 (90g:05004)

[7]
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. MR 0122729 (23:A69)

[8]
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. MR 0122730 (23:A70)

[9]
P. Dembowski, Finite geometries, Springer, New York, 1968. MR 0233275 (38:1597)

[10]
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.

[11]
J. Edmonds, Maximum matching and a polyhedron with $ 0,1$-vertices, J. Res. Nat. Bur. Standards B 69 (1965), 125-130. MR 0183532 (32:1012)

[12]
P. Erdös, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25-42. MR 602413 (82k:05001)

[13]
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. MR 0382050 (52:2938)

[14]
P. Frankl and V. Rödl, Near-perfect coverings in graphs and hypergraphs, Europ. J. Combin. 6 (1985), 317-326. MR 829351 (88a:05116)

[15]
Z. Füredi, On maximal intersecting families of finite sets, J. Combin. Theory A 28 (1980), 282-289. MR 570210 (81g:05002)

[16]
-, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115-206. MR 943753 (89i:05214)

[17]
J. Kahn, On a problem of Erdös and Lovász: random lines in a projective plane, Combinatorica 12 (1992), 417-423. MR 1194732 (93m:05199)

[18]
-, On a theorem of Frankl and Rödl, in preparation.

[19]
-, 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).

[20]
J.-C. Meyer, Hypergraph seminar (C. Berge and D. K. Ray-Chaudhuri, Eds.), Springer, Berlin, Heidelberg, and New York, 1974, pp. 285-286. MR 0360374 (50:12824)

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

[22]
N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A 51 (1989), 24-42. MR 993646 (90h:05091)

[23]
V. Rödl, On a packing and covering problem, European J. Combin. 5 (1985), 69-78. MR 793489 (86k:05033)

[24]
J. Spencer, lecture notes, M.I.T., 1987.

[25]
W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. (2) 22 (1947), 107-111. MR 0023048 (9:297d)

[26]
R. M. Wilson, Concerning the number of mutually orthogonal Latin squares, Discrete Math. 9 (1974), 181-198. MR 0345845 (49:10575)

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:

DOI: 10.1090/S0894-0347-1994-1224593-5
PII: S0894-0347-1994-1224593-5
Keywords: Hypergraphs, extremal problems, transversal designs
Copyright of article: Copyright 1994, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia