Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). Hindman has proved the conjecture for $n<10$. Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large $n$.
In [Er97d] Erdős asks how large $\chi(G)$ can be if instead of asking for the copies of $K_n$ to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge.
Conjectured by Bollobás and Erdős [BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao [FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most \[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]
See also [615].
In [Er92b] Erdős asks, more generally, if a graph on $(2k+1)n$ vertices in which every odd cycle has size $\geq 2k+1$ can be made bipartite by deleting at most $n^2$ edges.
In [Er92b] and [Er97f] Erdős asks more generally: if $r\geq 5$ is odd and a graph has $rn$ vertices and the smallest odd cycle has size $r$ then is the number of cycles of size $r$ at most $n^{r}$?
The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.
See also [65].
A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.
He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.
Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős wrote [Er87] that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.
David Penman has observed that this is certainly true if the graph has uncountable chromatic number, since by a result of Erdős and Hajnal [ErHa66] such a graph must contain arbitrarily large finite complete bipartite graphs (see also Theorem 3.17 of Reiher [Re24]).
Zach Hunter has observed that this follows from the work of Liu and Montgomery [LiMo20]: if $G$ has infinite chromatic number then, for infinitely many $r$, it must contain some finite connected subgraph $G_r$ with chromatic number $r$ (via the de Bruijn-Erdős theorem [dBEr51]). Each $G_r$ contains some subgraph $H_r$ with minimum degree at least $r-1$, and hence via Theorem 1.1 of [LiMo20] there exists some $\ell_r\geq r^{1-o(1)}$ such that $H_r$ contains a cycle of every even length in $[(\log \ell)^8,\ell]$.
See also [64].
This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove a much stronger result: if the average degree of $G$ is sufficiently large then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.
An infinite tree with minimum degree $3$ shows that the answer is trivially false for infinite graphs.
See also the entry in the graphs problem collection.
See also [57].
Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although he conjectured that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.
Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.
Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.
See also [922] and the entry in the graphs problem collection.
Rödl [Ro82] has proved this for hypergraphs, and also proved there is such a graph (with chromatic number $\aleph_0$) if $f(n)=\epsilon n$ for any fixed constant $\epsilon>0$.
It is open even for $f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$ (see [111]).
The answer is yes, proved by Gruslys and Letzter [GrLe20].
In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c>1/24$.
A shorter and simpler proof of an upper bound of the strength $4-c$ for some constant $c>0$ (and a generalisation to the case of more than two colours) was given by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba [BBCGHMST24].
This problem is #3 in Ramsey Theory in the graphs problem collection.
In [Er69b] Erdős asks for even a construction whose largest clique or independent set has size $o(n^{1/2})$, which is now known.
Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size \[\geq 2^{(\log\log n)^{C}}\] for some constant $C>0$. Li [Li23b] has recently improved this to \[\geq (\log n)^{C}\] for some constant $C>0$.
This problem is #4 in Ramsey Theory in the graphs problem collection.
Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?
Estimate $f_c(n)$. In particular, is it true that $f_c(n)>n^{\epsilon}$ for some $\epsilon>0$? Or $f_c(n)\gg \log n$?
Edwards (unpublished) and Khadziivanov and Nikiforov [KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see [905]).
Fox and Loh [FoLo12] proved that \[f_c(n) \leq n^{O(1/\log\log n)}\] for all $c<1/4$, disproving the first conjecture of Erdős.
The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.
See also [600] and the entry in the graphs problem collection.
A split graph is one where the vertices can be split into a clique and an independent set. Every split graph is chordal. Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.
Prove that $f(n)=o(2^n)$.
Prove that $f(n)/2^{n/2}\to \infty$.
One can also ask about the existence and value of $\lim f(n)^{1/n}$.
A similar question can be asked for other even cycles.
See also [666] and the entry in the graphs problem collection.
Even stronger, is there some $c>0$ such that, for all large $k$, $R(G)>cR(k)$ for every graph $G$ with chromatic number $\chi(G)=k$?
Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.
This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.
In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]
See also the entry in the graphs problem collection and [740] for the infinitary version.
A theorem of de Bruijn and Erdős [dBEr51] implies that, if $G$ has infinite chromatic number, then $G$ has a finite subgraph of chromatic number $n$ for every $n\geq 1$.
In [Er95d] Erdős suggests this is true, although such an $F$ must grow faster than the $k$-fold iterated exponential function for any $k$.
What is the behaviour of $h_G(n)$? Is it true that $h_G(n)/n\to \infty$ for every graph $G$ with chromatic number $\aleph_1$?
On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In [Er81] Erdős conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.
See also [74].
See also the entry in the graphs problem collection - on this site the problem replaces transitive tournament with directed path, but Zach Hunter and Raphael Steiner have a simple argument that proves, for this alternative definition, that $k(n,m)=(n-1)(m-1)$.
Disproved by Janzer [Ja21] who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]
See also [146] and [147] and the entry in the graphs problem collection.
Keevash and Sudakov [KeSu06] have proved this under the additional assumption that $G$ has at most $n^2/12$ edges.
The obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), provided $N \leq C^n$ for some absolute constant $C>1$. This implies $R(n;3,2) \geq C^{n}$, contradicting the conjecture.
Perhaps Erdős had a different problem in mind, but it is not clear what that might be. It would presumably be one where the natural probabilistic argument would deliver a bound like $C^{\sqrt{n}}$ as Erdős and Gyárfás claim to have achieved via the probabilistic method.
How large can the chromatic number and clique number of this graph be? In particular, can the chromatic number be infinite?
See also [213].
What is the order of growth of $f(n)$? Does $f(n)/\sqrt{n}\to \infty$?
Simonovits observed that the subsets of $[3m-1]$ of size $m$, two sets joined by edge if and only if they are disjoint, forms a triangle-free graph of diameter $2$ which is regular of degree $\binom{2m-1}{m}$. This construction proves that \[f(n) \leq n^{(1+o(1))\frac{2}{3H(1/3)}}=n^{0.7182\cdots},\] where $H(x)$ is the binary entropy function. In [Er97b] Erdős encouraged the reader to try and find a better construction.
In this note Alon provides a simple construction that proves $f(n) \ll \sqrt{n\log n}$: take a triangle-free graph with independence number $\ll \sqrt{n\log n}$ (the existence of which is the lower bound in [165]) and add edges until it has diameter $2$; the neighbourhood of any set is an independent set and hence the maximum degree is still $\ll \sqrt{n\log n}$.
Hanson and Seyffarth [HaSe84] proved that $f(n)\leq (\sqrt{2}+o(1))\sqrt{n}$ using a Cayley graph on $\mathbb{Z}/n\mathbb{Z}$, with the generating set given by some symmetric complete sum-free set of size $\sim \sqrt{n}$. An alternative construction of such a complete sum-free set was given by Haviv and Levy [HaLe18].
Füredi and Seress [FuSe94] proved that $f(n)\leq (\frac{2}{\sqrt{3}}+o(1))\sqrt{n}$.
The precise asymptotics of $f(n)$ are unknown; Alon believes that the truth is $f(n)\sim \sqrt{n}$.
Can $G$ be made into a triangle-free graph with diameter $2$ by adding at most $\delta n^2$ edges?
In this note Alon solves this problem in a strong form, in particular proving that a triangle-free graph on $n$ vertices with maximum degree $<n^{1/2-\epsilon}$ can be made into a triangle-free graph with diameter $2$ by adding at most $O(n^{2-\epsilon})$ edges.
See also [618].
The weaker conjecture that there exists some $c>0$ such that $(2-c)\Delta^2$ sets suffice was proved by Molloy and Reed [MoRe97], who proved that $1.998\Delta^2$ sets suffice (for $\Delta$ sufficiently large). This was improved to $1.93\Delta^2$ by Bruhn and Joos [BrJo18] and to $1.835\Delta^2$ by Bonamy, Perrett, and Postle [BPP22]. The best bound currently available is \[1.772\Delta^2,\] proved by Hurley, de Joannis de Verclos, and Kang [HJK22].
Erdős and Nešetřil also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved independently by Chung-Trotter and Gyárfás-Tuza.
Does $c(n)^{1/n}\to \alpha$ for some $\alpha <2$?
Solved by Bradač [Br24], who proved that $\alpha=\lim c(n)^{1/n}$ exists and \[\alpha \leq 2^{H(1/3)}=1.8899\cdots,\] where $H(\cdot)$ is the binary entropy function. Seymour's construction proves that $\alpha\geq 3^{1/3}=1.442\cdots$. Bradač conjectures that this lower bound is the true value of $\alpha$.
This problem is #17 in Ramsey Theory in the graphs problem collection.
This problem is #9 in Ramsey Theory in the graphs problem collection. See also [800].
See also [544].
This problem is #5 in Ramsey Theory in the graphs problem collection.
Is it true that, for every $\mathcal{F}$, there exists $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]
This is trivially true if $\mathcal{F}$ does not contain any bipartite graphs, since by the Erdős-Stone theorem if $H\in\mathcal{F}$ has minimal chromatic number $r\geq 2$ then \[\mathrm{ex}(n;H)=\mathrm{ex}(n;\mathcal{F})=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}.\] Erdős and Simonovits observe that this is false for infinite families $\mathcal{F}$, e.g. the family of all cycles.
See also [575] and the entry in the graphs problem collection.
A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.
See also [483].
The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.
Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.
See also [583].
Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.
Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for such a construction and \$25 for a proof that no such construction is possible.
Bradač and Christoph [BrCh24] have proved the answer is no: if $f(n)$ is the maximum number of unique subgraphs in a graph on $n$ vertices then \[f(n) = o\left(\frac{2^{\binom{n}{2}}}{n!}\right).\] (Quantitatively the $o(1)$ in their argument can be taken to be $O(\frac{\log\log\log n}{\log\log n})$.)
See also [712] for the general case.
Solved in the affirmative by Pokrovskiy, Versteegen, and Williams [PVW24].
They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620]) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle.
See also [579] and the entry in the graphs problem collection.
This problem is #10 in Ramsey Theory in the graphs problem collection.
This problem is #11 in Ramsey Theory in the graphs problem collection.
Implied by [548].
This problem is #14 in Ramsey Theory in the graphs problem collection.
It can be easily proved by induction that every graph on $n$ vertices with at least $n(k-1)+1$ edges contains every tree on $k+1$ vertices.
Brandt and Dobson [BrDo96] have proved this for graphs of girth at least $5$. Wang, Li, and Liu [WLL00] have proved this for graphs whose complements have girth at least $5$. Saclé and Woznik [SaWo97] have proved this for graphs which contain no cycles of length $4$. Yi and Li [YiLi04] have proved this for graphs whose complements contain no cycles of length $4$.
This is false: Norin, Sun, and Zhao [NSZ16] have proved that if $T$ is the union of two stars on $k$ and $2k$ vertices, with an edge joining the centre of the two stars, then $R(T)\geq (4.2-o(1))k$. The best upper bound for the Ramsey number for this tree is $R(T)\leq 4.27492k+1$, obtained by Dubó and Stein [DuSt24].
This problem is #15 in Ramsey Theory in the graphs problem collection.
This problem is #16 in Ramsey Theory in the graphs problem collection.
This identity was proved for $k>n^2-2$ by Bondy and Erdős [BoEr73]. Nikiforov [Ni05] extended this to $k\geq 4n+2$.
Keevash, Long, and Skokan [KLS21] have proved this identity when $k\geq C\frac{\log n}{\log\log n}$ for some constant $C$, thus establishing the conjecture for sufficiently large $n$.
Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.
Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.
If $G$ has $n$ vertices and maximum degree $d$ then prove that \[\hat{R}(G)\ll_d n.\]
This was disproved for $d=3$ by Rödl and Szemerédi [RoSz00], who constructed a graph on $n$ vertices with maximum degree $3$ such that \[\hat{R}(G)\gg n(\log n)^{c}\] for some absolute constant $c>0$. Tikhomirov [Ti22b] has improved this to \[\hat{R}(G)\gg n\exp(c\sqrt{\log n}).\] It is an interesting question how large $\hat{R}(G)$ can be if $G$ has maximum degree $3$. Kohayakawa, Rödl, Schacht, and Szemerédi [KRSS11] proved an upper bound of $\leq n^{5/3+o(1)}$ and Conlon, Nenadov, and Trujić [CNT22] proved $\ll n^{8/5}$. The best known upper bound of $\leq n^{3/2+o(1)}$ is due to Draganić and Petrova [DrPe22].
Determine \[\hat{R}(K_{n,n}),\] where $K_{n,n}$ is the complete bipartite graph with $n$ vertices in each component.
Conlon, Fox, and Wigderson [CFW23] have proved that, for any $s\leq t$, \[\hat{R}(K_{s,t})\gg s^{2-\frac{s}{t}}t2^s,\] and prove that when $t\gg s\log s$ we have $\hat{R}(K_{s,t})\asymp s^2t2^s$. They conjecture that this should hold for all $s\leq t$, and so in particular we should have $\hat{R}(K_{n,n})\asymp n^32^n$.
Let $F_1$ and $F_2$ be the union of stars. More precisely, let $F_1=\cup_{i\leq s} K_{1,n_i}$ and $F_2=\cup_{j\leq t} K_{1,m_j}$. Prove that \[\hat{R}(F_1,F_2) = \sum_{2\leq k\leq s+2}\max\{n_i+m_j-1 : i+j=k\}.\]
Prove that, for $r\geq 3$, \[\log_{r-1} R_r(n) \asymp_r n,\] where $\log_{r-1}$ denotes the $(r-1)$-fold iterated logarithm. That is, does $R_r(n)$ grow like \[2^{2^{\cdots n}}\] where the tower of exponentials has height $r-1$?
Prove that, for every $0\leq \alpha\leq 1/2$, \[F(n,\alpha)\sim c_\alpha\log n\] for some constant $c_\alpha$ depending only on $\alpha$.
Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.
See also [161].
Is there some constant $c>0$ such that \[R_3(n) \geq 2^{2^{cn}}?\]
Is it true that \[R^*(G) \leq 2^{O(n)}\] for any graph $G$ on $n$ vertices?
Rödl [Ro73] proved this when $G$ is bipartite. Kohayakawa, Prömel, and Rödl [KPR98] have proved that \[R^*(G) < 2^{O(n(\log n)^2)}.\] An alternative (and more explicit) proof was given by Fox and Sudakov [FoSu08]. Conlon, Fox, and Sudakov [CFS12] have improved this to \[R^*(G) < 2^{O(n\log n)}.\]
The graph $H_5$ can also be described as $K_4^*$, obtained from $K_4$ by subdividing one edge. ($K_4$ itself is not Ramsey size linear, since $R(4,n)\gg n^{3-o(1)}$, see [166].) Bradać, Gishboliner, and Sudakov [BGS23] have shown that every subdivision of $K_4$ on at least $6$ vertices is Ramsey size linear, and also that $R(H_5,H) \ll m$ whenever $H$ is a bipartite graph with $m$ edges and no isolated vertices.
A rational $\alpha\in [1,2]$ for which the first problem holds is known as a Turán exponent. Known Turán exponents are:
See also [713] and the entry in the graphs problem collection.
Erdős [Er64c] and Bondy and Simonovits [BoSi74] showed that \[\mathrm{ex}(n;C_{2k})\ll kn^{1+\frac{1}{k}}.\]
Benson [Be66] has proved this conjecture for $k=3$ and $k=5$. Lazebnik, Ustimenko, and Woldar [LUW95] have shown that, for arbitrary $k\geq 3$, \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{2}{3k-3+\nu}},\] where $\nu=0$ if $k$ is odd and $\nu=1$ if $k$ is even. See [LUW99] for further history and references.
See also [765] and the entry in the graphs problem collection.
See also [574] and the entry in the graphs problem collection.
See also [573] and the entry in the graphs problem collection.
Is it true that, for every $\mathcal{F}$, if there is a bipartite graph in $\mathcal{F}$ then there exists some bipartite $G\in\mathcal{F}$ such that \[\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?\]
See also [180] and the entry in the graphs problem collection.
A theorem of Sudakov and Tomon [SuTo22] implies \[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\] Janzer and Sudakov [JaSu22b] have improved this to \[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\] See also the entry in the graphs problem collection.
See also [533] and the entry in the graphs problem collection.
Komlós and Sós conjectured the generalisation that if at least $n/2$ vertices have degree at least $k$ then $G$ contains any tree with $k$ vertices.
Frankl and Rödl [FrRo86] proved $N\leq 7\times 10^{11}$, which Spencer [Sp88] improved to $\leq 3\times 10^{9}$. This resolved the challenge of Erdős [Er75d] to find such a graph with less than $10^{10}$ vertices.
Lu [Lu07] proved $N\leq 9697$ vertices. The current record is due to Dudek and Rödl [DuRo08] who proved $N\leq 941$ vertices. For further information we refer to a paper of Radziszowski and Xu [RaXu07], who prove that $N\geq 19$ and speculate that $N\leq 127$.
See also the entry in the graphs problem collection and [924] for the general case.
Chung [Ch78] proved that every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint trees. Pyber [Py96] has shown that every connected graph on $n$ vertices can be covered by at mst $n/2+O(n^{3/4})$ paths.
If we drop the edge-disjoint condition then this conjecture was proved by Fan [Fa02].
Hajos [Lo68] has conjectured that if $G$ has all degrees even then $G$ can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint cycles.
See also [184] and the entry in the graphs problem collection.
Fox and Sudakov [FoSu08b] have proved the second statement when $\delta >n^{-1/5}$.
Chakraborti, Janzer, Methuku, and Montgomery [CJMM24] have shown that such a graph can have at most $n(\log n)^{O(1)}$ many edges. Indeed, they prove that there exists a constant $C>0$ such that for any $k\geq 2$ there is a $c_k$ such that if a graph has $n$ vertices and at least $c_kn(\log n)^{C}$ many edges then it contains $k$ pairwise edge-disjoint cycles with the same vertex set.
Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595].
This was proved by Aharoni and Berger [AhBe09].
In [Er82e] Erdős offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.
Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.
Erdős and Faudree observed that every graph with $2n$ vertices and at least $n^2+1$ edges has a triangle whose vertices are joined to at least $n+2$ vertices.
Chung [Ch97] asked whether $f(n)\to \infty$ as $n\to \infty$. Day and Johnson [DaJo17] proved this is true, and that \[f(n)\geq 2^{c\sqrt{\log n}}\] for some constant $c>0$. The trivial upper bound is $2^n$.
Girão and Hunter [GiHu24] have proved that \[f(n) \ll \frac{2^n}{n^{1-o(1)}}.\]
Estimate $\tau(G)$. In particular, is it true that if $G$ has $n$ vertices then \[\tau(G) \leq n-c\sqrt{n\log n}\] for some absolute constant $c>0$?
This would be best possible, since there exist triangle-free graphs with all independent sets of size $O(\sqrt{n\log n})$, which follows from the lower bound for $R(3,k)$ by Kim [Ki95] (see [165]).
Indeed, Erdős, Gallai, and Tuza speculate that if $f(n)$ is the largest $k$ such that every triangle-free graph on $n$ vertices contains an independent set on $f(n)$ vertices, then $\tau(G)\leq n-f(n)$.
In [Er94] and [Er99] Erdős asks for a weaker upper bound $\tau(G) \leq n-\omega(n)\sqrt{n}$ for any $\omega(n)\to \infty$.
See also [611], this entry and and this entry in the graphs problem collection.
Is it true that if all maximal cliques in $G$ have at least $cn$ vertices then $\tau(G)=o_c(n)$?
Similarly, estimate for $c>0$ the minimal $k_c(n)$ such that if every maximal clique in $G$ has at least $k_c(n)$ vertices then $\tau(G)<(1-c)n$.
See also [610] and the entry in the graphs problem collection.
Resolved by Fox, Loh, and Zhao [FLZ15] who showed that the answer is no; in fact they prove that \[\mathrm{rt}(n; 4, ne^{-f(n)})\geq (1/8-o(1))n^2\] whenever $f(n) =o(\sqrt{\log n/\log\log n})$.
See also [22] and the entry in the graphs problem collection.
Determine the best possible $t$ such that, if $G$ is an $r$-uniform hypergraph $G$ where every subgraph $G'$ on at most $3r-3$ vertices has $\tau(G')\leq 1$, we have $\tau(G)\leq t$.
Erdős, Gyárfás, and Ruszinkó [EGR98] proved that if $G$ has no isolated vertices and maximum degree $O(1)$ then $h_2(G)\ll n\log n$.
Alon has observed this problem is essentially identical to [134], and his solution in this note also solves this problem in the affirmative.
See also [619].
Is it true that there exists a constant $c>0$ such that if $G$ is a connected graph on $n$ vertices then $h_4(G)<(1-c)n$?
If we omit the condition that the graph must remain triangle-free then Alon, Gyárfás, and Ruszinkó [AGR00] have proved that adding $n/2$ edges always suffices to obtain diameter at most $4$.
It is now known that $f(n)=n^{1/2+o(1)}$. Bollobás and Hind [BoHi91] proved \[n^{1/2} \ll f(n) \ll n^{7/10+o(1)}.\] Krivelevich [Kr94] improved this to \[n^{1/2}(\log\log n)^{1/2} \ll f(n) \ll n^{2/3}(\log n)^{1/3}.\] Wolfovitz [Wo13] proved \[f(n) \ll n^{1/2}(\log n)^{120}.\]
Is it true that \[\alpha_1(G)+\tau_1(G) \leq \frac{n^2}{4}?\]
If $G$ is a random graph with $n$ vertices and each edge included independently with probability $1/2$ then is it true that almost surely \[\chi(G) - \zeta(G) \to \infty\] as $n\to \infty$?
It is known that almost surely \[\frac{n}{2\log_2n}\leq \zeta(G)\leq \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.\] (The final upper bound is due to Bollobás [Bo88]. The first inequality follows from the fact that almost surely $G$ has clique number and independence number $< 2\log_2n$.)
Heckel [He24] and, independently, Steiner [St24b] have shown that it is not the case that $\chi(G)-\zeta(G)$ is bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$ with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that, with high probability, \[\chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}.\] Heckel [He24c] further proved that, for any $\epsilon>0$, we have \[\chi(G) -\zeta(G) \geq n^{1-\epsilon}\] for roughly $95\%$ of all $n$.
Conversely, if $h^{(m)}(n)$ is the maximal chromatic number of a graph on $n$ vertices with girth $>m$ then does \[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\] exist, and what is its value?
Erdős [Er59b] proved that \[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\gg \frac{1}{m}\] and, for odd $m$, \[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\leq \frac{2}{m+1},\] and conjectured this is sharp. He had no good guess for the value of the limit for even $m$, other that it should lie in $[\frac{2}{m+2},\frac{2}{m}]$, but could not prove this even for $m=4$.
Erdős [Er67c] proved that \[f(n) \asymp \frac{n}{(\log n)^2}\] and that the limit in question, if it exists, must be in \[(\log 2)^2\cdot [1/4,1].\]
Balogh, Kostochka, Prince, and Stiebitz [BKPS09] have proved the full conjecture for quasi-line graphs and graphs with independence number $2$.
Determine the minimal number of vertices $n(k)$ of a bipartite graph $G$ such that $\chi_L(G)>k$.
Erdős, Rubin, and Taylor [ERT80] proved $n(2)=6$ and Hanson, MacGillivray, and Toft [HMT96] proved $n(3)=14$ and \[n(k) \leq kn(k-2)+2^k.\]
Does every planar bipartite graph $G$ have $\chi_L(G)\leq 3$?
Does every planar graph $G$ have $\chi_L(G)\leq 5$? Is this best possible?
If $G$ is $(a,b)$-choosable then $G$ is $(am,bm)$-choosable for every integer $m\geq 1$.
This is false: Dvořák, Hu, and Sereni [DHS19] construct a graph which is $(4,1)$-choosable but not $(8,2)$-choosable.
This was proved by Kwan and Sudakov [KwSu21].
This was proved by Bukh and Sudakov [BuSu07].
Jenssen, Keevash, Long, and Yepremyan [JKLY20] have proved that there must exist an induced subgraph which contains $\gg n^{2/3}$ distinct degrees (with no restriction on the number of vertices).
Is it true that for every infinite cardinal $\aleph$ there is a graph $G$ of which every finite subgraph is in $S$ and if the edges of $G$ are coloured with $\aleph$ many colours then there is a monochromatic triangle.
This problem was solved completely by Keevash and Sudakov [KeSu04], who provd that the corret threshold is $\lfloor n^2/4\rfloor$ for all $n\geq 7$, is $\binom{n}{2}$ for $n\leq 5$, and is $10$ for $n=6$.
This was resolved in the negative by Janzer, Steiner, and Sudakov [JSS24] - in fact, this fails even at $k=2$. Janzer, Steiner, and Sudakov proved that there exists a constant $c>0$ such that, for all large $n$, there exists a graph on $n$ vertices with chromatic number \[\geq c\frac{\log\log n}{\log\log \log n}\] which contains no $4$-regular subgraph.
Füredi proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. More generally, Füredi proved that \[f(n;t) \ll \binom{n}{t-1}.\]
The answer to this problem is no: Chung [Ch92] and Brouwer, Dejter, and Thomassen [BDT93] constructed an edge-partition of $Q_n$ into four subgraphs, each containing no $C_6$.
See also [86].
When $q=1$ this corresponds exactly to the classical Ramsey problem, and hence for example \[\frac{1}{p-1}\leq c(p,1) \leq \frac{2}{p+1}.\] It is easy to see that if $q=\binom{p-1}{2}+1$ then $c(p,q)=1$. Erdős, Faudree, Rousseau, and Schelp have shown that $c(p,\binom{p-1}{2})\leq 1/2$.
Estimate the chromatic number $\chi(G_n)$. Does it grow exponentially in $n$? Does \[\lim_{n\to \infty}\chi(G_n)^{1/n}\] exist?
Is there some $k$ such that if $G$ has girth $\geq k$ (i.e. $G$ contains no cycles of length $<k$) then $\chi(G)\leq 3$?
Wormald [Wo79] has constructed a unit distance graph with $\chi(G)=4$ and girth $5$, with $6448$ vertices. O'Donnell [OD94] has constructed a unit distance graph with $\chi(G)=4$ and girth $4$, with $56$ vertices. Chilakamarri [Ch95] has constructed an infinite family of unit distance graphs with $\chi(G)=4$ and girth $4$, the smallest of which has $47$ vertices.
Estimate $L(r)$. In particular, is it true that $L(r)\leq r^{O(1)}$?
See also [500] for the case $r=3$ and $k=4$.
See also [571].
The answer is yes, proved by Tashkinov [Ta82].
In [Er81] Erdős asks whether the same is true for any $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges.
The answer is yes, proved by Fox, Lee, and Sudakov [FLS13].
Mader [Ma67] proved that $\geq 2^{\binom{r}{2}}n$ edges suffices.
The answer is yes, proved independently by Komlós and Szemerédi [KoSz96] and Bollobás and Thomason [BoTh96].
Is every $r$-hypergraph $G$ on $n$ vertices the union of at most $\mathrm{ex}_{r}(n;K_{r+1}^r)$ many copies of $K_r^r$ and $K_{r+1}^r$, no two of which share a $K_r^r$?
Is it true that, if $P_n$ is the path of length $n$, then \[\hat{R}(P_n)/n\to \infty\] and \[\hat{R}(P_n)/n^2 \to 0?\] Is it true that, if $C_n$ is the cycle with $n$ edges, then \[\hat{R}(C_n) =o(n^2)?\]
More generally, Erdős asks to characterise families $\mathcal{F}_\alpha$ of finite graphs such that there is a graph of chromatic number $\aleph_\alpha$ all of whose finite subgraphs are in $\mathcal{F}_\alpha$.
More generally, Erdős and Hajnal asked must there exist (for every cardinal $\mathfrak{m}$ and integer $r$) some $f_r(\mathfrak{m})$ such that every graph with chromatic number $\geq f_r(\mathfrak{m})$ contains a subgraph with chromatic number $\mathfrak{m}$ with no odd cycle of length $\leq r$?
Erdős [Er95d] claimed that even the $r=3$ case of this is open: must every graph with sufficiently large chromatic number contain a triangle free graph with chromatic number $\mathfrak{m}$?
In [Er81] Erdős also asks the same question but with girth (i.e. the subgraph does not contain any cycle at all of length $\leq C$).
This is true (for sufficiently large $n$) and was proved by Füredi [Fu92].
Gyárfás and Lehel [GyLe78] proved that this holds if all but at most $2$ of the trees are stars, or if all the trees are stars or paths. Fishburn [Fi83] proved this for $n\leq 9$. Bollobás [Bo83] proved that the smallest $\lfloor n/\sqrt{2}\rfloor$ many trees can always be packed greedily into $K_n$.
Joos, Kim, Kühn, and Osthus [JKKO19] proved that this conjecture holds when the trees have bounded maximum degree. Allen, Böttcher, Clemens, Hladky, Piguet, and Taraz [ABCHPT21] proved that this conjecture holds when all the trees have maximum degree $\leq c\frac{n}{\log n}$ for some constant $c>0$.
Janzer and Montgomery [JaMo24] have proved that there exists some $c>0$ such that the largest $cn$ trees can be packed into $K_n$.
Is it true that $f_k(n)\to \infty$ as $n\to \infty$? In particular, is it true that $f_4(n) \gg \log n$?
This conjecture was disproved by Rödl and Tuza [RoTu85], who proved that in fact $f_k(n)=\binom{k-1}{2}$ (for all sufficiently large $n$).
This is true. Pósa [Po76] proved that almost surely a random graph with $\geq Cn\log n$ edges is Hamiltonian for some large constant $C$, and Komlós and Szemerédi [KoSz83] proved that \[\geq \frac{1}{2}n\log n+\frac{1}{2}n\log\log n+w(n)n\] edges suffices, for any function $w$ which $\to \infty$ as $n\to \infty$.
The answer is yes, proved by Sudakov and Verstraëte [SuVe08], who in fact proved that under the assumption of average degree $k$ and girth $>2s$ there are at least $\gg k^s$ many consecutive even integers which are cycle lengths in $G$.
Does there exist some constant $c>0$ such that \[\chi_L(G)+\chi_L(G^c)> n^{1/2+c}\] for every graph $G$ on $n$ vertices (where $G^c$ is the complement of $G$)?
The answer is no: Alon [Al92] proved that, for every $n$, there exists a graph $G$ on $n$ vertices such that \[\chi_L(G)+\chi_L(G^c)\ll (n\log n)^{1/2},\] where the implied constant is absolute.
Determine $z(n)$ for small values of $z(n)$. In particular is it true that $z(12)=4$?
In fact there do exist such graphs - Bhavik Mehta found computationally that there is exactly one (up to taking the complement) graph on $12$ vertices such that both $G$ and its complement are $K_4$-free with chromatic number $\geq 5$. This graph was explicitly checked to have cochromatic number $4$, and hence this proves that indeed $z(12)=4$.
The values of $z(n)$ are now known for $1\leq n\leq 19$: \[1,1,2,2,3,3,3,3,4,4,4,4,5,5,5,6,6,6,6.\] (The only significant difficulty here is proving $z(12)=4$ - the others follow from easy inductive arguments and the facts that $R(3)=6$ and $R(4)=18$.) It is unknown whether $z(20)=6$ or $7$.
Gimbel [Gi86] has shown that $z(n) \asymp \frac{n}{\log n}$.
Let $z(S_n)$ be the maximum value of $\zeta(G)$ over all graphs $G$ which can be embedded on $S_n$, the orientable surface of genus $n$. Determine the growth rate of $z(S_n)$.
If $G$ is a graph with chromatic number $\chi(G)=m$ then must $G$ contain a subgraph $H$ with \[\zeta(H) \gg \frac{m}{\log m}?\]
The answer is yes, proved by Alon, Krivelevich, and Sudakov [AKS97].
Must a graph with large chromatic number have large dichromatic number? Must a graph with large cochromatic number contain a graph with large dichromatic number?
Is it true that if $G$ has no $K_5$ and $\zeta(G)\geq 4$ then $\chi(G) \leq \zeta(G)+2$?
This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$, $\zeta(G)=4$, and $\chi(G)=7$.
See also [572].
Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$. For fixed $k$ and large $n$ is $f(n;k,l)$ a strictly monotone function of $l$?
The conjectured equality was proved for $n\geq 3k+3$ by Jiang [Ji04].
Curiously, in [Er69b] Erdős mentions this problem, but states that his conjectured equality for $g_k(n)$ was disproved (for general $k$) by Lewin, citing oral communication. Perhaps Lewin only disproved this for small $n$, or perhaps Lewin's disproof was simply incorrect.
Is it true that, if $\epsilon>0$ and $n$ is sufficiently large, whenever $m\leq (2-\epsilon)2^{n/2}$ the graph $G_\mathcal{F}$ has $<2^{n}$ many edges?
Is it true that if $G_{\mathcal{F}}$ has $\geq cm^2$ edges then $m\ll_c 2^{n/2}$?
Is it true that, for any $\epsilon>0$, there exists some $\delta>0$ such that if there are $>m^{2-\delta}$ edges then $m<(2+\epsilon)^{n/2}$?
For the first question we need to take $\epsilon>0$ since since if $n$ is even and $m=2^{n/2+1}$ one could take $\mathcal{F}$ to be all subsets of $\{1,\ldots,n/2\}$ together with $\{1,\ldots,n/2\}$ union all subsets of $\{n/2+1,\ldots,n\}$, which produces $2^{n}$ edges.
The third question was answered in the affirmative by Alon and Frankl [AlFr85], who proved that, for every $k\geq 1$, if $m=2^{(\frac{1}{k+1}+\delta)n}$ for some $\delta>0$ then the number of edges is \[< \left(1-\frac{1}{k}\right)\binom{m}{2}+O(m^{2-\Omega_k(\delta^{k+1})}).\] They also answer the second question in the negative, noting that if $\mathcal{F}$ is the family of sets which either intersect $\{n/2+1,\ldots,n\}$ in at most $1$ element or intersect $\{1,\ldots,n/2\}$ in at least $n/2-1$ elements then $m \gg n2^{n/2}$ and there are at least $2^{-5}\binom{m}{2}$ edges.
Finally, an affirmative answer to the first question follows from Theorem 1.4 and Corollary 1.5 of Alon, Das, Glebov, and Sudakov [ADGS15].
Does Bob have a winning strategy for $n\geq 3$? (Erdős believed the answer is yes.)
If we change the game so that Bob colours two edges after each edge that Alice colours, but now require Bob's largest clique to be strictly larger than Alice's, then does Bob have a winning strategy for $n>3$?
Finally, consider the game when Alice wins if the maximum degree of the red subgraph is larger than the maximum degree of the blue subgraph. Who wins?
Similarly, for the third game they prove that the set of $n$ for which Bob wins has density at least $2/3$, and prove the stronger statement that if Alice wins at $n$ then Bob wins at $n+1,n+2$.
Estimate $f(d)$. In particular is it true that $f(d)=o(d^2)$?
Resolved by Alon, McDiarmid, and Reed [AMR91] who showed \[\frac{d^{4/3}}{(\log d)^{1/3}}\ll f(d) \ll d^{4/3}.\]
Is it true that $\chi_L(G)=o(n)$ for almost all graphs on $n$ vertices?
The answer is yes: Alon [Al92] proved that in fact the random graph on $n$ vertices with edge probability $1/2$ has \[\chi_L(G) \ll \frac{\log\log n}{\log n}n\] almost surely. Alon, Krivelevich, and Sudakov [AKS99] improved this to \[\chi_L(G) \asymp \frac{n}{\log n}\] almost surely.
Is it true that for every $m\geq 1$, if $n$ is sufficiently large, any graph on $n$ vertices with $\geq n\log_2n$ edges contains a $O(1)$-balanced subgraph with $m$ vertices and $\gg m\log m$ edges (where the implied constants are absolute)?
Alon [Al08] proved this is actually false: for every $D>1$ and $n>10^5$ there is a graph $G$ with $\leq 2n$ vertices and $\geq 2n\log(2n)$ edges such that if $H$ is a $D$-balanced subgraph then $H$ has $\ll m(\sqrt{\log m}+\log D)$ many edges.
Estimate $f(n)$. In particular, is it true that $f((\log n)^2,n) \geq n^{1/2-o(1)}$? Is it true that $f((\log n)^3,n)\gg (\log n)^3$?
See also [805].
In particular, is there such a graph for $g(n)=(\log n)^3$?
Alon, Bucić, and Sudakov [ABS21] construct such a graph with \[g(n)\leq 2^{2^{(\log\log n)^{1/2+o(1)}}}.\] See also [804].
Is it true that, if $G$ is a random graph on $n$ vertices with edge probability $1/2$, then \[\tau(G)=n-\alpha(G)\] almost surely?
This strong conjecture was disproved by Alon, Ruzsa, and Solymosi [ARS20], who constructed (for arbitrarily large $n$) a set of integers $A$ with $\lvert A\rvert=n$ and a graph $G$ with $\gg n^{5/3-o(1)}$ many edges such that \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \ll \lvert A\rvert^{4/3+o(1)}.\] Alon, Ruzsa, and Solymosi do prove, however, that if $A$ has size $n$ and $G$ has $m$ edges then \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \gg m^{3/2}n^{-7/4}.\]
Is it true that \[F_k(n)\sim n^2/8?\]
See also [810].
See also [809].
If $d_G(n)$ exists then determine the best possible value of $d_G(n)$.
The Kürschák competition in Hungary in 1986 asked students to prove that $d_{K_3}(n)$ exists. Kostochka proved that $d_{K_3}(n)=n/4$ is the best possible. Tuza proved that \[d_{C_4}(n) \leq \left(\frac{1}{4}-c\right)n\] for some constant $c>0$. Brightwell and Trotter proved that \[d_{C_6}(n) > (1-o(1))\frac{n}{6}.\]
Bucić and Sudakov [BuSu23] have proved \[h(n) \gg n^{5/12-o(1)}.\]
Such graphs are called degree $3$ critical. This conjecture was disproved by Narins, Pokrovskiy, and Szabó [NPS17], who proved that there are arbitrarily large such graphs with no cycle of length $23$.
It remains open whether this question has an affirmative answer if we restrict to even $k$.
This was disproved by Alon [Al85], who proved, for example, that there exists some absolute constant $C>0$ such that if $r\geq C$ and $k\geq Cr$ then there exists an $r$-uniform hypergraph with chromatic number $\geq k$ with at most \[\leq (7/8)^r\binom{(r-1)(k-1)+1}{r}\] many edges.
In general, Alon gave an upper bound for the minimal number of edges using Turán numbers. Using known bounds for Turán numbers then suffices to disprove this conjecture for all $r\geq 4$. The validity of this conjecture for $r=3$ remains open.
If $m(r,k)$ denotes the minimal number of edges of any $r$-uniform hypergraph with chromatic number $>k$ then Akolzin and Shabanov [AkSh16] have proved \[\frac{r}{\log r}k^r \ll m(r,k) \ll (r^3\log r) k^r,\] where the implied constants are absolute. Cherkashin and Petrov [ChPe20] have proved that, for fixed $r$, $m(r,k)/k^r$ converges to some limit as $k\to \infty$.
This was solved by Erdős and Lovász [ErLo75], who proved in particular that there is a vertex contained in at least \[\frac{2^{r-1}}{4r}\] many edges.
They do not specify what is meant by $3$-critical. One definition in the literature is: a hypergraph is $3$-critical if there is a set of $3$ vertices which intersects every edge, but no such set of size $2$, and yet for any edge $e$ there is a pair of vertices which intersects every edge except $e$. Raphael Steiner observes that a $3$-critical hypergraph in this sense has bounded size, so this problem would be a finite computation, and perhaps is not what they meant.
An alternative definition is that a hypergraph is $3$-critical if it has chromatic number $3$, but its chromatic number becomes $2$ after deleting any edge or vertex.
This is equivalent to asking whether there exists $k>2$ such that the chromatic number of the Johnson graph $J(2k,k)$ is $k+1$ (it is always at least $k+1$ and at most $2k$). The chromatic numbers listed at this website show that this is false for $3\leq k\leq 8$.
Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.
What is $A_3$?
Is it true that if $\lvert A\rvert >\frac{2}{3}n$ then $G(A)$ contains all odd cycles of length $\leq \frac{n}{3}+1$?
Is it true that, for every $\ell\geq 1$, if $n$ is sufficiently large and $\lvert A\rvert>\frac{2}{3}n$ then $G(A)$ must contain a complete $(1,\ell,\ell)$ triparite graph on $2\ell+1$ vertices?
Is there a function $f$ such that $f(x)/x\to \infty$ as $x\to \infty$ such that, for all large $C$, if $G$ is a graph with $n$ vertices and $e\geq Cn$ edges then \[\hat{R}(G) > f(C) e?\]
Bollobás proved this when $m=4$ - in fact he showed that every graph with $n$ vertices and $2n-1$ edges contains two points joined by $4$ edge-disjoint paths.
Is it true that \[f_k(n) \gg_k n^2?\] Is it true that \[f_6(n)\sim n^2/4?\] More generally, is it true that, for $k\geq 6$, \[f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2?\]
Erdős [Er69b] observed that Dirac's construction generalises to show that, if $3\mid k$, there are infinitely many values of $n$ (those of the shape $mk/3$ where $m$ is odd) such that \[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{k/3}\right)n^2 + n.\]
Toft [To70] proved that $f_k(n)\gg_k n^2$ for $k\geq 4$.
Constructions of Stiebitz [St87] show that, for $k\geq 6$, there exist infinitely many values of $n$ such that \[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor+\delta_k}\right)n^2\] where $\delta_k=0$ if $k\equiv 0\pmod{3}$, $\delta_k=1/7$ if $k\equiv 1\pmod{3}$, and $\delta_k\equiv 24/69$ if $k\equiv 2\pmod{3}$, which disproves Erdős' conjectured asympotic for $k\not\equiv 0\pmod{3}$.
Stiebitz also proved the general upper bound \[f_k(n) < \mathrm{ex}(n;K_{k-1})\sim \frac{1}{2}\left(1-\frac{1}{k-2}\right)n^2\] for large $n$. Luo, Ma, and Yang [LMY23] have improved this upper bound to \[f_k(n) \leq \frac{1}{2}\left(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1)\right)n^2\]
Is there a graph with $\aleph_{\omega+1}$ vertices and chromatic number $\aleph_1$ such that every subgraph on $\aleph_\omega$ vertices has chromatic number $\aleph_0$?
What if instead we ask for $G$ to have chromatic number $\aleph_1$?
Erdős and Hajnal showed this does not generalise to higher cardinals - they (see [Er69b]) constructed a set on $\omega_1^2$ with chromatic number $\aleph_1$ such that every strictly smaller subgraph has chromatic number $\leq \aleph_0$ as follows: the vertices of $G$ are the pairs $(x_\alpha,y_\beta)$ for $1\leq \alpha,\beta <\omega_1$, ordered lexicographically. We connect $(x_{\alpha_1},y_{\beta_1})$ and $(x_{\alpha_2},y_{\beta_2})$ if and only if $\alpha_1<\alpha_2$ and $\beta_1<\beta_2$.
A similar construction produces a graph on $\omega_2^2$ with chromatic number $\aleph_2$ such that every smaller subgraph has chromatic number $\leq \aleph_1$.
Is it true that, for $k\geq 4$, \[g_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^c}\] for some constant $c>0$?
The lower bound $R(4,m) \gg m^3/(\log m)^4$ of Mattheus and Verstraete [MaVe23] (see [166]) implies \[g_4(n) \gg \frac{n^{2/3}}{(\log n)^{4/3}}.\] In general it is known (see [BoKe10]) that \[R(k,m)\gg (\log m)^{-O_k(1)}m^{\frac{k+1}{2}}\] which implies \[g_k(n) \gg \frac{n^{1-\frac{2}{k+1}}}{(\log n)^{c_k}}.\]
Since each $H_k$ is 2-degenerate this is a special case of [146].
This was disproved by Spencer [Sp71], who proved that in fact \[g(n) > n-\log_2 n-O(1).\]
See also [775].
Estimate $h_t(d)$.
It is easy to see that $h_t(d)\leq 2d^t$ always and $h_1(d)=d+1$.
Erdős and Nešetřil and Bermond, Bond, Paoli, and Peyrat [BBPP83] independently conjectured that $h_2(d) \leq \tfrac{5}{4}d^2+1$, with equality for even $d$. This was proved by Chung, Gyárfás, Tuza, and Trotter [CGTT90].
Cambie, Cames van Batenburg, de Joannis de Verclos, and Kang [CCJK22] conjectured that \[h_3(d) \leq d^3-d^2+d+2,\] with equality if and only if $d=p^k+1$ for some prime power $p^k$, and proved that $h_3(3)=23$. They also conjecture that, for all $t\geq 3$, $h_t(d)\geq (1-o(1))d^t$ for infinitely many $d$ and $h_t(d)\leq (1+o(1))d^t$ for all $d$ (where the $o(1)$ term $\to 0$ as $d\to \infty$).
The same authors prove that, if $t$ is large, then there are infinitely many $d$ such that $h_t(d) \geq 0.629^td^t$, and that for all $t\geq 1$ we have \[h_t(d) \leq \tfrac{3}{2}d^t+1.\]