All Problems

    Ramsey Theory
  1. The Happy Ending problem: forcing convex polygons (Szekeres)
  2. Forcing empty convex polygons
  3. Does the Ramsey limit exist? What is the limit? ($100 / $250)
  4. Constructive Ramsey ($100)
  5. Lower bound for \( r(4, n) \) ($250)
  6. Lower bound for \(r(k, n)\)
  7. Consecutive Ramsey numbers (Burr)
  8. Bounds for growth of \(r(3, n)\) (Sós) (two problems combined)
  9. Linear Ramsey numbers (Burr) ($25)
  10. Cliques are Ramsey-extremal (Graham)
  11. \(r(G)\) is subexponential in sqrt(edges)
  12. \(r(G)\) is bounded by \(r(\chi(G))\) (1)
  13. \(r(G)\) is bounded by \(r(\chi(G))\) (2)
  14. Upper bound for Ramsey on trees (Burr)
  15. Exact Ramsey value for some trees
  16. Upper bound on r(tree, complete multi-partite)
  17. Upper bound for Ramsey number for \(4\)-cycle
  18. Exact values for Ramsey numbers for \(k\)-cycle (Faudree, Rousseau, Schelp)
  19. Exact value for Ramsey number of \(k\)-cycle and star (Burr, Faudree, Rousseau, Schelp)
  20. Upper bound for Ramsey number for the hypercube (Burr)
  21. Multi-color Ramsey number for triangles ($250/$100)
  22. \(r(3, 3, n)\) is much larger than \(r(3, n)\)
  23. Multi-color Ramsey number for triangles grows faster than for other odd cycles (Graham)
  24. Multi-color Ramsey number for even cycles (Graham)
  25. \(3\)-color Ramsey number for \(n\)-cycles (Bondy)
  26. Multi-color Ramsey number for trees (Graham)
  27. Multi-color Ramsey number for complete bipartite graphs (Chung, Graham)
  28. Size Ramsey number for graphs of bounded degree (Beck)
  29. Size Ramsey number for complete balanced bipartite graphs (Faudree, Rousseau, Schelp)
  30. Size Ramsey number for unions of stars (Burr, Faudree, Rousseau, Schelp)
  31. A linear bound on some size Ramsey numbers (Faudree, Rousseau, Schelp)
  32. A linear bound on some size Ramsey numbers for particular graphs (Faudree, Rousseau, Schelp)
  33. A linear bound on some size Ramsey numbers for trees (Faudree, Rousseau, Schelp)
  34. A linear bound on some size Ramsey numbers for odd cycles (Faudree, Rousseau, Schelp)
  35. A linear bound on some size Ramsey numbers for cycles (Faudree, Rousseau, Schelp)
  36. Upper bound on induced Ramsey numbers (Rödl)
  37. Double exponential lower bound for \(3\)-uniform hypergraph Ramsey numbers (Hajnal, Rado) ($500)
  38. Asymptotic behavior of \(t\)-uniform hypergraph Ramsey numbers (Hajnal, Rado)
  39. Asymptotic behavior of generalized Ramsey numbers
  40. Behavior of generalized hypergraph Ramsey numbers ($500)

    41. Extremal Graph Theory
  41. Turán number for complete balanced bipartite graphs (Zarankiewicz, not Erdős)
  42. Lower bound for Turán number for \(K_{4,4}\)
  43. Upper bound for Turán number for bipartite degenerate graphs (Simonovits) ($100)
  44. Lower bound for Turán number for bipartite non-degenerate graphs
  45. Turán number for bipartite graphs is a rational power of n (Simonovits)
  46. Turán number for even cycles (Simonovits)
  47. Turán number for families of graphs behave like Turán number for one of the members (Simonovits)
  48. Asymptotic behavior for joint Turán number for \(3\)- and \(4\)-cycles (Simonovits)
  49. Asymptotic behavior for joint Turán number for consecutive cycles (Simonovits)
  50. Extremal graph avoiding \(3\)- and \(4\)-cycles avoids all odd cycles
  51. Behavior of Turán number for a family of graphs is controlled by a bipartite member
  52. Turán number for cubes (Simonovits)
  53. Turán number for graphs with subgraphs of minimum degree \(> 2\) (Simonovits) ($250/$100)
  54. Number of edges in a graph with small independent sets avoid the octahedron (Hajnal, Sós, Szemerédi)
  55. Subgraphs of the cube without a \(2k\)-cycle ($100)
  56. Number of edges to force all trees (Sós)
  57. The \( (n/2-n/2-n/2) \) conjecture (Füredi, Loebl, Sós)
  58. Making a triangle-free graph bipartite (Faudree, Pach, Spencer)
  59. Largest bipartite subgraph of a triangle free graph
  60. \(2\)-coloring \(K_4\)-free graphs to avoid monochromatic triangles ($100) (Proven by Linyuan Lu in "Explicit construction of small Folkman graphs", 2008)
  61. Forcing triangles with local edge densities (Rousseau)
  62. Graphs covered by triangles (Rothschild)
  63. Edge-partitioning into paths (Gallai)
  64. Forcing large directed paths or independent sets (Rado)
  65. Minimizing the harmonic sum of cycle lengths (Hajnal)
  66. Subgraphs where every pair of edges is in a short cycle (Duke, Rödl) (two problems combined)
  67. Many edges are contained in \(5\)-cycles
  68. Decomposing a complete graph to avoid small odd cycles (Graham)
  69. Existence of Cycles of Order \(2^k\) (Gyárfás)
  70. Estimate the clique transversal number of a graph (Gallai, Tuza)
  71. Upper bound on clique transversal number
  72. Clique transversal number is sublinear for graphs with no small cliques
  73. Diameter of a \(K_r\)-free graph (Pach, Pollack, Tuza)
  74. Linearly many edges force certain cycle lengths ($100)
  75. Unions of bipartite graphs and graphs with bounded degree
  76. A problem on sparse induced subgraphs
  77. Any graph with many large independent sets is almost bipartite
  78. Upper bound for \(rt(n, 4; n/log(n))\)
  79. If \(G\) has no \(5\)-cliques, and any large subset of vertices contains a triangle, then \(G\) is sparse
  80. A graph without induced \(5\)-cycles has large cliques or independent sets

    81. Coloring, Packing, and Covering
  81. Growth of girth in graphs with fixed chromatic number
  82. Counting vertices of a graph with large girth and chromatic number
  83. Finding subgraphs with large girth and chromatic number (Hajnal)
  84. Ratio of chromatic number to clique number
  85. Decomposing graphs into subgraphs with higher total chromatic number (Lovász)
  86. Bipartite graphs with high list-chromatic numbers
  87. If \(G\) is \((a, b)\)-choosable, then \(G\) is \((am, bm)\)-choosable for every positive integer \(m\) (Rubin, Taylor)
  88. Estimate the maximum number of edges for a \(k\)-critical graph on n vertices
  89. Find the exact maximum number of edges for a \(k\)-critical graph on n vertices
  90. Critical graphs with large minimum degree
  91. Vertex critical graphs with many extra edges
  92. Bounding the strong chromatic index (Nešetřil)
  93. Many disjoint monochromatic triangles (Faudree, Ordman) (two problems combined)
  94. Edge-coloring to avoid large monochromatic stars (Faudree, Rousseau, Schelp)
  95. Anti-Ramsey graphs (Burr, Graham, Sós)
  96. Anti-Ramsey problem for balanced colorings
  97. Bounding the acyclic chromatic number for graphs of bounded degree
  98. Any graph of large chromatic number has an odd cycle spanning a subgraph of large chromatic number (Hajnal)
  99. Any graph of large chromatic number has many edge-disjoint cycles on one subset of vertices (Hajnal)
  100. Covering by \(4\)-cycles
  101. Maximum chromatic number of the complement graph of graphs with fixed \(h(G)\) (Faudree)
  102. Ratio of clique partition number to clique covering number (Faudree, Ordman)
  103. Difference of clique partition number to clique covering number
  104. Maximum product of clique partition numbers for complementary graphs
  105. The ascending subgraph decomposition problem (Alavi, Boals, Chartrand, Oellermann)

    106. Random Graphs and Graph Enumeration
  106. At what density is the chromatic number of a random graph r?
  107. Find the range of expected chromatic numbers for a random graph
  108. Random graphs contain cubes (Bollobás)
  109. Large independent sets in all large subgraphs of a random graph (Bollobás)
  110. Covering a random graph with triangles (Spencer)
  111. Avoiding anti-monotone graph properties in a random graph (Suen, Winkler)
  112. Number of induced \(G\)-subgraphs in a given graph
  113. Adding an edge to an extremal \(4\)-cycle-free graph gives two \(4\)-cycles (Siminovits)
  114. Number of triangles in a multi-partite graph with large minimum degree (Bollobás, Szemerédi)
  115. Number of graphs with a forbidden subgraph (Kleitman, Rothschild)
  116. Regular induced subgraphs (Fajtlowicz, Staton)
  117. Graphs with induced subgraphs of any number of edges (McKay) ($100)
  118. Count the ways to add a K4 (Tuza)
  119. Number of triangle-free graphs
  120. Number of pentagons in a triangle free graph
  121. A conjecture of \(3\)-colored triangles in the complete graph (Sós)

    122. Hypergraphs
  122. Turán's conjecture: hypergraph Turán numbers: \(t_r(n, k)\) (Turán, not Erdős) ($1000)
  123. Exact values for \(t_3(n, 4) \) (Turán, not Erdős) ($500)
  124. Asymptotics of \(t_3(n, 5)\) (Turán, not Erdős)
  125. Adding an edge to extremal \(K^{(3)}_k\)-free graph gives two copies of \(K^{(3)}_k\)
  126. Adding an edge to extremal \(K^{(3)}_k\)-free graph gives a \(K^{(3)}_{k+1}\) missing an edge
  127. Avoiding triple systems (Brown, Sós)
  128. Lower bound for hypergraph Turán numbers
  129. Turán densities are rational
  130. Unavoidable stars (Rado)
  131. Special case: unavoidable \(3\)-stars
  132. Unavoidable stars of an n-set (Szemerédi)
  133. Weak \(\Delta\)-systems (Milner, Rado)
  134. Weak \(\Delta\)-systems of an n-set (Szemerédi)
  135. Erdős-Faber-Lovász conjecture: a simple hypergraph on \(n\) vertices has chromatic index at most \(n\) (Faber, Lovász)
  136. Minimum number of edges for a \(n\)-graph to not have Property B (that is: to not be \(2\)-colorable)
  137. Minimum number of edges for a \(3\)-chromatic \(4\)-graph
  138. Conjecture on \(3\)-chromatic hypergraphs (Lovász)
  139. Conjecture on minimum \(3\)-chromatic hypergraphs (Lovász)
  140. Maximum edges in a \(3\)-chromatic \(r\)-clique (Lovász)
  141. Maximum vertices in a \(3\)-chromatic \(r\)-clique (Lovász)
  142. \(3\)-chromatic cliques have edges with large intersection (Lovász) ($100)
  143. Number of sizes of edge intersections in a \(3\)-chromatic \(r\)-graph (Lovász)
  144. Jumping densities for \(3\)-hypergraphs ($500)
  145. Conjecture on covering a hypergraph (Lovász)
  146. Stronger conjecture on covering a hypergraph
  147. Maximum unavoidable hypergraphs (Chung)
  148. Unavoidable stars with fixed intersection size (Duke)
  149. Hypergraph decomposition (Chung, Graham)
  150. Characterize hypergraphs with maximum/minimum product of point and line covering numbers (Chung, Graham)
  151. Covering complete \(3\)-graphs (Tuza)
  152. \(r\)-sets with common union and intersection (Füredi)
  153. Finding small global vertex covers for r-graphs with small local vertex covers (Fon der Flaass, Kostochka, Tuza)
  154. A Ramsey-type conjecture for \(2\)-colorings of complete \(3\)-graphs
  155. A Ramsey-Turán upper bound for \(3\)-graphs
  156. A Ramsey-Turán lower bound for \(3\)-graphs (Sós)

    157. Infinite Graphs
  157. Menger's theorem for infinite graphs
  158. Ordinal Ramsey: For which \(\alpha\) does \(\omega^{\alpha} → (\omega^{\alpha}, 3)^{2}\)? (Hajnal) ($1000)
  159. Ordinal Ramsey: If \(\alpha → (\alpha, 3)^{2},\) then \(\alpha → (\alpha, 4)^{2}\) (Hajnal)
  160. Ordinal Ramsey: \(\omega_{1} → (\alpha, 4)^{3}\) for \(\alpha < \omega_{1}\)
  161. Ordinal Ramsey: \(\omega_{1}^{2} → (\omega_{1}^{2}, 3)^{2}\)
  162. Ordinal Ramsey: \(\omega_{3} → (\omega_{2} + 2)^{3}_{\omega}\)
  163. Almost-bipartite graphs with infinite chromatic number (Hajnal, Szemerédi) ($250)
  164. Another problem on almost-bipartite graphs with infinite chromatic number
  165. Uncountable-chromatic graphs have common \(4\)-chromatic subgraphs (Hajnal)
  166. Infinite \(K_{4}\)-free graphs are the union of triangle-free countable graphs (Hajnal) ($250)
  167. The harmonic sums of odd-cycle lengths diverges for graphs of infinite chromatic number (Hajnal)
  168. There is an uncountable-chromatic graph \(G\) so that the size of the smallest \(n\)-chromatic subgraph grows arbitrarily slowly (Hajnal, Szemerédi)
  169. Infinite graphs have infinite paths or arbitrary independent sets (Hajnal, Milner)
  170. Down-up matchings in infinite graphs (Larson)