Unsolved Problems

Let $r\geq 3$, and let $f_r(N)$ denote the size of the largest subset of $\{1,\ldots,N\}$ such that no subset of size $r$ has the same pairwise greate...

Let $\epsilon>0$ and $N$ be sufficiently large. Is it true that if $A\subseteq \{1,\ldots,N\}$ has size at least $\epsilon N$ then there must be disti...

Let $r\geq 2$ and suppose that $A\subseteq\{1,\ldots,N\}$ is such that, for any $m$, there are at most $r$ solutions to $m=pa$ where $p$ is prime and ...

Let $h(n)$ be such that, for any set $A\subseteq \mathbb{N}$ of size $n$, the set $ \left\{ \frac{a}{(a,b)}: a,b\in A\right\} $ has size at least $h(n...

Define $f(N)$ be the minimal $k$ such that the following holds: if $G$ is an abelian group of size $N$ and $A\subseteq G$ is a random set of size $k$ ...

Show that $ R(3,k+1)-R(3,k)\to\infty $ as $k\to \infty$. Similarly, prove or disprove that $ R(3,k+1)-R(3,k)=o(k). $ ...

Let $G$ be a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is 'as complete as possible'? That is, if $...

Let $m_1\leq\cdots\leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex cla...

Determine the Ramsey number $ R(C_4,S_n), $ where $S_n=K_{1,n}$ is the star on $n+1$ vertices. In particular, is it true that, for any $c>0$, there ar...

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Show that $ \lim_{k\to...

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine the value of...

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Is it true that $ R(T;...

Let $R(G;k)$ denote the minimal $m$ such that if the edges of $K_m$ are $k$-coloured then there is a monochromatic copy of $G$. Determine $ R(K_{s,t};...

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-col...

Let $\hat{R}(G)$ denote the size Ramsey number, the minimal number of edges $m$ such that there is a graph $H$ with $m$ edges such that in any $2$-col...

Let $R_r(n)$ denote the $r$-uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$-colour all edges of the complete $r$-uniform hypergr...

Let $F(n,\alpha)$ denote the smallest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq [n]$ with $\lvert X\r...

Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$-uniform hypergraph on $m$ vertices are $2$-coloured then there is a monochromatic co...

Let $G$ be such that any subgraph on $k$ vertices has at most $2k-3$ edges. Is it true that, if $H$ has $m$ edges and no isolated vertices, then $ R(G...

Let $G$ be either $Q_3$ or $K_{3,3}$ or $H_5$ (the last formed by adding two vertex-disjoint chords to $C_5$). Is it true that, if $H$ has $m$ edges a...

Let $G$ be a graph such that $R(G,T_n)\ll n$ for any tree $T_n$ on $n$ vertices and $R(G,K_n)\ll n^2$. Is it true that, for any $H$ with $m$ edges and...

Let $k\geq 1$. What is the best possible $c_k$ such that $ R(C_{2k+1},H)\leq c_k m $ for any graph $H$ on $m$ edges without isolated vertices?...

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

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

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

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}}. $ ...

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 wi...

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...

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 ...

Let $G$ be a graph with $n$ vertices and $\delta n^{2}$ edges. Are there subgraphs $H_1,H_2\subseteq G$ such that {UL} {LI}$H_1$ has $\gg \delta^3n^2$...

What is the maximum number of edges that a graph on $n$ vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?...

Let $f_k(n)$ be minimal such that if $n$ points in $\mathbb{R}^2$ have no $k+1$ points on a line then there must be at most $f_k(n)$ many lines contai...

Let $g(n)$ be maximal such that in any set of $n$ points in $\mathbb{R}^2$ with no four points on a line there exists a subset on $g(n)$ points with n...

Let $\alpha$ be the infinite ordinal $\omega^{\omega^2}$. Is it true that in any red/blue colouring of the edges of $K_\alpha$ there is either a red $...

Determine which countable ordinals $\beta$ have the property that, if $\alpha=\omega^{^\beta}$, then in any red/blue colouring of the edges of $K_\alp...

Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number $>\aleph_0$....

Is there an infinite graph $G$ which contains no $K_4$ and is not the union of countably many triangle-free graphs?...

For which graphs $G_1,G_2$ is it true that {UL} {LI} for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured...

Let $G$ be a graph on at most $\aleph_1$ vertices which contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite graph with $\aleph_0$...

Let $m$ be an infinite cardinal and $\kappa$ be the successor cardinal of $2^{\aleph_0}$. Can one colour the countable subsets of $m$ using $\kappa$ m...

Let $e(n,r)$ be minimal such that every graph on $n$ vertices with at least $e(n,r)$ edges, each edge contained in at least one triangle, must have an...

For which limit ordinals $\alpha$ is it true that if $G$ is a graph with vertex set $\alpha$ then $G$ must have either an infinite path or independent...

Let $(A_i)$ be a family of sets with $\lvert A_i\rvert=\aleph_0$ for all $i$, such that for any $i eq j$ we have $\lvert A_i\cap A_j\rvert$ finite and...

Let $(A_i)$ be a family of countably infinite sets such that $\lvert A_i\cap A_j\rvert eq 2$ for all $i eq j$. Find the smallest cardinal $C$ such th...

Given $n$ distinct points $A\subset\mathbb{R}^2$ must there be a point $x\in A$ such that $ \#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}? $ Or even $\gg n/\...

Let $f(n)$ be the minimal $m$ such that if the edges of $K_{2^n+1}$ are coloured with $n$ colours then there must be a monochromatic odd cycle of leng...

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (sometimes called the cl...

For a graph $G$ let $\tau(G)$ denote the minimal number of vertices that include at least one from each maximal clique of $G$ (sometimes called the cl...

Let $G$ be a connected graph with $n$ vertices, minimum degree $d$, and diameter $D$. Show if that $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$ th...

Let $f(n,k)$ be minimal such that there is a graph with $n$ vertices and $f(n,k)$ edges where every set of $k+2$ vertices induces a subgraph with maxi...