18 problems

Alon–Krivelevich–Sudakov conjecture. The condition

Let $G$ be an $(n,d,lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose non-trivial adjacency-matrix eigenvalues have absolute value at most $lambda$. Krivelevich–Sud…

Krivelevich–Sudakov–Szabó conjecture. There exists an absolute constant $c>0$ such that if $\lambda\leq cd^2/n$, then every $(n,d,\lambda)$-graph $G$ on $n\in 3\mathbb{N}$ vertices…

Let $G$ be an $(n,d,\lambda)$-graph, meaning an $n$-vertex $d$-regular graph whose non-trivial eigenvalues have absolute value at most $\lambda$. A Hamilton cycle is a cycle contai…

Let $\mathscr{G}_n$ be the family of explicit graphs with $n$ vertices constructed for $n=2^m-1$, and let $\Gamma_n\in\mathscr{G}_n$ be any choice. Their limiting spectral distribu…

Let $G$ be an $(n,d,lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose non-trivial adjacency-matrix eigenvalues have absolute value at most $lambda$. A Hamilton deco…

Let $G$ be an $(n,d,\lambda)$-graph, meaning that $G$ is a $d$-regular graph on $n$ vertices and every non-trivial eigenvalue of its adjacency matrix has absolute value at most…

Let $G$ be an $(n,d,\lambda)$-graph, meaning an $n$-vertex $d$-regular graph whose nontrivial adjacency eigenvalues have absolute value at most $\lambda$. The independent-set count…

Let $\Delta\geq2$. An $(n,D,\lambda)$-graph is a graph with the corresponding order, degree and spectral parameters, and a $[t]$-colored tree is a tree whose edges receive colors i…

Tightness conjecture. The exponent $1/3$ in the authors' general density bound is tight.

Let $\Gamma$ be an $(n,d,\lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose nontrivial adjacency eigenvalues have absolute value at most $\lambda$. Let $k$ be a pos…

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…

Conlon–Rödl–Schacht–Skokan conjecture. The triangle removal lemma for subgraphs of $(p,\beta)$-bijumbled graphs should hold under the improved condition

For $k\geq 2$, let an $(\varepsilon,p,k-1,k)$-pseudorandom graph mean a graph satisfying the stated pseudorandomness condition with parameters $(\varepsilon,p,k-1,k)$. The $k$th po…

Sudakov–Szabó–Vu conjecture. The bound $\beta\leq c p^{t-1}n$ is the correct condition for finding copies of $K_t$ in a $(p,\beta)$-jumbled graph.

Let $t\geq4$, let $p$ be the edge-density parameter, and let a $(p,\beta)$-jumbled graph be a graph whose edge distribution has discrepancy at most $\beta$. Write $K_t$ for the com…

Let $t\geq 4$, and let a $(n,d,\lambda)$-graph be a graph on $n$ vertices with degree $d$ and second eigenvalue at most $\lambda$. The parameter $c>0$ is an absolute constant, and…

Global resilience conjecture. Then $G$ has global resilience $(1/4+o(1))nd$ with respect to being $C_k$-free.