12 problems

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

Triangle-maximisation conjecture. If

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

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 $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…

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…

Lovász–Simonovits conjecture. For every integer $r\geq 3$, there exists $n_0=n_0(r)>0$ such that