Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Paul Erdős: Life and Work Read chapter Read first chapter

2013 | OriginalPaper | Chapter

On Some Hypergraph Problems of Paul Erdős and the Asymptotics of Matchings, Covers and Colorings

Author : Jeff Kahn

Published in: The Mathematics of Paul Erdős I

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This article summarizes progress on several old hypergraph problems of Paul Erdős and a few questions to which they led. Quite unexpectedly, there turned out to be substantial connections between the problems under discussion, surely some indication (if any were needed) that Erdős’ questions were the “right” ones. Here’s a quick synopsis.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Games, Randomness and Algorithms
next chapter The Origins of the Theory of Random Graphs
Literature
1.
M. Ajtai, J. Komlós and E. Szemerédi, A dense infinite Sidon sequence, Europ. J. Combinatorics 2 (1981), 1–11.
2.
M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combinatorial Th. (A) 299 (1980), 354–360.
3.
N. Alon, Restricted colorings of graphs, Surveys in Combinatorics, 1993 (Proc. 14th British Combinatorial Conf.), Cambridge Univ. Press, Cambridge, 1993.
4.
N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, New York, 1992.MATH
5.
N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.
6.
L.D. Andersen, On edge-colourings of graphs, Math. Scand. 40 (1977), 161–175.
7.
K. Azuma, Weighted sums of certain dependent random variables, Tokuku Math. J. 19 (1967), 357–367.
8.
E. A. Bender and E. R. Canfield, The asymptotic number of labelled graphs with given degree sequences, J. Combinatorial Th. (A) 24 (1978), 296–307.
9.
C. Berge, Hypergraphs: Combinatorics of Finite Sets, North Holland, Amsterdam, 1989.MATH
10.
C. Berge, On the chromatic index of a linear hypergraph and the Chvátal conjecture, pp. 40–44 in Combinatorial Mathematics: Proc. 3rd Int’l. Conf (New York, 1985), Ann. N. Y. Acad. Sci. 555, New York Acad. Sci., New York, 1989.
11.
A. Blokhuis, More on maximal intersecting families of finite sets, J. Combinatorial Th. (A) 44 (1987), 299–303.
12.
B. Bollobás, A probabilistic proof of an asymptotic formula for the number of regular graphs, Europ. J. Combinatorics 1 (1980), 311–316.
13.
B. Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), 433–436.
14.
B. Bollobás, Martingales, isoperimetric inequalities and random graphs, in Combinatories, A. Hajnal, L. Lovász and V.T. Sós Eds., Colloq. Math. Soc. János Bolyai 52, North Holland, 1988.
15.
B. Bollobás and A. J. Harris, List-colourings of graphs, Graphs and Combinatorics 1 (1985), 115–127.
16.
B. Bollobás and H. Hind, A new upper bound for the list chromatic number, Discrete Math. 74 (1989), 65–75.
17.
V. Boltjansky and I. Gohberg, Results and Problems in Combinatorial Geometry, Cambridge University Press, Cambridge, 1985.MATHCrossRef
18.
E. Boros, Z. Füredi and J. Kahn, Maximal intersecting families and affine regular polygons, J. Combinatorial Th. (A) 52 (1989), 1–9.
19.
K. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundamenta Math. 20 (1933), 177–190.
20.
N. G. de Bruijn and P. Erdős, A combinatorial problem, Indagationes Math. 8 (1946), 461–467.
21.
W. I. Chang and E. Lawler, Edge coloring of hypergraphs and a conjecture of Erdős, Faber, Lovász, Combinatorica 8 (1989), 293–295.
22.
A. Chetwynd and R. Häggkvist, A note on list-colorings, J. Graph Th. 13 (1989), 87–95.
23.
S. Chowla, P. Erdős and E. Straus, On the maximal number of pairwise orthogonal Latin squares of a given order, Can. J. Math. 12 (1960), 204–208.MATHCrossRef
24.
H. Croft, K. Falconer and R. Guy, Unsolved Problems in Geometry, Springer-Verlag, New York, 1991.MATHCrossRef
25.
S. J. Dow, C. 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, Congressus Numerantium 48 (1985), 47–48.
26.
J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bureau of Standards (B) 69 (1965), 125–130.
27.
M.N. Ellingham and L. Goddyn, List edge colourings of some regular 1-factorable multigraphs, Combinatorica16 (1996), 343–352.
28.
P. Erdős, Some old and new problems in various branches of combinatorics, Congressus Numerantium 23 (1979), 19–37.
29.
P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25–42.
30.
P. Erdős, My Scottish book “problems”, pp. 35–43 in The Scottish Book. Mathematics from the Scottish Café (R.D. Mauldin, ed.), Birkhäuser, 1981.
31.
P. Erdős, Some of my old and new combinatorial problems, pp. 35–46 in Paths, Flows and VLSI-Layout (B. Korte, L. Lovász, H.-J. Promel and A. Schrijver, eds.), Springer, Berlin, 1990.
32.
P. Erdős and H. Hanani, On a limit theorem in combinatorial analysis, Publ. Math. Debrecen 10 (1963), 10–13.
33.
P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Coll. Math. Soc. J. Bolyai 10 (1974), 609–627.
34.
P. Erdős, A. Rubin and H. Taylor, Choosability in graphs, Congressus Numerantium 26 (1979), 125–157.
35.
S. J. Fiorini and R. J. Wilson, Edge Colourings of Graphs, Research Notes in Mathematics 16, Pitman, London, 1977.
36.
R. A. Fisher, An examination of the different possible solutions of a problem in incomplete blocks, Ann Eugenics 10 (1940), 52–75.
37.
H. Fleischner and M. Stiebitz, A solution to a colouring problem of P. Erdős, Disc. Math. 101 (1992), 39–48.
38.
P. Frankl and V. Rödl, Near-perfect coverings in graphs and hypergraphs, Europ. J. Combinatorics 6 (1985), 317–326.
39.
P. Frankl and R.M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357–368.
40.
Z. Füredi, On maximal intersecting families of finite sets, J. Combinatorial Th. (A) 28 (1980), 282–289.
41.
Z. Füredi, The chromatic index of simple hypergraphs, Graphs and Combinetorics 2 (1986), 89–92.
42.
Z. Füredi, Matchings and covers in hypergraphs, Graphs and Combinatorics 4 (1988), 115–206.
43.
C. D. Godsil, Matching behavior is asymptotically normal, Combinatorica 1 (1981), 369–376.
44.
C.D. Godsil, Matchings and walks in graphs, J. Graph Th. 5 (1981), 285–297.
45.
M. K. Goldberg, Edge-colorings of multigraphs: recoloring technique, J. Graph Th. 8 (1984), 123–127.
46.
B. Grünbaum, Borsuk’s problem and related questions, Proc. Symp. Pure Math. 7 (Convexity), Amer. Math. Soc., 1963.
47.
R. Häggkvist and A. Chetwynd, Some upper bounds on the total and list chromatic numbers of multigraphs, J. Graph Th. 16 (1992), 503–516.
48.
R. Häggkvist and J. C. M. Janssen, On the list-chromatic index of bipartite graphs, manuscript, 1993.
49.
L.H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Stat. 38 (1967), 410–414.
50.
O. J. Heilmann and E.H. Lieb, Monomers and dimers, Phys. Rev. Letters 24 (1970), 1412–1414.
51.
O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Physics 25 (1972), 190–232.
52.
H.R. Hind, Restricted edge-colourings, Doctoral thesis, Peterhouse College, Cambridge, 1988.
53.
N. Hindman, On a conjecture of Erdős, Faber and Lovász about n-colorings, Canadian J. Math. 33 (1981), 563–570.
54.
W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc. 27 (1963), 13–30.
55.
R. Huang and G.-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients, manuscript, 1993.
56.
J.C.M. Janssen, The Dinitz problem solved for rectangles, Bull. Amer. Math. Soc. 29 (1993), 243–249.
57.
J. Kahn, On a theorem of Frankl and Rödl, in preparation.
58.
J. Kahn, Coloring nearly-disjoint hypergraphs with n + o(n) colors, J. Combinatorial Th. (A) 59 (1992), 31–39.
59.
J. Kahn, On a problem of Erdős and Lovász: random lines in a projective plane, Combinatorica 12 (1992), 417–423.
60.
J. Kahn, Recent results on some not-so-recent hypergraph matching and covering problems, pp. 305–353 in Extremal Problems for Finite Sets, Visegrád, 1991, Bolyai Soc. Math. Studies 3, 1994.
61.
J. Kahn, On a problem of Erdős and Lovász II: n(r) = O(r), J. Amer. Math. Soc. 7 (1994), 125–143.
62.
63.
J. Kahn, A normal law for matchings, Combinatorica 20 (2000), 339–391.
64.
J. Kahn and G. Kalai, A problem of Füredi and Seymour on covering intersecting families by pairs, J. Combinatorial Th. 68 (1994), 317–339.MathSciNetMATHCrossRef
65.
J. Kahn and G. Kalai, A counterexample to Borsuk’s Conjecture, Bull. Amer. Math. Soc. 29 (1993), 60–62.
66.
J. Kahn and M. Kayll, Fractional vs. integral covers in hypergraphs of bounded edge size, J. Combinatorial Th. A 78 (1997), 199–235.
67.
J. Kahn and J.H. Kim, Random matchings in regular graphs, Combinatorica 18 (1998), 201–226.
68.
J. Kahn and P. D. Seymour, A fractional version of the Erdős-Faber-Lovász Conjecture, Combinatorica 12 (1992), 155–160.
69.
J. H. Kim, On Brooks’ Theorem for sparse graphs, Combinatorics, Probability and Computing 4 (1995), 97–132.
70.
J. Komlós, J. Pintz and E. Szemerédi, A lower bound for Heilbronn’s problem, J. London Math. Soc. 25 (1982), 13–24.
71.
A. V. Kostochka, Degree, girth and chromatic number, pp. 679–696 in Combinatorics, Keszthely 1976, A. Hajnal and V. T. Sós Eds., Colloq. Math. Soc. János Bolyai 18, North Holland, 1978.
72.
H. Kunz, Location of the zeros of the partition function for some classical lattice systems, Phys. Lett. (A) (1970), 311–312.
73.
D. G. Larman, in Convexity and Graph Theory (Rosenfeld and Zaks, eds.), Ann. Discrete Math. 20 (1984), 336.
74.
L. Lovász and M.D. Plummer, Matching Theory, North Holland, Amsterdam, 1986.MATH
75.
C.J.H. McDiarmid, On the method of bounded differences, pp. 148–188 in Surveys in Combinatorics 1989, Invited Papers at the 12th British Combinatorial Conference, J. Siemons Ed., Cambridge Univ. Pr., 1989.
76.
J.-C. Meyer, pp. 285–286 in Hypergraph Seminar (Berge and Ray-Chaudhuri, eds.), Springer, Berlin-Heidelberg-New York, 1974.
77.
N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combinatorial Th. (A) 51 (1989), 24–42.
78.
Y. Rabinovich, A. Sinclair and A. Wigderson, Quadratic Dynamical Systems, Proc. 33rd IEEE Symposium on Foundations of Computer Science (1992), 304–313.
79.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, 1958.MATH
80.
V. Rödl, On a packing and covering problem, Europ. J. Combinatorics 5 (1985), 69–78.
81.
A. Ruciński, The behaviour of \(\left ({ n \atop k,,\ldots,,k,n-ik} \right ){c}^{i}/i!\) is asymptotically normal, Discrete Math. 49 (1984), 287–290.
82.
A. Schrijver, Theory of Linear and Integer Programming, Wiley, Chichester, 1986.MATH
83.
P. D. Seymour, Some unsolved problems on one-factorizations of graphs, in Graph Theory and Related Topics (Bondy and Murty, eds.), Academic Press, New York, 1979.
84.
P. D. Seymour, Packing nearly-disjoint sets, Combinatorica 2 (1982), 91–97.
85.
C. E. Shannon, A theorem on coloring the lines of a network, J. Math. Phys. 28 (1949), 148–151.
86.
87.
88.
89.
B. Toft, 75 graph-colouring problems, pp. 9–35 in Graph Colourings (R. Nelson and R.J. Wilson, eds.), Wiley, New York, 1990.
90.
V. G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian), Diskret. Analiz 3 (1964), 25–30.
91.
V. G. Vizing, Some unsolved problems in graph theory (Russian), Uspehi Mat. Nauk. 23 (1968), 117–134. English translation in Russian Math. Surveys 23 (1968), 125–141.
92.
V. G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. Analiz No 29 Metody Diskret. Anal. v Teorii Kodov i Shem (1976), 3–10, 101 (MR58 #16371).
93.
R. M. Wilson, An existence theory for pairwise balanced designs I–III, J. Combinatorial Th. (A) 13 (1972), 220–273, 18 (1975), 71–79.
Metadata
Title
On Some Hypergraph Problems of Paul Erdős and the Asymptotics of Matchings, Covers and Colorings
Author
Jeff Kahn
Copyright Year
2013
Publisher
Springer New York
Book
The Mathematics of Paul Erdős I

Print ISBN: 978-1-4614-7257-5

Electronic ISBN: 978-1-4614-7258-2

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-7258-2_22

Premium Partner

    Image Credits