ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For k≥2k\geq 2, let Gn,kG_{n,k} be the graph obtained from Kk,n−kK_{k,n-k} by adding all edges among the kk vertices in the first part; equivalently, it is the kk-fold cone over n−kn-k isolated vertices. Let PG\mathcal{P}_G be the symmetric edge polytope of a graph GG on nn vertices, and let γk(PG)\gamma_k(\mathcal{P}_G) denote its kkth gamma coefficient. A graph is kk-connected if deleting fewer than kk vertices leaves it connected.

Gamma-zero characterization conjecture. If k∈Nk\in\mathbb{N} and GG is a kk-connected graph on nn vertices, then

γk(PG)=0\gamma_k(\mathcal{P}_G)=0

if and only if n<2k+1n<2k+1, or n≥2k+1n\geq 2k+1 and

Kk,n−k⊆G⊆Gn,k.K_{k,n-k}\subseteq G\subseteq G_{n,k}.

The conjecture generalizes the stated characterization for γ2=0\gamma_2=0 and has been verified computationally for small values of kk and nn. Its general status remains open.

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.