22 problems

If $H$ is bipartite and is $r$-degenerate, that is, every induced subgraph of $H$ has minimum degree $\leq r$, then $\mathrm{ex}(n;H) \ll n^{2-1/r}.$

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs…

For $r≥4$, let $f_r(n)$ be the least number of edges forcing a $K_r$ in every $n$-vertex graph. Is there a constant $c_r>0$ such that every $n$-vertex graph with $f_r(n)$ edges has…

Is it true that every $3$-uniform hypergraph on $3n$ vertices with at least $n^3+1$ edges contains either a subgraph on $4$ vertices with $3$ edges or a subgraph on $5$ vertices wi…

Let $g_k(n)$ be the largest number of edges in an $n$-vertex graph having no cycle with $k$ chords incident to a single vertex of the cycle. Is $g_k(n)=(k+1)n-(k+1)^2$ for all suff…

Let $f(n;k,l)=\min \mathrm{ex}(n;G)$, where $G$ ranges over all graphs with $k$ vertices and $l$ edges. Give good estimates for $f(n;k,l)$ in the range $k<l\leq k^2/4$. For fixed…

Determine an asymptotic formula for $ex(n,C_4)$, the largest number of edges in an $n$-vertex graph containing no four-cycle.

Is it true that $\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?$

Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [1,2)$ and $c>0$ such that $\mathrm{ex}(n;G)\sim cn^\alpha?$ Must $\alpha$ be rational?

Determine, for any $k>r>2$, the value of $\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},$ where $\mathrm{ex}_r(n,K_k^r)$ is the largest number of $r$-edges which can placed on $n$…

Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ and at least $\delta n^2$ edges then $G$ contains an independent set of size…

Let $Q_k$ be the $k$-dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of $\mathrm{ex}(n;Q_k).$

If $\mathcal{F}$ is a finite set of finite graphs then $\mathrm{ex}(n;\mathcal{F})$ is the maximum number of edges a graph on $n$ vertices can have without containing any subgraphs…

Is it true that, for $k\geq 2$, $\mathrm{ex}(n;\{C_{2k-1},C_{2k}\})=(1+o(1))(n/2)^{1+\frac{1}{k}}.$

Is it true that $\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?$

Show that for $k\geq 3$ $\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.$

Show that for any rational $\alpha \in [1,2)$ there exists a bipartite graph $G$ such that $\mathrm{ex}(n;G)\asymp n^{\alpha}.$

What is $\mathrm{ex}_3(n,K_4^3)$? That is, the largest number of $3$-edges which can placed on $n$ vertices so that there exists no $K_4^3$, a set of 4 vertices which is covered by…

If a bipartite graph $H$ has minimum degree $r\geq3$, must there exist $\varepsilon(H)>0$ such that …

For a bipartite graph $H$, is $\operatorname{ex}(n,H)=O(n^{3/2})$ if and only if $H$ is $2$-degenerate, meaning every nonempty subgraph of $H$ has a vertex of degree at most $2$?

Let $H$ be a fixed graph containing a cycle, and let $\operatorname{ex}(n,H)$ be the maximum number of edges in an $H$-free graph on $n$ vertices. Is the number of labelled $H$-fre…

A balanced double star $S_{m,m}$ is the graph obtained from an edge whose endpoints are joined respectively to $m$ and $m$ additional distinct vertices. For a planar graph family,…