14 problems

For each integer $k\geq3$, let $\widetilde{P}_k$ denote the CRG introduced in the paper, and let $p_k$ be the associated parameter defined there. A CRG is $p$-core when it has no a…

Let ${\mathcal H}$ be a non-trivial hereditary property of graphs, and call $p\in[0,1]$ an accumulation point when the edit-distance function of ${\mathcal H}$ is not locally deter…

Let ${\mathcal H}$ be a non-trivial hereditary property of graphs, and call $p\in[0,1]$ an accumulation point when the edit-distance function of ${\mathcal H}$ is not locally deter…

Let $s,t\in\mathbb{N}$. Forbidding the complete bipartite graph $K_{s,t}$ defines the hereditary property $\operatorname{Forb}(K_{s,t})$, and an accumulation point is a parameter…

Let $h$ be even, let $p_0$ be the parameter from the paper, and let $p\in(0,p_0]$. Write $\operatorname{ed}_{\operatorname{Forb}(C_h)}(p)$ for the edit-distance function for forbid…

Let $\alpha_k$ be the asymptotic expected edit-distance constant for independent random strings over an alphabet of size $k$. Large-alphabet asymptotic conjecture. There exists a c…

Let $\gamma_k$ denote the asymptotic expected edit-distance constant for independent random strings over an alphabet of size $k$. Kleinberg–Karp's conjecture. Sampling estimates su…

Let $\mathcal{H}$ be a non-trivial hereditary graph property, and let accumulation points mean limit points of its edit distance function. Half-interval conjecture. For any non-tri…

Let $\mathcal{H}$ be a non-trivial hereditary graph property, and call a point an accumulation point if it is a limit point of the edit distance function of $\mathcal{H}$. Finitene…

For positive integers $s$ and $t$, let $K_{s,t}$ be the complete bipartite graph with parts of sizes $s$ and $t$, and let $\operatorname{Forb}(K_{s,t})$ denote the hereditary prope…

Let $d4d8$ be a non-trivial hereditary property, and let $d4d2(d4d8)$ be the set of CRGs avoiding its forbidden graphs. For each $p a[0,1]$, let $gK(p)$ denote the quadratic minimi…

Finite CRG representation conjecture. For every nontrivial hereditary property $\mathcal{H}$ and every $\varepsilon>0$, the edit distance function…

Let $H_9$ be the graph defined in Theorem. Write $d^*(H_9)$ for its edit distance and $p^*(\operatorname{Forb}(H_9))$ for the associated critical probability. Conjecture for $H_9$.…

Fix $p_0\in (0,1)$ and let $G(n_0,p_0)$ denote the Erdős–Rényi random graph on $n_0$ vertices with edge-probability $p_0$. Let $\mathcal{H}={\rm Forb}(G(n_0,p_0))$ be the hereditar…