The arithmetic of edge-threshold graph polytopes: Minkowski interpolation, transcendental spectra, and a mixed-volume shift theorem

Abstract For a finite graph 𝐺 and a parameter 𝑑, the edge-threshold polytope 𝑃𝐺(𝑑) = {π‘₯ ∈ [0, 1]𝑛 ∢ π‘₯𝑒 + π‘₯𝑣 ≀ 𝑑 for all 𝑒𝑣 ∈ 𝐸(𝐺)} interpolates between the fractional stable set polytope 𝑃𝐺(1) of 𝐺 and the unit cube. We prove three groups of results. (i) For 1 ≀ 𝑑 ≀ 2, 𝑃𝐺(1 + 𝑐) = (1 βˆ’ 𝑐)𝑃𝐺(1) + 𝑐[0, 1]𝑛 is a Minkowski interpolation; hence Vol 𝑃𝐺(1 + 𝑐) is a polynomial of degree at most 𝑛 whose Bernstein coefficients are the mixed volumes of 𝑃𝐺(1) and [0, 1]𝑛. (ii) For the path graph the transfer operator 𝑇𝑑 on 𝐿 2 [0, 1] has a fully explicit spectrum: the nonzero eigenvalues are πœ† = (2 βˆ’ 𝑑)/πœƒ, where πœƒ runs over the non-degenerate real roots of (2 βˆ’ 𝑑) cos πœƒ = (𝑑 βˆ’ 1)πœƒ(1 + sin πœƒ); if 𝑑 is algebraic then every nonzero eigenvalue is transcendental, by an elementary rigidity lemma based on the Hermite–Lindemann theorem; and the volume expansion carries an explicit remainder bound. (iii) We prove a subgraph identity and a vertex-deletion recursion for the coefficients π‘Žπ‘— (𝐺) = [πœ€π‘— ] Vol 𝑃𝐺(2 βˆ’ πœ€), and deduce a complete mixed-volume shift theorem: the Bernstein coefficients of Vol 𝑃𝐢𝑛+1 (1 + 𝑐) are those of Vol 𝑃𝑃 𝑛 (1 + 𝑐) shifted by one position, with the leading coefficient halved. The 𝛼 = 1 2 volume identity of Ehrenborg–Henning is the top case of this theorem, and the deletion recursion answers their request for a direct explanation of that identity in the present setting. Explicit closed forms for the top mixed volumes, a clique analogue with the volume formula Vol 𝑃𝐾 π‘š (1) = 21βˆ’π‘š (verified for π‘š ≀ 5), and open problems are included.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24337918
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The arithmetic of edge-threshold graph polytopes: Minkowski interpolation, transcendental spectra, and a mixed-volume shift theorem

Tianzhao Qiu
1 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

The arithmetic of edge-threshold graph polytopes: Minkowski interpolation, transcendental spectra, and a mixed-volume shift theorem

Tianzhao Qiu
preprint en

Abstract

Abstract For a finite graph 𝐺 and a parameter 𝑑, the edge-threshold polytope 𝑃𝐺(𝑑) = {π‘₯ ∈ [0, 1]𝑛 ∢ π‘₯𝑒 + π‘₯𝑣 ≀ 𝑑 for all 𝑒𝑣 ∈ 𝐸(𝐺)} interpolates between the fractional stable set polytope 𝑃𝐺(1) of 𝐺 and the unit cube. We prove three groups of results. (i) For 1 ≀ 𝑑 ≀ 2, 𝑃𝐺(1 + 𝑐) = (1 βˆ’ 𝑐)𝑃𝐺(1) + 𝑐[0, 1]𝑛 is a Minkowski interpolation; hence Vol 𝑃𝐺(1 + 𝑐) is a polynomial of degree at most 𝑛 whose Bernstein coefficients are the mixed volumes of 𝑃𝐺(1) and [0, 1]𝑛. (ii) For the path graph the transfer operator 𝑇𝑑 on 𝐿 2 [0, 1] has a fully explicit spectrum: the nonzero eigenvalues are πœ† = (2 βˆ’ 𝑑)/πœƒ, where πœƒ runs over the non-degenerate real roots of (2 βˆ’ 𝑑) cos πœƒ = (𝑑 βˆ’ 1)πœƒ(1 + sin πœƒ); if 𝑑 is algebraic then every nonzero eigenvalue is transcendental, by an elementary rigidity lemma based on the Hermite–Lindemann theorem; and the volume expansion carries an explicit remainder bound. (iii) We prove a subgraph identity and a vertex-deletion recursion for the coefficients π‘Žπ‘— (𝐺) = [πœ€π‘— ] Vol 𝑃𝐺(2 βˆ’ πœ€), and deduce a complete mixed-volume shift theorem: the Bernstein coefficients of Vol 𝑃𝐢𝑛+1 (1 + 𝑐) are those of Vol 𝑃𝑃 𝑛 (1 + 𝑐) shifted by one position, with the leading coefficient halved. The 𝛼 = 1 2 volume identity of Ehrenborg–Henning is the top case of this theorem, and the deletion recursion answers their request for a direct explanation of that identity in the present setting. Explicit closed forms for the top mixed volumes, a clique analogue with the volume formula Vol 𝑃𝐾 π‘š (1) = 21βˆ’π‘š (verified for π‘š ≀ 5), and open problems are included.

Zenodo (CERN European Organization for Nuclear Research)
Hunan University of Finance and Economics (CN)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon