On the combinatorial problems which I would most like to see solved. (English) Zbl 0486.05001
I was asked to write a paper about the major unsolved problems in combinatorial mathematics. After some thought it seemed better to modify the title to a less pretentious one. Combinatorial mathematics has grown enormously and a genuine survey would have to include not only topics where I have no real competance but also topics about which I never seriously thought, E.G. algorithmic combinatorics, coding theory and matroid theory.
MSC:
| 05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |
| 05Cxx | Graph theory |
| 05Bxx | Designs and configurations |
| 11B75 | Other combinatorial number theory |
| 03E05 | Other combinatorial set theory |
| 00A07 | Problem books |
Keywords:
problemsReferences:
| [1] | M. Ajtai, J. Komlós andE. Szemerédi, On infinite Sidon sequences,European J. Comb., to appear. |
| [2] | K. Appel andW. Haken, Every planar map is four colourable,Illinois J. of Math. 21 (1977) 429–490. · Zbl 0387.05009 |
| [3] | F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression,Proc. Nat. Acad. Sci. USA 32 (1946) 331–332. · Zbl 0060.10302 · doi:10.1073/pnas.32.12.331 |
| [4] | C. Berge,Graphs and Hypergraphs, North Holland Publ. Comp. Amsterdam–London 1973. · Zbl 0254.05101 |
| [5] | B. Bollobás,Extremal Graph Theory, London Math. Soc. Mon. No. 11. 1978. |
| [6] | J. A. Bondy, Reflections on the legitimate deck problem,Lecture Notes in Math.,686, Springer 1977, 1–12 · doi:10.1007/BFb0062511 |
| [7] | J. A. Bondy andP. Erdos, Ramsey numbers for cycles in graphs,J. Comb. Theory 14 (1973) 46–54. · Zbl 0248.05127 · doi:10.1016/S0095-8956(73)80005-X |
| [8] | J. A. Bondy andR. L. Hemminger, Graph reconstruction,J. of Graph Theory 1 (1977), 227–268. · Zbl 0375.05040 · doi:10.1002/jgt.3190010306 |
| [9] | R. C. Bose, E. T. Parker andS. Shrikhande, Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture,Can. J. Math. 12, 189–203. · Zbl 0093.31905 |
| [10] | W. G. Brown, On graphs that do not contain a Thomsen graph,Canad. Math. Bull. 9 (1966) 281–285. · Zbl 0178.27302 · doi:10.4153/CMB-1966-036-2 |
| [11] | W. G. Brown, P. Erdos andV. T. Sós, Some extremal problems onr-graphs,New Directions in the Theory of Graphs (ed. F. Harary), Academic Press 1973, 53–64. |
| [12] | W. G. Brown, P. Erdos andV. T. Sós, On the existence of triangulated spheres in 3-graphs and related questions,Periodica Math. Hung. 3 (1973) 221–228. · Zbl 0269.05111 · doi:10.1007/BF02018585 |
| [13] | R. H. Bruck andH. J. Ryser, The nonexistence of certain projective planes,Canad. J. Math. 1 (1949) 88–93. · Zbl 0037.37502 · doi:10.4153/CJM-1949-009-2 |
| [14] | N. G. de Bruijn andP. Erdos, A colour problem for infinite graphs and a problem in theory of relations,Nederl. Akad. Wetensch. Proc. Ser. A 54 (1951) 371–373. · Zbl 0044.38203 |
| [15] | S. A. Burr, Generalized Ramsey theory for graphs – a survey,Graphs and Combinatorics, Lecture Notes in Math. 406, Springer 1974, 52–75. · Zbl 0293.05122 · doi:10.1007/BFb0066435 |
| [16] | P. A. Catlin, Subgraphs of graphs I,Discrete Math. 10 (1974) 225–233. · Zbl 0289.05122 · doi:10.1016/0012-365X(74)90119-8 |
| [17] | V. Chvátal, Intersection families of edges in hypergraphs having the hereditary property,Hypergraph Seminar, Lecture Notes in Math. 411, Springer 1972, 61–66. · doi:10.1007/BFb0066179 |
| [18] | V. Chvátal, R. L. Graham, H. A. Perold andS. H. Whitesides, Combinatorial designs related to the strong perfect graph conjecture,Discrete Math. 26 (1979) 83–92. · Zbl 0403.05017 · doi:10.1016/0012-365X(79)90114-6 |
| [19] | J. Dénes andA. D. Keedwell,Latin Squares and their applications, Academic Press, New York 1974. · Zbl 0283.05014 |
| [20] | G. Dirac, In abstrakten Graphen vorhandene 4-Graphen und ihre Unterteilungen,Math. Nachrichten 22 (1960) 61–85. · Zbl 0096.17903 · doi:10.1002/mana.19600220107 |
| [21] | P. Erdos, Combinatorial problems in geometry and number theory,to appear. See alsoP. Erdos, On some problems of elementary and combinatorial geometry,Annali di Mat. ser. 4,104 (1975) 99–108. · Zbl 0303.52006 · doi:10.1007/BF02414146 |
| [22] | P. Erdos andS. Fajtlowicz, On the conjecture of Hajós,to appear in Combinatorica. · Zbl 0698.68080 |
| [23] | P. Erdos, A. W. Goodman andL. Pósa, The representation of a graph by set intersection,Canad. J. Math. 18 (1966) 106–112. · Zbl 0137.43202 · doi:10.4153/CJM-1966-014-3 |
| [24] | P. Erdos andA. Hajnal, Unsolved and solved problems in set theory,Proc. Symp. Pure Math. XXIII. Univ. Calif. Berkeley, A.M.S. 1971, 17–48. |
| [25] | P. Erdos andA. Hajnal, On chromatic number of graphs and set systems,Acta Math. Acad. Sci. Hung. 17 (1966) 61–99. · Zbl 0151.33701 · doi:10.1007/BF02020444 |
| [26] | P. Erdos andA. Hajnal, On complete topological subgraphs of certain graphs,Annales Univ. Sci. Budapest 7 (1969) 193–199. |
| [27] | P. Erdos, A. Hajnal andE. C. Milner, A problem on well ordered sets,Acta Math. Acad. Sci. Hung. 20 (1969) 323–329. · Zbl 0193.30803 · doi:10.1007/BF01894901 |
| [28] | P. Erdos, A. Hajnal andS. Shelah, On some general properties of chromatic numbers,Coll. Math. Soc. J. Bolyai 8,Topics in Topology, North-Holland 1972, 243–255. |
| [29] | P. Erdos, A. Hajnal andE. Szemerédi, On almost bipartite large chromatic graphs,to appear in the volume dedicated to the 60th birthday of A. Kotzig. |
| [30] | P. Erdos andI. Kaplansky, The asymptotic number of Latin rectangles,Amer. J. Math. 69 (1946) 230–236. · Zbl 0060.02808 · doi:10.2307/2371834 |
| [31] | P. Erdos andD. Kleitman, Extremal problems among subsets of a set,Discrete Math. 8/3 (1974) 281–294. See alsoG. O. H. Katona, Extremal problems for hypergraphs,Combinatorics (M. Hall and J. H. van Lint, eds.) Math. Centre Amsterdam 1974, 215–244. · Zbl 0281.04002 · doi:10.1016/0012-365X(74)90140-X |
| [32] | P. Erdos andL. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions,Coll. Math. J. Bolyai 10 Infinite and Finite Sets, 1973, 609–617. |
| [33] | P. Erdos, E. C. Milner andR. Rado, Intersection theorems for systems of sets III.Austral. J. Math. 18 (1974) 22–40. · Zbl 0331.04002 · doi:10.1017/S1446788700019091 |
| [34] | P. Erdos andR. Rado, Intersection theorems for systems of sets,J. London Math. Soc. 35 (1960) 85–90. · Zbl 0103.27901 · doi:10.1112/jlms/s1-35.1.85 |
| [35] | P. Erdos andA. Rényi, On the existence of a factor of degree one of a connected random graph,Acta Math. Acad. Sci. Hung. 17 (1966) 359–379. · Zbl 0203.56902 · doi:10.1007/BF01894879 |
| [36] | P. Erdos, A. Rényi andV. T. Sós, On a problem of graph theory,Studia Sci. Math. Hung. 1 (1966) 215–235. |
| [37] | P. Erdos andM. Simonovits, Some extremal problems in graph theory,Comb. Theory and Appl. (P. Erdos et al. eds.)Coll. Math. Soc. J. Bolyai 4 (1969) 377–390. |
| [38] | P. Erdos andM. Simonovits, An extremal graph problem,Acta Math. Acad. Sci. Hung. 22/3–4 (1971) 275–282. · Zbl 0234.05118 · doi:10.1007/BF01896420 |
| [39] | P. Erdos andM. Simonovits, On a valence problem in extremal graph theory,Discrete Math. 5 (1973) 323–334. · Zbl 0268.05121 · doi:10.1016/0012-365X(73)90126-X |
| [40] | P. Erdos andM. Simonovits, On the chromatic number of geometric graphs, to appear inArs Combinatoria. |
| [41] | P. Erdos andE. Szemerédi, Combinatorial properties of systems of sets,J. of Comb. Theory A 24 (1978) 308–313. · Zbl 0383.05002 · doi:10.1016/0097-3165(78)90060-2 |
| [42] | P. Erdos andP. Turán, On some sequences of integers,J. of London Math. Soc. 11 (1936) 341–363. |
| [43] | P. Erdos andP. Turán, On a problem of Sidon in additive number theory and related problems,J. London Math. Soc. 16 (1941) 212–216. · Zbl 0061.07301 · doi:10.1112/jlms/s1-16.4.212 |
| [44] | R. J. Faudree andR. H. Schelp, All Ramsey numbers for cycles in graphs,Discrete Math. 8 (1974) 313–329. · Zbl 0294.05122 · doi:10.1016/0012-365X(74)90151-4 |
| [45] | P. Frankl, On families of finite sets no two of which intersect in a singleton,Bull. Austral. Math. Soc. 17 (1977) 125–134. · Zbl 0385.05003 · doi:10.1017/S0004972700025521 |
| [46] | P. Frankl, An intersection problem for finite sets,Acta Math. Acad. Sci. Hung. 30 (1977) 371–373. · Zbl 0398.05002 · doi:10.1007/BF01896201 |
| [47] | P. Frankl, Extremal problems and coverings of the space,European J. of Comb. 1 (1980),to appear. · Zbl 0463.05043 |
| [48] | H. Fürstenberg, Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions I–III,J. Analyse Math. 31 (1977) 204–256. · Zbl 0347.28016 · doi:10.1007/BF02813304 |
| [49] | H. Fürstenberg andY. Katznelson, An ergodic Szemerédi theorem for commuting transformations,J. Analyse Math. 34 (1978) 275–291. · Zbl 0426.28014 · doi:10.1007/BF02790016 |
| [50] | P. Gács andL. Lovász, Khachian’s Algorithm for linear programming,Math. Progr. Studies, to appear |
| [51] | T. Gallai, On covering of graphs,Theory of Graphs, Proc. Coll. Tihany, Hungary 1968, (P. Erdos and G. Katona, eds.) 231–236. |
| [52] | R. L. Graham, B. Rothschild andJ. Spencer,Ramsey Theory, John Wiley, New York 1980. |
| [53] | H. Hadwiger, Ungelöste Probleme No. 40,Elemente der Math. 16 (1961) 103–104. |
| [54] | H. Hadwiger, Über eine Klassifikation der Streckenkomplexe,Vierte Naturforsch. Ges. Zürich 88 (1943) 133–142. · Zbl 0061.41308 |
| [55] | G. Hajós, Über eine Konstruktion nichtn-färbbarer Graphen,Wiss. Zeitschr. Martin Luther Univ. Halle–Wittenberg A 10 (1961) 116–117. |
| [56] | H. Hanani, The existence and construction of balanced incomplete block designs,Ann. Math. Stat. 32 (1961) 361–386. · Zbl 0107.36102 · doi:10.1214/aoms/1177705047 |
| [57] | G. O. H. Katona,unpublished. |
| [58] | L. M. Kelly andW. Moser, On the number of ordinary lines determined byn points,Canad. J. Math. 10 (1958) 210–219. · Zbl 0081.15103 · doi:10.4153/CJM-1958-024-6 |
| [59] | L. G. Khachiyan, A polynomial algorithm in linear programming (in Russian)Doklady Akademii Nauk SSSR,244, (1979), 1093–1096. · Zbl 0414.90086 |
| [60] | J. Komlós andE. Szemerédi, Limit distribution for the existence of Hamilton cycles in a random graph,Discrete Math., to appear. |
| [61] | T. Kovári, V. T. Sós andP. Turán, On a problem of Zarankiewicz,Coll. Math. 3 (1954) 50–57. · Zbl 0055.00704 |
| [62] | D. G. Larman andC. A. Rogers, The realization of distances within sets in Euclidean space,Mathematica 19 (1972) 1–24. · Zbl 0246.05020 |
| [63] | L. Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Math. 2 (1972) 253–267. · Zbl 0239.05111 · doi:10.1016/0012-365X(72)90006-4 |
| [64] | L. Lovász, |
| [65] | W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen,Math. Annalen 174 (1967) 265–268. · Zbl 0171.22405 · doi:10.1007/BF01364272 |
| [66] | U. S. R. Murty, How many magic configurations are there,Amer. Math. Monthly 1978/9, 1001–1002. |
| [67] | U. S. R. Murty,unpublished. SeeL. Caccetta andR. Häggkvist, On diameter critical graphs,Discrete Math. 28 (1979) 223–229. |
| [68] | J. Paris andL. Harrington, A Mathematical Incompleteness in Peano Arithmetic,Handbook of Math. Logic, North Holland, Amsterdam 1977, 1133–1142. |
| [69] | J. Pelikán, Valency conditions for the existence of certain subgraphs,Theory of Graphs, Proc. Coll. Tihany, Hungary 1968, 251–258. · Zbl 0157.31205 |
| [70] | L. Pósa, Hamiltonian cycles in random graphs,Discrete Math. 14 (1976) 359–364. · Zbl 0322.05127 · doi:10.1016/0012-365X(76)90068-6 |
| [71] | V. Rödl,to appear. |
| [72] | Vera Rosta, On a Ramsey type problem of J. A. Bondy and P. Erdos I–II,J. Comb. Theory B 15 (1973) 94–105, 105–120. · Zbl 0261.05118 · doi:10.1016/0095-8956(73)90035-X |
| [73] | K. F. Roth, On certain sets of integers II,J. of London Math. Soc. 29 (1954) 20–26. · Zbl 0055.27201 · doi:10.1112/jlms/s1-29.1.20 |
| [74] | I. Z. Ruzsa andE. Szemerédi, Triple systems with no six points carrying three triangles,Coll. Math. Soc. J. Bolyai 18 Combinatorics (A. Hajnal and V. T. Sós, eds.) North-Holland 1978, 939–946. |
| [75] | M. Simonovits, Paul Turán*rss influence on graph theory,J. Graph Theory 2 (1977). 102–116. · Zbl 0383.05023 · doi:10.1002/jgt.3190010205 |
| [76] | M. Simonovits, A method for solving extremal problems in graph theory,Theory of Graphs, Proc. Coll. Tihany, Hungary 1966, 279–319. |
| [77] | J. Spencer, Intersection theorems for systems of sets,Canad. Math. Bull. 20 (1977) 249–254. · Zbl 0361.05028 · doi:10.4153/CMB-1977-038-7 |
| [78] | G. Szekeres, On an extremum problem in the plane,Amer. J. Math. 63 (1941) 208–211. · Zbl 0024.13202 · doi:10.2307/2371290 |
| [79] | E. Szemerédi, On sets of integers containing nok elements in arithmetic progression,Acta Arithm. 27 (1975) 199–245. · Zbl 0303.10056 |
| [80] | E. Szemerédi, A. Gyárfás andZs. Tuza, Induced subtrees in graphs of large chromatic number,Discrete Math. 30 (1980) 235–244. · Zbl 0475.05027 · doi:10.1016/0012-365X(80)90230-7 |
| [81] | P. Turán, On an extremal problem in graph theory (in Hungarian)Mat. Fiz. Lapok 48 (1941) 436–452 and On theory of graphs,Coll. Math. 3 (1954) 19–30. |
| [82] | B. L. van der Waerden, Beweis einer Baudetschen Vermutung,Nieuw. Arch. Wisk. 15 (1928) 212–216. · JFM 53.0073.12 |
| [83] | R. M. Wilson, An existence theory for pairwise balanced designs I–II,J. Comb. Theory A 13 (1972) 220–273. · Zbl 0263.05014 · doi:10.1016/0097-3165(72)90028-3 |
| [84] | N. Wormald, A 4-chromatic graph with a special plane drawing,J. Austral. Math. Soc. Ser. A. 28 (1979) 1–8. · Zbl 0418.05026 · doi:10.1017/S1446788700014865 |
| [85] | T. Bang, On matrix functioner som med et numerisk lille deficit viser v. d. Waerdens permanenthypotese,Proc. Scandinavian Congress, Turku 1976 |
| [86] | S. Friedland, A lower bound for the permanent of a doubly stochastic matrix,Ann. Math. 110 (1979), 167–176 · doi:10.2307/1971250 |
| [87] | B. Grünbaum,Arrangements and Spreads, A. M. S., Providence, R. I. 1972 |
| [88] | T. S. Motzkin, The lines and planes connecting the points of a finite set,Trans. A. M. S. 70 (1951), 451–464. · Zbl 0043.14603 · doi:10.1090/S0002-9947-1951-0041447-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
