Top 10 Erdős Problems

By Thomas Bloom on 16 April 2026

While Erdős generated a huge number of problems, they are not all equally significant and important. I have, unfortunately, seen some mathematicians grow dismissive of Erdős problems recently, perhaps because they have seen reports of AI solving problems on this site that turned out to be quite simple, and wrongly generalised this to assume that all problems posed by Erdős are amusing novelties, of the level of olympiad problems.

This couldn't be further from the truth - within number theory and combinatorics especially, the questions that Erdős posed have been hugely influential, and led to the development of many important techniques and ideas in the quest for a solution. In this blog post I will assemble a personal 'top 10' list of some candidates for the 'most important' Erdős problems (both solved and unsolved).

Naturally this is very subjective (and probably will change even for myself day to day), and others are welcome to post in the comments their own candidates. Since choosing just 10 problems was already hard enough, I have not attempted to further order them, and will present them in the numerical order which they appear on this site.

[3] and [139] - Sets without arithmetic progressions

How large can a set of integers A⊂N$A\subset \mathbb{N}$ be if it does not contain k$k$ integers in arithmetic progression? (That is, a,a+d,…,a+(k−1)d$a,a+d,\dots ,a+(k-1)d$ for some d≠0$d\ne 0$.) This question, perhaps first considered in the literature by Erdős and Turán [ErTu36], is the most important question in additive combinatorics. It is a very natural question; arithmetic progressions are maybe the simplest objects one can define, and yet their study has led to the invention of a huge amount of deep and important mathematics.

The first significant conjecture Erdős posed, with Turán in [ErTu36], was [139], that any set with no k$k$-term arithmetic progression must have density 0$0$. Since at the time the best constructions they knew of were very sparse, growing like |A∩[1,N]|≈N1−c$|A\cap [1,N]|\approx N^{1-c}$ for some constant c>0$c>0$, this seemed almost certainly true. Yet it was 17 years before Roth [Ro53] proved the first non-trivial case of this when k=3$k=3$. Roth's proof used an important variation of the circle method, adapting it to yield results for arbitrary sets of positive density (compared to previous applications which focused on specific sets such as the primes or powers).

Roth tried for many years, unsuccessfully, to extend his proof to longer progressions, but the resolution of [139] was achieved by Szemerédi [Sz75] in 1975 using a very different, purely combinatorial, argument. One of the most useful by-products of Szemerédi's proof was the Szemerédi Regularity Lemma, an indispensable modern tool in graph theory. Since then there have been many different proofs of Szemerédi's theorem (most notably using ergodic theory, by Furstenberg [Fu81], and using a higher-order generalisation of Fourier analysis, by Gowers [Go01]). Tao has called Szemerédi's theorem a 'Rosetta stone', highlighting the links between disparate areas of mathematics.

Yet despite the huge amount of work done on [139], our knowledge of the bounds for how a set without k$k$-term arithmetic progressions can grow is still quite poor, especially for k≥4$k\ge 4$. If rk(N)$r_k(N)$ is the maximal size of a subset of {1,…,N}$\{1,\dots ,N\}$ without a k$k$-term arithmetic progression (so that [139] is that rk(N)=o(N)$r_k(N)=o(N)$) then our best lower bounds have the shapefor some constant ck>0$c_k>0$. (This was proved by Behrend [Be46] for k=3$k=3$ and extended for all k≥4$k\ge 4$ by Rankin [Ra60].) When k=3$k=3$ we have an upper bound of the same kind of shape, thanks to Kelley and Meka [KeMe23], but for k=4$k=4$ we only know r4(N)≪N/(logN)c$r_4(N)\ll N/(\log N{)}^c$ for some small c>0$c>0$, a result of Green and Tao [GrTa17], and for k≥5$k\ge 5$ we do not even have a bound of this strength, despite a recent breakthrough of Leng, Sah, and Sawhney [LSS24].

The conjecture [3], for which Erdős offered $5000, is often posed as asking whether ∑n∈A1n=∞$\sum _{n\in A}\frac{1}{n}=\mathrm{\infty }$ implies A$A$ contains arbitrarily long arithmetic progressions. This is roughly equivalent to an estimate of the strength rk(N)≤N/(logN)1+o(1)$r_k(N)\le N/(\log N{)}^{1+o(1)}$ - and hence still out of reach even for k=4$k=4$. Erdős was most likely motivated to make this specific threshold a conjecture because it would imply that the primes contain arbitrarily long arithmetic progressions - now a theorem of Green and Tao [GrTa08] (see [219]), which used some of the machinery mentioned above developed in connection with Szemerédi's theorem combined with number theoretic input about the distribution of primes. Erdős' conjecture [3] posits that one does not need any special information about the primes here: they contain long arithmetic progressions simply because there are a lot of them.

Compared to the lower bound mentioned above, the rk(N)≤N/(logN)1+o(1)$r_k(N)\le N/(\log N{)}^{1+o(1)}$ bound is likely still far from the truth, so even after a resolution of [3], there is still likely a long way to go before we have a complete understanding of the question that Erdős and Turán asked 90 years ago.

[4] - Large gaps between primes

Mathematicians have been interested in the distribution of prime numbers long before Erdős, and there are many questions one can ask. The prime number theorem, proved independently by Hadamard and de la Vallée Poussin in 1896, states that the n$n$th prime is asymptotically equal to pn∼nlogn$p_n\sim n\log n$. Equivalently, in the interval [1,x]$[1,x]$ there are ∼x/logx$\sim x/\log x$ many prime numbers. This is an excellent 'first order' approximation to the distribution of primes, describing, on average, how many we expect to find.

Yet as soon as we move away from average behaviour to 'worst-case' behaviour, we encounter some of the most intractable problems in number theory. For example, the prime number theorem implies that the average gap between two consecutive prime numbers, both of scale ≈x$\approx x$, is ≈logx$\approx \log x$. But this is only the average behaviour; what about the extremal behaviour? If we ask how small they can get, the infamous twin prime conjecture suggests that the gap between consecutive primes can, infinitely often, be as small as 2$2$.

How large can the gap between consecutive primes get? Since the average gap →∞$\to \mathrm{\infty }$ it is wrong to ask for an absolute constant, so we ask instead whether there is some function f(n)$f(n)$, which →∞$\to \mathrm{\infty }$ as n→∞$n\to \mathrm{\infty }$, such that there exist infinitely many pairs of consecutive primes pn,pn+1$p_n,p_{n+1}$ such that pn+1−pn≥f(n)logn$p_{n+1}-p_n\ge f(n)\log n$. This was proved by Westzynthius [We31] - but how quickly should f(n)$f(n)$ grow? After an improvement by Erdős [Er35c], Rankin [Ra38] proved that one can take(This does go to infinity, but not to the naked eye.) This bound seems very artificial and arbitrary, and yet Erdős realised that it was a natural limit of these methods, and therefore offered one of his largest ever prizes, $10000, for any meaningful improvement over this (i.e. proving that one can take the implicit constant arbitrarily large).

Erdős' belief in the difficulty of this problem was well-founded - it was over 60 years since he asked this question till it was solved by Maynard [Ma16] and Ford, Green, Konyagin, and Tao [FGKT16] - their combined efforts [FGKMT18] yieldimproving over Rankin's bound by logloglogn$\log \log \log n$.

As with [3], the particular form of [4] is a great example of Erdős' knack for asking the right questions - he did not pose the obvious challenge of proving the best possible bounds, but rather located the nearest significant threshold for the techniques as he understood them, and gave this as a specific problem.

As with the previous problem, even though [4] has been solved, this is still woefully short of what we believe to be true: the best upper bound we have is that f(n)≪n0.525+o(1)$f(n)\ll n^{0.525+o(1)}$ (a result of Baker, Harman, and Pintz [BHP01]), and even assuming the Riemann Hypothesis this can only be improved to f(n)≤n1/2+o(1)$f(n)\le n^{1/2+o(1)}$.

Yet the likely truth, using a heuristic of Cramér that the primes are distributed as a random sequence (modulo the obvious congruence restrictions), is that f(n)≍logn$f(n)\asymp \log n$.

[20] - Sunflower conjecture

We now move from number theory to pure combinatorics. Let A1,…,At$A_1,\dots ,A_t$ be a collection of finite sets, all of size n$n$. Can we find three of these sets which are pairwise disjoint? Obviously not, no matter how large t$t$ is, since all these sets may contain some fixed element.

Erdős and Rado [ErRa60] considered the next best thing: what if we want to find, not necessarily three sets which are pairwise disjoint, but three sets which become disjoint after the removal of some common 'core' set, say B$B$. This problem has been given the evocative name of the 'sunflower problem', viewing B$B$ as the core of the sunflower and Ai∖B$A_i\mathrm{\setminus }B$ as the (disjoint) petals.

