Vertex–Facet Assignment Obstructions Beyond Free Joins: Exact Defect, Transfer, and Constant-Additive Constructions

We study vertex–facet assignments for convex polytopes through their vertex–facet nonincidence graphs. We derive an exact face formula for the matching number and decompose assignment deficiency across connected components. For nondegenerate vertex-preserving one-point extensions in the strict visible/retained setting, we prove a transfer theorem in which connectedness is characterized by a rooted horizon graph and surviving faces yield explicit matching bounds. This produces, for every d ≥ 7, rational counterexamples beyond nontrivial free joins, including balanced deficiency-one examples with 33 vertices and 33 facets in dimension seven and infinitely many pairwise nonisomorphic families with exact matching numbers. Within the factor-witnessed strict join-stack class, every obstructive construction has at least 2d + 6 vertices and 2d + 6 facets, while balanced constructions of sizes 2d + 10 for even d ≥ 18 and 2d + 12 for odd d ≥ 19 imply the class optimum η_d = 2d + O(1).

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-08-24
DOI
https://doi.org/10.5281/zenodo.22082655
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Vertex–Facet Assignment Obstructions Beyond Free Joins: Exact Defect, Transfer, and Constant-Additive Constructions

Dongming Zhang, Qihang Wang
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

Vertex–Facet Assignment Obstructions Beyond Free Joins: Exact Defect, Transfer, and Constant-Additive Constructions

Dongming Zhang, Qihang Wang
preprint en

Abstract

We study vertex–facet assignments for convex polytopes through their vertex–facet nonincidence graphs. We derive an exact face formula for the matching number and decompose assignment deficiency across connected components. For nondegenerate vertex-preserving one-point extensions in the strict visible/retained setting, we prove a transfer theorem in which connectedness is characterized by a rooted horizon graph and surviving faces yield explicit matching bounds. This produces, for every d ≥ 7, rational counterexamples beyond nontrivial free joins, including balanced deficiency-one examples with 33 vertices and 33 facets in dimension seven and infinitely many pairwise nonisomorphic families with exact matching numbers. Within the factor-witnessed strict join-stack class, every obstructive construction has at least 2d + 6 vertices and 2d + 6 facets, while balanced constructions of sizes 2d + 10 for even d ≥ 18 and 2d + 12 for odd d ≥ 19 imply the class optimum η_d = 2d + O(1).

Zenodo (CERN European Organization for Nuclear Research)
Peking University (CN)
Advanced Graph Theory Research
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.

Vertex–Facet Assignment Obstructions Beyond Free Joins: Exact Defect, Transfer, and Constant-Additive Constructions — Dongming Zhang, Qihang Wang · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS