19 problems

Let $G$ be a graph on $n$ vertices with maximum degree at most $r$, and let $t\geq 3$ be fixed. Let $a$ be as large as possible subject to $n=a(r+1)+b$, with $0\leq b<r+1$. Gan–Loh…

Let $t\geq 3$, let $G$ be a graph with $m$ edges and maximum degree at most $r$, and write … Here $k_t(G)$ denotes the number of copies of $K_t$ in $G$, $K_{r+1}$ is the complete g…

Let $T$ be a tree on $k$ vertices and let $r\geq3$. Write … For a graph $G$, let ${\mathcal N}(K_r,G)$ denote the number of copies of $K_r$ in $G$, and let ${\mathrm{ex}}(n,K_r,T)$…

Frankl–Gryaznov–Talebanfard's conjecture. If $\mathcal{H}$ contains no clique of size $ell+1$, then

Let $n$, $k$, and $s$ be integers, and let $P_3$ denote the path on three vertices. Write $kP_3$ for the disjoint union of $k$ copies of $P_3$, and let $M_n$ be the graph consistin…

Fix $r\ge4$. For positive integers $n,e$ with $e\le\binom{n}{2}$, let $t_{r-1}(n)$ be the number of edges in the balanced complete $(r-1)$-partite graph, let $g_r(n,e)$ be the mini…

Let $g_r(n,e)$ denote the minimum number of copies of $K_r$ among graphs with $n$ vertices and $e$ edges, and let $\mathcal{H}_1(n,e)$ be the family of $(n,e)$-graphs obtained from…

Let $g_r(n,e)$ be the minimum number of copies of $K_r$ in an $n$-vertex graph with $e$ edges, and let $\mathcal{K}(n,e)$ be the family of $(n,e)$-graphs obtained from a complete m…

Let $G$ be a graph, let $m\geq 1$ and $k\geq 2$, and let $w$ be an $m$-weighting of $G$. A $k$-clique independent set is a set $I$ of vertices such that every $k$-clique of $G$ con…

Asymptotic clique-count conjecture. The expected number of cliques satisfies

Extremal graph conjecture. The extremal graph for $ex(n,K_r,F_k)$ is still $\bar K_{n-v(H)}+H$, where $H$ is a graph with $V(H)=k-1$ and $\Delta(H)=k-1$.

Triangle-maximisation conjecture. If

Simultaneous clique-maximisation conjecture. If $C(G)=C(\Sigma,n)$, then for every $s\geqslant 0$,

Clique-count decomposition conjecture. For every surface $\Sigma$ and integer $n$,

Let $n=a(r+1)+b$, and let $m$ satisfy … For fixed $t$, or for $k=\sum_{t \ge 2} k_t$, consider graphs of order $n$, size $m$, and maximum degree at most $r$. Critical-regime clique…

Let $n=qD+r$, where $q\in\mathbb{N}$ and $1\le r\le D$. Consider $n$-vertex graphs with maximum degree at most $D-1$, and let $t\ge 3$. Clique-count conjecture. The maximum number…

Strong worst-case clique-counting hardness conjecture. Any randomized algorithm $A$ for \textsc{\#(k,s)-clique} with error probability less than $1/3$ takes time…

Threshold conjecture for $K_m$-counts. If

Let $K_{s,t}$ denote the complete bipartite graph with parts of sizes $s$ and $t$, and consider the case $H=K_{s,t}$ with $s\leq t$ and $T=K_m$. In particular, when $H=K_{1,t}$, an…