Erdős and Rado gave an elegant inductive argument that shows, if t$t$ is large enough depending on n$n$, then we are guaranteed to find such a sunflower of 3$3$ sets. Let f(n)$f(n)$ be the smallest t$t$ which guarantees this. Their proof gave f(n)≤2nn!$f(n)\le 2^{n}n!$ - this grows worse than exponentially in n$n$, more like exponentially in nlogn$n\log n$.

Problem [20], for which Erdős offered $1000, asks whether this can be improved to f(n)≤Cn$f(n)\le C^n$ for some constant C$C$. Again, despite receiving a lot of attention, the Erdős-Rado bound of f(n)≤2O(nlogn)$f(n)\le 2^{O(n\log n)}$ was not improved until 60 years later, when Alweiss, Lovett, Wu, and Zhang [ALWZ20] provedThe sunflower problem is, in my opinion, one of the most elegant questions in combinatorics, involving nothing more than finite sets and a simple intersection property, and yet despite the attention it has received we lack a complete understanding. Amusingly, even Erdős himself was surprised that this seemed so intractable, writing in [Er81] that 'I really do not see why this question is so difficult'.

Perhaps it is not; perhaps there is a completely different approach to this question that resolves it cleanly and swiftly. I suspect that once we have found whatever this missing idea is it will prove to be a lasting and significant part of our toolkit for many other combinatorial questions.

[28] - Erdős-Turán conjecture on additive bases

One of Erdős' favourite objects of study were additive bases: sets of positive integers A⊂N$A\subset \mathbb{N}$ that are enough to generate all (sufficiently large) integers in just some bounded number of sums - in other words, N∖(A+⋯+A)$\mathbb{N}\mathrm{\setminus }(A+\cdots +A)$ is finite, where we take some fixed finite number of sums.

Even the case of two sums is interesting: from now on, by an additive basis, we just mean a set A$A$ such that A+A$A+A$ contains all large (positive) integers. There are many examples of such a set - a trivial one is to take A$A$ to be the set of all odd numbers together with 2$2$, for example. Let 1A∗1A(n)$1_A\ast 1_A(n)$ count the number of representations n=a1+a2$n=a_1+a_2$ where a1,a2∈A$a_1,a_2\in A$. The additive basis property is equivalent to 1A∗1A(n)>0$1_A\ast 1_A(n)>0$ for all large n$n$. In the odd numbers union 2$2$ example, this representation function grows very quickly, like 1A∗1A(n)≫n$1_A\ast 1_A(n)\gg n$ for all even n$n$.

Sidon asked Erdős how efficient an additive basis could be - in other words, can 1A∗1A(n)$1_A\ast 1_A(n)$ grow very slowly, and yet always be >0$>0$? Erdős [Er56] proved, by a random construction, that there does exist an efficient basis, in which 1A∗1A(n)≪logn$1_A\ast 1_A(n)\ll \log n$. (It was open until very recent work of Jain, Pham, Sawhney, and Zakharov [JPSZ24] whether there is a non-random construction of an efficient additive basis - see [29].)

Erdős returned to this question many times, and it is generally believed that this logarithmic growth is the best possible. Yet [28], a conjecture of Erdős and Turán, remains open: this asks whether there is an additive basis A$A$ such that 1A∗1A(n)≪1$1_A\ast 1_A(n)\ll 1$ for all n$n$.

For example, could there exist a set A$A$ such that every large integer can be written as a1+a2$a_1+a_2$ in at least one, yet always at most 100$100$, different ways?

The answer is surely no, yet disproving even this very strong behaviour remains out of reach. Once again, even after this problem is resolved, there may still be many difficult questions remaining about the possible growth of 1A∗1A(n)$1_A\ast 1_A(n)$.

[52] - Sum-product problem

Another central problem in additive combinatorics. There are many problems in this family, but the original conjecture [52] (often attributed to Erdős and Szemerédi in the literature, who did have the first paper [ErSz83] on this type of problem, but the question appears to have first been asked by Erdős in 1977 [Er77c]) remains the most attractive form.

