PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
August 26, 20260 citationsOpen Access

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

View Full Paper
QWQihang WangDZDongming Zhang

Key Points

  • To characterize vertex–facet nonincidence assignments and identify structural deficiency obstructions beyond free joins in multidimensional convex polytopes.
  • Derived an exact face formula for the matching number and decomposed assignment deficiency across connected components in vertex–facet nonincidence graphs.
  • Developed a transfer theorem for nondegenerate vertex-preserving one-point extensions evaluated via rooted horizon graphs under strict visible/retained conditions.
  • Generated rational counterexamples beyond nontrivial free joins for every dimension d ≥ 7, including balanced deficiency-one polytopes with 33 vertices and 33 facets in dimension seven.
  • Established that factor-witnessed strict join-stack obstructions require at least 2d + 6 vertices and facets, yielding balanced constructions of sizes 2d + 10 (even d ≥ 18) and 2d + 12 (odd d ≥ 19) with class optimum η_d = 2d + O(1).

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).

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Wang et al. (2026) studied this question.

synapsesocial.com/papers/6a8e9b79451774b83f3b43afhttps://doi.org/10.5281/zenodo.22082655
Ask AI
Helpful
Bookmark
Share
View Full Paper