The bounded enumeration conjecture for induced cuts

From papers

For a graph with the parameters and family of cuts defined in Lemma~, let Cind\mathcal{C}^{\mathrm{ind}} denote the corresponding family of induced cuts. Bounded enumeration conjecture. Lemma~ holds with

Cind2O(1/δ).|\mathcal{C}^{\mathrm{ind}}| \leq 2^{O(1/\delta)}.

This conjecture proposes that the family of induced cuts can be bounded independently of the graph size, depending only exponentially on 1/δ1/\delta. The supplied text gives no resolution or further evidence for the conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Charlie Carlson, Ewan Davies, Alexandra Kolla and Aditya Potukuchi, “Approximately counting independent sets in dense bipartite graphs via subspace enumeration”, arXiv:2307.09533 (2023).

Solutions 0

No solutions have been posted yet.