Gamma-zero characterization conjecture for k-connected graph symmetric edge polytopes

About 4 years old · traced to

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.

References

Primary source

Alessio D'Alì, Martina Juhnke-Kubitzke, Daniel Köhne and Lorenzo Venturello, “On the gamma-vector of symmetric edge polytopes”, arXiv:2201.09835 (2022).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.