PreprintarXiv licencearXiv
The Genus of Bipartite Kneser Graphs
Abstract
We determine the orientable genus of an infinite family of bipartite Kneser graphs. The graph H(h,2) has two copies of the two-element subsets of [h], with opposite-class vertices adjacent when the corresponding subsets are disjoint. For every prime h>3 with h≡3pmod8, we prove γ(H(h,2))=1−(h(h−1))/2 +(h(h−1)(h−2)(h−3))/16. Euler's formula gives this lower bound, with equality for a quadrangulation. We construct a vertex-transitive orientable quadrangulation using an odd-order affine group that acts simply transitively on the two-element subsets. This gives an infinite family satisfying Pisanski's conjecture on quadrilateral embeddings of regular bipartite graphs.
Related
BibTeX
@misc{ulrigg2026genus,
title = {{The Genus of Bipartite Kneser Graphs}},
author = {Austin Ulrigg and Alexander Metzger},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03159},
eprint = {2610.03159},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03159},
}
RIS
TY - UNPB
TI - The Genus of Bipartite Kneser Graphs
AU - Austin Ulrigg
AU - Alexander Metzger
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03159
UR - https://arxiv.org/abs/2610.03159
AB - We determine the orientable genus of an infinite family of bipartite Kneser graphs. The graph H(h,2) has two copies of the two-element subsets of [h], with opposite-class vertices adjacent when the corresponding subsets are disjoint. For every prime h>3 with h≡3pmod8, we prove γ(H(h,2))=1−(h(h−1))/2 +(h(h−1)(h−2)(h−3))/16. Euler's formula gives this lower bound, with equality for a quadrangulation. We construct a vertex-transitive orientable quadrangulation using an odd-order affine group that acts simply transitively on the two-element subsets. This gives an infinite family satisfying Pisanski's conjecture on quadrilateral embeddings of regular bipartite graphs.
ER -