106 problems

Let $G$ be an $n$-vertex $k$-chromatic $\ell$-connected graph, and let $i_t(G)$ denote the number of independent sets of size $t$ in $G$. Fixed-size independent-set conjecture. If…

Let $G$ be an $n$-vertex $k$-chromatic $\ell$-connected graph, and let $i_t(G)$ denote the number of independent sets of size $t$ in $G$. Fixed-size independent-set conjecture. If…

Maximum-independent-set structure conjecture. For all positive integers $k$, every maximum independent set in $QI(k^2,k)$ is of the form $S_{\{a,b\}}$ for distinct…

Let $d\geq 3$ be the maximum degree, let $\ell$ be the activity, and let $\ell_c(d)=(d-1)^{d-1}/(d-2)^d$ be the critical activity for decay of correlations on the infinite $d$-regu…

Let $G$ be the graph whose vertices are the elements of the symmetric group $S_n$, with two vertices $\pi$ and $\pi'$ adjacent when $\pi(i)\neq\pi'(i)$ for every $1\leq i\leq n$. A…

Independent-set density existence conjecture. For every $c>0$ and $r\geq 3$, the limits

Let $0<c<1$ be a constant. For a graph $G$, let $\operatorname{MIS}(G)$ denote its family of maximal independent sets, and define the family of large maximal independent sets by ……

Beta conjecture. For all graphs $G$ on $n$ vertices,

Let $0<c<1$ be a constant. For a graph $G$, let $\alpha(G)$ be the size of a largest independent set, and let $h(G)$ be the size of a smallest set meeting every maximum independent…

Finite exact-density tile-family conjecture. For every fixed $q$, there is a finite coordinate-symmetric family of induced templates of independence density $1/q$ such that, in eve…

Let $k\geq 3$ be an integer. A $k$-uniform hypergraph is linear if it contains no $2$-cycle, and let $\alpha({\mathcal H})$ denote its independence number. Shattering-threshold con…

Let $k\geq 3$, and let $a_k>0$ satisfy $a_k=1-o_k(1)$ as $k\to\infty$. A $k$-uniform hypergraph is linear if it contains no $2$-cycle. Verstraëte–Wilson conjecture. Every $n$-verte…

A pseudorandom class of hypergraphs is a hereditary class whose sparse random model contains, with high probability, an induced subhypergraph on at least $(1-o_d(1))n$ vertices bel…

AIM low-degree conjecture. In $G(n,\frac12)$, no degree-$o(\log^2 n)$ polynomial can find an independent set of size $0.9\log_2 n$.

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

Let $i(P)$ denote the number of independent sets of a connected planar graph $P$. Planar Linek's Problem. Every positive integer is equal to $i(P)$ for some connected planar graph…

Let $i(T)$ denote the number of independent sets of a tree $T$. Effective Linek's Problem. Every integer greater than $88013$ appears as $i(T)$ for some tree $T$. This is an effect…

Let $T$ be a tree, let $k\geq 1$, and let $\mathcal{I}_{T}^{k}(v)$ denote the family of independent sets of size $k$ in $T$ containing $v$. A leaf-centred maximum-star conjecture.…

Let $\Gamma$ be an $n$-vertex graph, and let $\mathrm{mis}(\Gamma)$ denote its number of maximal independent sets. Hassler–Treglown conjecture. If $\Gamma$ contains a perfect match…

Let $G$ be the graph in the paper's online model, let $\mathcal{A}(G)$ be the set selected by an online algorithm $\mathcal{A}$, and let $E$ be the set of all future edges ever rev…

Let $G_{\mathrm{bip}}(n,p)$ be the random bipartite graph in the online model considered in the source, let $\gamma$ be the balance parameter, and let $\alpha_{\rm COMP}$ denote th…

Let $\Gamma$ be a graph on $n$ vertices containing a perfect matching. A maximal independent set is an independent vertex set that is not properly contained in any larger independe…

Ilinca–Kahn's conjecture. The precise asymptotics satisfy

Let $\mathbb{G}(n,1/2)$ be the Erdős–Rényi random graph on $n$ vertices, and let a degree-$r$ polynomial algorithm mean a polynomial of degree at most $r$ used to find an independe…

Let $D$ be a digraph, and call a set of vertices independent if no two of its vertices are joined by an arc. A path in $D$ is longest if it has maximum length among all paths in…