Turán's tetrahedron problem
Determine the largest fraction of triples on n points with no 4-set covered by all its triples; Turán conjectured 5/9.
问题
开放问题和研究问题，每个都是一个 git 仓库：很多来自精选合集，并注明出处。路线是任何人都能开启或接续的分支；检验通过后，结果才算数。
符合的问题
Making a triangle-free graph bipartite
Show that any triangle-free graph on 5n vertices becomes bipartite after deleting n² edges, or find one that needs more.
Gyárfás's tree packing conjecture
Show that any trees T_2, …, T_n with T_k on k vertices can be packed edge-disjointly into the complete graph K_n.
Doubly exponential growth of 3-uniform Ramsey numbers
Show that the 2-colour Ramsey number of triples, R_3(n), grows doubly exponentially in n; the best lower bound is only 2^{cn²}.
An asymptotic formula for the Ramsey number R(3,k)
Find the constant c in R(3,k) ~ c·k²/log k; it is now known to lie between 1/2 and 1.
Explicit Ramsey graphs
Construct explicit graphs on n vertices with no clique or independent set of size c·log n, matching Erdős's random graphs.
Sparse halves in triangle-free graphs
Show that every triangle-free graph on n vertices has ⌊n/2⌋ vertices spanning at most n²/50 edges, or find a counterexample.
The Erdős matching conjecture
Determine the largest r-uniform hypergraph on n vertices with no k disjoint edges; Erdős conjectured one of two simple families wins.
The Erdős–Hajnal conjecture
Show that graphs avoiding a fixed induced subgraph H always contain a clique or independent set of size n^{c(H)}.
Cycles of length a power of two (the Erdős–Gyárfás conjecture)
Show that every finite graph with minimum degree 3 has a cycle of length 4, 8, 16 or another power of two, or find a counterexample.
The exponential growth rate of Ramsey numbers
Find lim R(k)^{1/k} for the diagonal Ramsey numbers, or even prove that the limit exists; it lies between √2 and 3.8.
The chromatic number of the plane
Decide whether 6 or 7 colours are needed to colour the plane so that points at distance 1 always get different colours.
Four-cycle-free subgraphs of the hypercube
Show that a subgraph of the n-cube with no 4-cycle has at most about half of the cube's edges; the best bound is 0.60318.
Rational exponents for bipartite Turán numbers
Decide whether every bipartite graph G has ex(n;G) ~ c·n^α for some α in [1,2), and whether α must be rational.