71 problems

A graphon $W$ is $\rho$-locally dense if … for every measurable set $S\subseteq[0,1]$. A finite graph $H$ is called KNRS if every $\rho$-locally dense graphon satisfies…

Lovász–Szegedy finite-dimensionality conjecture. The space of typical vertices of every finitely forcible graphon has finite dimension.

Skokan–Thoma forcing conjecture. Every bipartite graph containing a cycle is forcing.

Behague–Morrison–Noel conjecture. Every odd cycle $C_{2k+1}$ is strongly common.

Let $W$ be a connected graphon and $K\in\mathbb{N}$. For each $n\in\mathbb{N}$, consider the $W$-edge-incremental process $\mathfrak{X}_n=(G_n^t)_{t=0}^{\binom{n}{2}}$ of order $n$…

Apex conjecture. For every positive integer $a$, the graph $H^{+a}$ is common. In particular, every complete tripartite graph $K_{r,s,t}$ is common.

Let graphons be measurable symmetric functions representing limits of dense graphs, and let subgraph density constraints prescribe the densities of specified finite graphs. A stoch…

Let $H$ be a fixed graph without isolated vertices. For $0<\beta<1$, let $\mathcal M_H(\beta)$ be the supremum of $t(H,W)$ over graphons $W$ with $t(K_2,W)\le\beta$. For…

Let $F$ be a graph, let $m_1,\dots,m_r$ and $\alpha_1,\dots,\alpha_r$ be the parameters defining $\widetilde{\mathcal P}_{m_1,\dots,m_r}(F;\alpha_1,\dots,\alpha_r)$, and let…

Let $W:\Omega^2\to[0,1]$ be a graphon, let $k\ge 2$ be fixed, and let $\mathbb{G}(n,W)$ be the associated inhomogeneous random graph. A $K_{k+1}$-fractional cover of $W$ is a measu…

Let $W:\Omega^2\to[0,1]$ be a graphon, and let $\mathbb{G}(n,W)$ denote the associated inhomogeneous random graph. The four conditions in Proposition are: $W$ is not a connected gr…

KRRS phase-structure conjecture. The Razborov triangle consists of one phase above the Erdős–Rényi curve and three infinite families of phases below the Erdős–Rényi curve.

Let $\mathbf L$ be a Lebesgue graph, meaning a graph on the standard probability space $[0,1]$ whose edge set is Lebesgue-measurable. A finite graph $F$ has a density in a graph gi…

Partial homogenization conjecture. If the corresponding solutions of are denoted by $(\bm{X}^{(k)}_i(t))_{i\in[N_k]}$ and $(\bm{w}^{(k)}_{i,j}(t))_{i,j\in[N_k]}$, then

Graphon quasirandomness conjecture. If there exists a constant-degree polynomial test distinguishing $\mathbb{G}(n,1/2)$ from any graphon, then the two distributions can also be di…

Persistence conjecture. Similar persistence results should hold for more complex bifurcation scenarios that occur only in infinite-dimensional systems.

The positive graph conjecture. A graph $H$ is positive if and only if it has a stable involution.

Lovász's finite forcibility conjecture. Finite forcibility is true: the extremal solutions of $t(F,\mathord{\cdot})$ or $I(\mathord{\cdot})$ on…

Nonattainment conjecture. There exists no $f\in\mathcal F$ such that

Extremal lower-bound conjecture. One should have

Let $H_1$ and $H_2$ be graphs, and let $p\in(0,1)$. A pair $(H_1,H_2)$ is $(p,1-p)$-common when it satisfies the off-diagonal common-pair inequality for every complementary pair of…

Off-diagonal uncommon-component conjecture. There exist a pair $(H_1,H_2)$ and $p\in(0,1)$ such that $H_2$ is uncommon and $(H_1,H_2)$ is $(p,1-p)$-common. The paper's abstract sta…

Let $H$ be a non-empty graph. It is common if, for every sequence of graphs $G$ with $v(G)\to\infty$, … where $\overline{G}$ is the complement of $G$. Erdős's conjecture. Every com…

Let $W$ be a graphon, meaning a symmetric measurable function $W:[0,1]^2\to[0,1]$, and let $t(H,W)$ denote the homomorphism density of a graph $H$ in $W$. A graph $H$ is strongly c…

Let $w$ be an $L^p$-graphon, and let the results of Theorem cited in the source be understood as the robust Robinson-property recovery results established there for $p>5$. Robust r…