40 problems

Let $t$ and $n$ be positive integers, and consider graphs on $n$ vertices with no $K_t$-subdivision. Clique-count conjecture. The maximum number of cliques in such a graph is … Thi…

Let $f(n,k)$ denote the maximal-clique deficiency parameter and let $c(n,k)$ denote the layered-tree parameter for $k$-uniform hypergraphs, as defined in the paper. Exponential rel…

Let $G$ be a graph with a fixed number of vertices and maximum degree $Delta$. A disjoint union of cliques of size $Delta+1$, together with at most one smaller clique, is a graph m…

Linear threshold conjecture. If

Jung–Keszegh–Pálvölgyi–Yuditsky conjecture. For all $k\geq2$ there exists a constant $c_k<1$ such that, whenever

Feige–Pauzner conjecture. For all $n>0$,

Let $G$ be a finite graph, and call it $r$-locally chordal if every ball of radius $r$ in $G$ is chordal. Let $|V(G)|$ denote the number of vertices of $G$ and let…

Let $G$ be a graph of average degree $d$, and let $\lambda_n$ be its smallest adjacency eigenvalue. Yang–Koolen conjecture. If $d$ is exponentially larger than $|\lambda_n|$, then…

Asymptotic clique-ratio conjecture. There exist positive constants $\varepsilon_1$ and $\varepsilon_2$ such that

Keevash–Saks–Sudakov–Verstraëte quadratic-range conjecture. The exact formula and extremal-structure conclusion for $\operatorname{ex}_k(n,K_r)$ established for sufficiently large…

Localized hypergraph clique-weight conjecture. One has

Frohmader's localized clique-weight conjecture. For every $m$-edge graph $G$,

Let $G$ be a 2-connected $n$-vertex graph with $n\ge 3$, and let $uv$ be an edge of $G$. Let $k\ge 4$ and $s\ge 2$ be integers, and write … where $0\le t\le k-4$. Here $N_s(G)$ den…

Let $r$ and $k$ be integers satisfying $1\le r\le k$ and $k\ge 3$. The Ramsey–Turán tiling function ${\bf{RTT}}_r(K_k)$ is defined as the asymptotic minimum-degree threshold for fo…

Let $G$ be a $2$-connected graph on $n$ vertices, and let $ab$ be an edge of $G$. Let $r\geq 4$ and $s\geq 2$ be integers, and write … for some $0\leq t\leq r-4$. Here $N_s(G)$ den…

Threshold equality conjecture. For all $r>k\ge 2$,

Gustavsson's conjecture. For each $r\ge 3$, we have

Let $t_{k-1}(n)$ denote the maximum number of edges in a $K_{k-1}$-free graph on $n$ vertices, and let $\tau_k(G)$ be the minimum size of a vertex set meeting every copy of $K_k$ i…

Let $V_1,V_2,\ldots,V_{k-1}$ be the vertex classes of the balanced Turán graph $T_{k-1}(n)$, with sizes satisfying…

Fix positive integers $d$ and $r$, and let $G$ be a graph on $d+1+r$ vertices with maximum degree $d$. For a fixed integer $t\ge 3$, let a clique of size $t$ mean a complete subgra…

Fix positive integers $d$ and $n$ with $d+1 \le n \le 2d+1$. Let $G$ be an $n$-vertex graph with maximum degree $d$, and write $r=n-d-1$. Galvin's conjecture. The maximum number of…

Erdős's conjecture. Every graph $G$ on $n$ vertices with more than $t_2(n)$ edges satisfies

Bucic et al.'s conjecture. The construction is optimal: every $2$-colored graph in which every vertex belongs to a monochromatic $k$-clique of each color has at least $4(k-1)$ vert…

For a graph with edge-density parameter $p$, call it $(p,\nu)$-bijumbled if it satisfies the relevant bijumbledness condition with parameter $\nu$. Bijumbled clique-avoidance conje…

Let $t$ be a positive integer and let $n\geq t-2$. Consider the maximum number of cliques in an $n$-vertex graph with no $K_t$-minor. Wood's conjecture. This maximum is…