Geodesic
On a problem of Erdős and Lovász. II. 𝑛(𝑟)=𝑂(𝑟)
Journal of the American Mathematical Society, Tome 07 (1994) no. 1, pp. 125-143

Voir la notice de l'article provenant de la source American Mathematical Society

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. 
@article{10_1090_S0894_0347_1994_1224593_5,
     author = {Kahn, Jeff},
     title = {On a problem of {Erd\r{A}‘s} and {Lov\~A{\textexclamdown}sz.} {II.} {\dh}‘›({\dh}‘Ÿ)={\dh}‘‚({\dh}‘Ÿ)},
     journal = {Journal of the American Mathematical Society},
     pages = {125--143},
     publisher = {mathdoc},
     volume = {07},
     number = {1},
     year = {1994},
     doi = {10.1090/S0894-0347-1994-1224593-5},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1994-1224593-5/}
}
TY  - JOUR
AU  - Kahn, Jeff
TI  - On a problem of Erdős and Lovász. II. 𝑛(𝑟)=𝑂(𝑟)
JO  - Journal of the American Mathematical Society
PY  - 1994
SP  - 125
EP  - 143
VL  - 07
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1994-1224593-5/
DO  - 10.1090/S0894-0347-1994-1224593-5
ID  - 10_1090_S0894_0347_1994_1224593_5
ER  - 
%0 Journal Article
%A Kahn, Jeff
%T On a problem of Erdős and Lovász. II. 𝑛(𝑟)=𝑂(𝑟)
%J Journal of the American Mathematical Society
%D 1994
%P 125-143
%V 07
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1994-1224593-5/
%R 10.1090/S0894-0347-1994-1224593-5
%F 10_1090_S0894_0347_1994_1224593_5
Kahn, Jeff. On a problem of Erdős and Lovász. II. 𝑛(𝑟)=𝑂(𝑟). Journal of the American Mathematical Society, Tome 07 (1994) no. 1, pp. 125-143. doi: 10.1090/S0894-0347-1994-1224593-5

[1] Bender, Edward A., Canfield, E. Rodney The asymptotic number of labeled graphs with given degree sequences J. Combinatorial Theory Ser. A 1978 296 307

[2] Bien, Frã©Dã©Ric Constructions of telephone networks by group representations Notices Amer. Math. Soc. 1989 5 22

[3] Blokhuis, Aart More on maximal intersecting families of finite sets J. Combin. Theory Ser. A 1987 299 303

[4] Bollobã¡S, Bã©La A probabilistic proof of an asymptotic formula for the number of labelled regular graphs European J. Combin. 1980 311 316

[5] Bollobã¡S, Bã©La The independence ratio of regular graphs Proc. Amer. Math. Soc. 1981 433 436

[6] Boros, Endre, Fã¼Redi, Zoltã¡N, Kahn, Jeff Maximal intersecting families and affine regular polygons in 𝑃𝐺(2,𝑞) J. Combin. Theory Ser. A 1989 1 9

[7] Bose, R. C., Shrikhande, S. S., Parker, E. T. Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture Canadian J. Math. 1960 189 203

[8] Chowla, S., Erdå‘S, P., Straus, E. G. On the maximal number of pairwise orthogonal Latin squares of a given order Canadian J. Math. 1960 204 208

[9] Dembowski, P. Finite geometries 1968

[10] Edmonds, Jack Maximum matching and a polyhedron with 0,1-vertices J. Res. Nat. Bur. Standards Sect. B 1965 125 130

[11] Erdå‘S, P. On the combinatorial problems which I would most like to see solved Combinatorica 1981 25 42

[12] Erdå‘S, P., Lovã¡Sz, L. Problems and results on 3-chromatic hypergraphs and some related questions 1975 609 627

[13] Frankl, P., Rã¶Dl, V. Near perfect coverings in graphs and hypergraphs European J. Combin. 1985 317 326

[14] Fã¼Redi, Zoltã¡N On maximal intersecting families of finite sets J. Combin. Theory Ser. A 1980 282 289

[15] Fã¼Redi, Zoltã¡N Matchings and covers in hypergraphs Graphs Combin. 1988 115 206

[16] Kahn, Jeff On a problem of Erdős and Lovász: random lines in a projective plane Combinatorica 1992 417 423

[17] Unsolved problems 1974 278 287

[18] Pippenger, Nicholas, Spencer, Joel Asymptotic behavior of the chromatic index for hypergraphs J. Combin. Theory Ser. A 1989 24 42

[19] Rã¶Dl, Vojtä›Ch On a packing and covering problem European J. Combin. 1985 69 78

[20] Tutte, W. T. The factorization of linear graphs J. London Math. Soc. 1947 107 111

[21] Wilson, Richard M. Concerning the number of mutually orthogonal Latin squares Discrete Math. 1974 181 198

Cité par Sources :