Let A⊂Z$A\subset \mathbb{Z}$ be a finite set of integers. The sum set A+A$A+A$ and product set AA$AA$ are defined as the set of all pairwise sums and products respectively from A$A$. The trivial bounds are |A|≪|A+A|,|AA|≪|A|2$|A|\ll |A+A|,|AA|\ll |A{|}^2$. It is easy to find examples where the lower bounds are achieved: for an arithmetic progression, for example, we have |A+A|≍|A|$|A+A|\asymp |A|$, while for a geometric progression |AA|≍|A|$|AA|\asymp |A|$. What about the upper bounds? Again, it is easy to see that |A+A|≍|A|2$|A+A|\asymp |A{|}^2$ when A$A$ is a geometric progression. When A$A$ is an arithmetic progression the calculation is a little less trivial (see the multiplication table problem), but we have nearly maximal behaviour |AA|=|A|2−o(1)$|AA|=|A{|}^{2-o(1)}$.

So the examples with |A+A|$|A+A|$ small actually have |AA|$|AA|$ nearly maximal, and vice versa. Is it always the case that at least one of |A+A|$|A+A|$ and |AA|$|AA|$ is nearly maximal? The conjecture [52] is yes:Like many of the great conjectures of number theory, this problem is asking something quite fundamental about the relationship between addition and multiplication, and heuristically the idea is that additive and multiplicative structure 'repel' each other. Out of the many instances of this heuristic, I think this one, about completely arbitrary finite sets of integers, is one of the purest and most appealing.

Maybe at first sight it seems like it should be straightforward to get some kind of bound, but it is non-trivial to get any non-trivial bound of the shapefor some constant c>1$c>1$. This was done by Erdős and Szemerédi [ErSz83], and there have been a number of ingenious arguments since, improving the value of the constant c$c$. Particularly noteworthy is the argument of Solymosi [So09] which achieves c=4/3$c=4/3$ by a beautiful geometric argument. There have been improvements since, most recently by Cushman [Cu25], but the best known value is still only slightly above 4/3$4/3$.

Who knows what other clever ideas await - I still would not be surprised if there was some other elegant geometric insight that could give a relatively short proof of c=3/2$c=3/2$, but establishing the full conjecture of c=2$c=2$ would likely involve some deep number theoretic input. (Maybe surprisingly, assuming other grand conjectures in number theory such as the Riemann Hypothesis or ABC conjecture doesn't seem to help with this problem at all.)

[61] - Erdős-Hajnal conjecture

A stable set of vertices in a graph is one which is either a complete graph or an independent set - in other words, either all possible edges are present, or none of them are. The Erdős-Szekeres bound for Ramsey numbers says that every graph on n$n$ vertices contains a stable set on ≫logn$\gg \log n$ vertices. This is, in general, the best possible: a random graph, in which every edge is present independently with probability 1/2$1/2$, has no stable set larger than O(logn)$O(\log n)$.

So this ≍logn$\asymp \log n$ bound cannot be improved for an arbitrary graph, because the graph might behave like a random one. But what if we had some additional information that said that the graph does not look like a random one? Can we improve the bound for the size of the largest stable set? There are many possible ways to say that a graph does not look random, but one of the most important is that it does not contain some fixed graph as an induced subgraph, since random graphs contain lots of copies of any particular fixed small graph with high probability.

This leads to [61], the Erdős-Hajnal conjecture: if we fix some subgraph H$H$, then is it true that any graph without H$H$ as an induced subgraph contains a stable set on at least ncH$n^{c_H}$ vertices, for some constant cH>0$c_H>0$ depending only on H$H$? Erdős and Hajnal [ErHa89] proved this themselves for all H$H$ with ≤4$\le 4$ vertices, but it was only this year that we knew it for all H$H$ on 5$5$ vertices. Each new H$H$ was hard-won, requiring a long and complicated argument using special properties of H$H$.

A general proof of the Erdős-Hajnal conjecture for all H$H$ seems far out of reach, although Erdős and Hajnal [ErHa89] did manage to prove that any H$H$-free graph contains a stable set onvertices, which Bucić, Nguyen, Scott, and Seymour [BNSS23] improved to exp(cHlognloglogn−−−−−−−−−−−√)$\exp (c_H\sqrt{\log n\log \log n})$.

It feels like there is a large important structural aspect of graphs that we are missing. As Zach Hunter has pointed out, it is even open whether there is some fH(n)→∞$f_H(n)\to \mathrm{\infty }$ such that any H$H$-free graph contains either a complete graph on ≥ncH$\ge n^{c_H}$ vertices or an independent set on at least fH(n)$f_H(n)$ vertices.

[67] - Erdős discrepancy problem

Suppose we assign all natural numbers n≥1$n\ge 1$ a positive or negative sign: in other words, a function f:N→{−1,+1}$f:\mathbb{N}\to \{-1,+1\}$. Given any finite set A$A$ we can then measure the discrepancy of f$f$ along this sequence asIn other words, it measures how 'unbalanced' f$f$ is over A$A$. Note that D(A)≤|A|$D(A)\le |A|$ for any A$A$. A general question in discrepancy theory is to find sets A$A$ with very large discrepancy.

For some functions f$f$ this is easy - for example if f(n)=+1$f(n)=+1$ for all n$n$ then D(A)=|A|$D(A)=|A|$ for every A$A$. It is trivial that, for any N$N$, there exists A⊆{1,…,N}$A\subseteq \{1,\dots ,N\}$ such that D(A)≥N/2$D(A)\ge N/2$. But what if we ask for A$A$ to be structured, such as an arithmetic progression? Roth [Ro64] proved that, for any f$f$, there exists an arithmetic progression P⊆{1,…,N}$P\subseteq \{1,\dots ,N\}$ such that(In fact Roth said, in his later years, that this was his favourite of all the results he proved!) This is best possible in general, as a random f$f$ demonstrates.

In [67] Erdős goes further, and asks for not only an arithmetic progression, but a homogeneous arithmetic progression: a set of the shape P={d,2d,…,kd}$P=\{d,2d,\dots ,kd\}$ for some integers k,d≥1$k,d\ge 1$. Must there exist, for any f:N→{−1,1}$f:\mathbb{N}\to \{-1,1\}$, homogeneous arithmetic progressions such that D(P)$D(P)$ grows arbitrarily large? Erdős was a big fan of this problem, returning to it in many problem collections, and offered $500 for a solution.

This was resolved in the affirmative by Tao [Ta16]; a key part of Tao's proof relies on reducing it to the case of multiplicative functions f$f$ (this reduction was first done by the Polymath project), and then using a sophisticated number theoretic argument to find homogeneous progressions along which multiplicative functions f$f$ must grow.

Yet again, although the original challenge of Erdős has been met, there is still much we don't understand here - in particular it seems likely that there is a quantitative version of this, that there must exist a homogeneous progression P$P$ of length N$N$ such that D(P)≫logN$D(P)\gg \log N$. The best we know in this direction is D(P)≫(loglogN)c$D(P)\gg (\log \log N{)}^c$ for some c>0$c>0$, a result of McNamara [Mc21].

[77] - Ramsey numbers

Another central topic in graph theory, and combinatorics in general, is Ramsey theory, which studies various instances of the phenomena that in any finite colouring of some large enough global structure one is guaranteed to find monochromatic copies of any fixed smaller structure. (We've already seen this in the discussion of the Erdős-Hajnal conjecture above.) The most natural, and simplest, Ramsey parameter to define is the Ramsey number: let R(k)$R(k)$ be the smallest n$n$ such that in any 2$2$-colouring of the edges of the complete graph Kn$K_n$ there must exist a monochromatic copy of Kk$K_k$.

Ramsey himself considered an infinite analogue of this question (with applications in mind to logic); the first proper paper on finite Ramsey theory, and functions such as R(k)$R(k)$, was by Erdős and Szekeres [ErSz35] (in fact with an application to a problem in geometry in mind, see [107]). In that paper they proved, by a simple inductive argument, that R(k)≤(2k−2k−1)$R(k)\le (\genfrac{}{}{0ex}{}{2k-2}{k-1})$, which has the shape 4(1+o(1))k$4^{(1+o(1))k}$. A few years later Erdős used the probabilistic method to give a lower bound which also grows exponentially with k$k$, but more like 2–√(1+o(1))k${\sqrt{2}}^{(1+o(1))k}$.

Erdős posed a number of questions about R(k)$R(k)$, and [77] is one of the most famous: improve both upper and lower bounds, ideally to the point of meeting in the middle and finding some constant C$C$ such that R(k)=(C+o(1))k$R(k)=(C+o(1){)}^k$. The above mentioned results show that, if it exists, then 2–√≤C≤4$\sqrt{2}\le C\le 4$. The lower bound has yet to be improved. The upper bound was improved only recently by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23], and subsequent work of Gupta, Ndiaye, Norin, and Wei [GNNW24] has refined this further, and we now know thatBut we don't actually know that C$C$ even exists! It is possible, with the current state of our understanding, that R(k)≈2–√k$R(k)\approx {\sqrt{2}}^k$ for many k$k$, and also sometimes R(k)≈3k$R(k)\approx 3^k$, also for many k$k$. I haven't even heard anyone even give a reasonable guess or heuristic that predicts what the correct value of C$C$ should be (occasionally I've heard C=2–√$C=\sqrt{2}$ should be correct, because the random construction probably can't be improved much, but this was not said with a lot of confidence).

Improving the bounds for C$C$, or even showing that it exists, would be a major advance in Ramsey theory.

[90] - Unit distances

Erdős asked many beautiful questions in discrete geometry, and it was tough to choose from amongst these; perhaps the distinct distances problem [89] is more influential and well-known than this problem, but since that problem has been nearly resolved by Guth and Katz [GuKa15], I thought I'd highlight another problem, perhaps superficially similar, but that we know much less about.

Let P$P$ be an arbitrary set of n$n$ points in R2${\mathbb{R}}^2$. Let U(P)$U(P)$ count the number of pairs x,y∈P$x,y\in P$ which are distance 1$1$ apart: |x−y|=1$|x-y|=1$. Obviously we can certainly have U(P)=0$U(P)=0$ in many different ways, so the interesting question is how large can U(P)$U(P)$ get? The trivial upper bound is O(n2)$O(n^2)$, and after some experimentation one is led to guess that this should never be achieved: it is hard to place n$n$ points in the plane while keeping many points just distance 1$1$ from each other!

For example, a naive start might be to put down one point, and then n−1$n-1$ points arranged on the unit circle centred at the first point. This shows that U(P)≫n$U(P)\gg n$ is certainly possible - but then it is impossible to get more than O(1)$O(1)$ many more unit distances from those other points, wherever on the circle we place them. A better choice is to take n$n$ points arranged at the integer points of a grid; this does a little better,but this is still of the shape U(P)≤n1+o(1)$U(P)\le n^{1+o(1)}$. Erdős conjectured many times (and offered $500 for a solution) that this was best possible: U(P)≤n1+o(1)$U(P)\le n^{1+o(1)}$ for any set P$P$ of n$n$ points. This is somehow the 'dual' of the distinct distance problem (where instead of asking for lower bound on the number of different distances we're asking for an upper bound on the number of the same distance), and has seen much less progress. Spencer, Szemerédi, and Trotter [SST84] proved that U(P)≪n4/3$U(P)\ll n^{4/3}$, but this bound has not been improved in over 40 years.

This problem serves as a great example that, despite some spectacular results in recent years in discrete geometry, we are still a long way from understanding even some of the most basic questions.

[571] and [713] - Exponents of Turán numbers

Finally, one more problem from graph theory. Given a fixed finite graph G$G$, the Turán number ex(n;G)$\mathrm{e}\mathrm{x}(n;G)$ is defined as the largest possible number of edges in a graph on n$n$ vertices which does not contain G$G$ as a subgraph. Large parts of extremal graph theory is concerned with the estimation of these Turán numbers, which arise in many different applications of graph theory. (Indeed, Erdős actually considered what we would now call ex(n;C4)$\mathrm{e}\mathrm{x}(n;C_4)$ in 1936 when considering a number theoretic problem [425], 5 years before Turán himself studied the concept.)

To a first order approximation, the behaviour of the Turán number is known, and depends only on the chromatic number of G$G$: if χ(G)=k$\chi (G)=k$ thenas proved by Erdős and Stone. Fascinating questions arise, however, when we ask for more refined information.

In particular, what can we say about ex(n;G)$\mathrm{e}\mathrm{x}(n;G)$ when G$G$ is a bipartite graph? The Erdős-Stone theorem says only that it is o(n2)$o(n^2)$. On the other hand, (unless G$G$ is just a union of disjoint edges) then clearly ex(n;G)≫n$\mathrm{e}\mathrm{x}(n;G)\gg n$, since one could e.g. take a disjoint matching. But how fast can it actually grow? Are all scales of growth between n$n$ and n2$n^2$ possible? For example, ex(n;C4)≍n3/2$\mathrm{e}\mathrm{x}(n;C_4)\asymp n^{3/2}$.

Erdős and Simonovits conjectured that every rational exponent α$\alpha$ is achievable, in that ex(n;G)≍nα$\mathrm{e}\mathrm{x}(n;G)\asymp n^{\alpha }$ for some bipartite G$G$ (this is [571]). Conversely, if ex(n;G)≍nα$\mathrm{e}\mathrm{x}(n;G)\asymp n^{\alpha }$ then α$\alpha$ must be a rational in [1,2)$[1,2)$ (this is [713]). There are many partial results towards these conjectures known, but a full solution is still out of reach.