181 problems

Let $G$ be a graph, and let $\mu(G)$ be the minimum size of a maximal independent set in $G$. For an integer $k$, say that $G$ is $k$-EKR if no intersecting family in the family of…

Let $G$ be a $d$-regular graph, and let $i(G)$ denote its number of independent sets. Kahn's conjecture. The upper bound proved for regular bipartite graphs could be extended to al…

Davies's conjecture.

Let $G$ be a $d$-regular graph, and let $i(G)$ denote its number of independent sets. Among $d$-regular graphs, consider the quantity $i(G)^{1/|V(G)|}$. Alon–Kahn conjecture. The e…

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…

Let $T$ be a tree, and let $i_j(T)$ denote the number of independent sets of $T$ with cardinality $j$. Alavi–Erdős–Malde–Schwenk conjecture. The sequence of numbers of independent…

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.…

Ilinca–Kahn's conjecture. The precise asymptotics satisfy

Let an $(n,d)$-graph be a $d$-regular graph on $n$ vertices, and let $i(G)$ denote its number of independent sets. Granville's conjecture. Every $(n,d)$-graph satisfies … where…

Let $G$ be a finite graph. Write $\ker(G)$ for its kernel, $\diadem(G)$ for its diadem, and $\alpha(G)$ for its independence number. Kernel–diadem conjecture. For every graph $G$,…

Let $G$ be a graph on $n$ vertices with minimum degree at least $d$, and let $K_{d,n-d}$ denote the complete bipartite graph with parts of sizes $d$ and $n-d$. Galvin's conjecture.…

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$.

Davies–Perkins conjecture. The down-up walk mixes in polynomial time whenever

Let $d\geq 3$. In distance-$d$ independent set reconfiguration, denoted by $\textsc{D}d\textsc{ISR}$, configurations are distance-$d$ independent sets, and under the token-sliding…

Sharp second-order conjecture. Suppose $r,d\geq 2$. Then

Let $t$ be a positive integer, let $G$ be an $n$-vertex graph, and let $\alpha(G)$ denote the size of its largest independent set. Independent-set bound for clique-minor-free graph…

Let $G=(V,\mathcal{E})$ be a graph and let $\mathcal{I}_G$ be its hereditary family of independent sets. Write $\mathcal{I}_G^{(r)}$ for the independent sets of size $r$, and let…

Engbers–Galvin conjecture. The complete bipartite graph $K_{\delta,n-\delta}$ maximizes $i_t(G)$ over all $n$-vertex graphs with minimum degree at least $\delta$.

Let $G$ be a graph. An independent set is a set of vertices containing no edge of $G$, and a cover of the vertex set is a family of such sets whose union is the vertex set. Strong…

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 $G$ be a random $d$-regular bipartite graph with bipartition $V_1\cup V_2$, and for density parameters $(\alpha,\beta)$ let $Z_G^{\alpha,\beta}$ denote the total weight of inde…

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…

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

Let $G$ be a triangle-free graph with maximum degree $\Delta$ and $n=|V(G)|$, and let $\varepsilon>0$. Karp's conjecture. No randomized polynomial-time algorithm can, for every tri…

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 ……