ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let G(n,m)\mathbf{G}(n,m) denote the collection of graphs on nn vertices and mm edges, and let β1FL(G)\beta^{\mathrm{FL}}_1(G) denote the first flag-complex Betti number of a graph GG.

Complete-bipartite spanning-subgraph conjecture. If G∈G(n,m)G\in\mathbf{G}(n,m) and

β1FL(G)=max⁡H∈G(n,m)β1FL(H),\beta^{\mathrm{FL}}_1(G)=\max_{H\in\mathbf{G}(n,m)}\beta^{\mathrm{FL}}_1(H),

then GG contains a complete bipartite spanning subgraph.

This conjecture proposes a structural characterization of graphs attaining the extremal first flag-complex Betti number for fixed numbers of vertices and edges. The source presents the problem as a challenging direction for future research and gives an example showing that extremal graphs need not contain a Turán graph as a spanning subgraph.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.