Antifactors in bipartite multigraphs

Louis Esperet

arxiv: 2205.14904 · v2 · submitted 2022-05-30 · 🧮 math.CO

Antifactors in bipartite multigraphs

Louis Esperet This is my paper

Pith reviewed 2026-05-24 11:42 UTC · model grok-4.3

classification 🧮 math.CO

keywords bipartite multigraphsantifactorsq-regular graphsperfect matchingsprime powersspanning subgraphsdegree conditions

0 comments

The pith

Bipartite multigraphs admit spanning subgraphs with degree 1 on one part and no degree 1 on the other when q is a prime power and the number of perfect matchings is not divisible by q.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends a 2020 theorem from simple graphs to multigraphs. It establishes that a q-regular bipartite multigraph has a spanning subgraph H in which all vertices on one side have degree exactly 1 and all on the other side have degree different from 1, provided q is a prime power and the number of perfect matchings is not a multiple of q. This arithmetic condition is shown to be necessary in the multigraph setting. The authors also conjecture a limiting distribution for the number of perfect matchings modulo q in random q-regular bipartite graphs.

Core claim

Under the stated conditions on q and the number of perfect matchings, every q-regular bipartite multigraph has a spanning subgraph with the required degree properties on each part of the bipartition.

What carries the argument

The extension of the antifactor existence result to multigraphs, which relies on algebraic or combinatorial properties available precisely when q is a prime power together with the non-divisibility of the number of perfect matchings.

Load-bearing premise

The algebraic or combinatorial properties that work for prime powers q in the simple graph case continue to apply in the multigraph setting.

What would settle it

A concrete q-regular bipartite multigraph where q is a prime power, the number of perfect matchings is not divisible by q, yet no spanning subgraph exists with degree 1 on one side and no degree 1 on the other.

read the original abstract

Let $G$ be a $q$-regular bipartite graph with bipartition $(U,V)$. It was proved by Lu, Wang, and Yan in 2020 that $G$ has a spanning subgraph $H$ such that each vertex of $U$ has degree 1 in $H$, and each vertex of $V$ has degree distinct from 1 in $H$. We extend the result to multigraphs, under the condition that $q$ is a prime power and the number of perfect matchings of $G$ is not divisible by $q$. The condition on the number of perfect matchings is necessary for multigraphs. We conclude with a conjecture on the limiting distribution of the number of perfect matchings modulo $q$ in a random bipartite $q$-regular graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends the 2020 antifactors result to multigraphs only when q is prime power and perfect matchings count is not divisible by q, with necessity shown for the multigraph case.

read the letter

The main point is that this paper extends the Lu-Wang-Yan antifactors theorem from simple bipartite graphs to multigraphs, but only under the conditions that q is a prime power and the number of perfect matchings is not divisible by q. It also proves that the non-divisibility condition is necessary once multiple edges are allowed, which was not an issue in the simple-graph setting. This fills a specific gap left by the earlier work. The extension itself is the new content, along with the necessity argument and the final conjecture on the limiting distribution of the number of perfect matchings modulo q in random q-regular bipartite graphs. The paper states the conditions clearly and gives counterexamples to show why non-divisibility matters for multigraphs. That necessity part is handled directly and adds value. The prime-power restriction is a real boundary on the result. The proof apparently relies on algebraic features that are available precisely when q is a prime power, so the statement does not reach all q. The paper does not overclaim here. The conjecture is left open, which is fine for a short note but means it functions more as a suggestion than a resolved claim. This is aimed at people working in matching theory and factorizations in graphs. A reader who already knows the 2020 paper will see the incremental advance and the necessity detail. The work is coherent on its own terms and has enough new verifiable content to go through peer review rather than a desk reject.

Referee Report

2 major / 1 minor

Summary. The paper extends the 2020 result of Lu, Wang, and Yan showing that every q-regular bipartite graph G with bipartition (U,V) admits a spanning subgraph H in which every vertex in U has degree 1 and every vertex in V has degree ≠1. The extension asserts that the same conclusion holds for multigraphs provided q is a prime power and the number of perfect matchings of G is not divisible by q; the authors further claim that the non-divisibility condition is necessary in the multigraph setting. The manuscript concludes with a conjecture on the limiting distribution of the number of perfect matchings modulo q for a random q-regular bipartite graph.

Significance. If verified, the result would usefully enlarge the scope of antifactor theorems from simple graphs to multigraphs while isolating an algebraic condition (q prime power) and a combinatorial obstruction (matching count divisible by q). The necessity claim for multigraphs distinguishes the multigraph case from the simple-graph case and may prompt further work on when such obstructions appear. The conjecture on the modular distribution of perfect matchings is a natural probabilistic counterpart that could be of independent interest in enumerative combinatorics.

major comments (2)

[Abstract] Abstract: the necessity of the condition that the number of perfect matchings is not divisible by q is asserted for multigraphs, yet no argument, counter-example, or reference establishing necessity is supplied; this claim is load-bearing for the stated extension.
[Abstract] Abstract: the extension to multigraphs is stated to hold precisely when q is a prime power, but the manuscript supplies no indication of how the algebraic or combinatorial properties used in the 2020 simple-graph proof transfer to the multigraph setting under this hypothesis.

minor comments (1)

[Abstract] The abstract mentions a conjecture on the limiting distribution but gives no supporting heuristic, numerical evidence, or reference to related work on perfect-matching enumeration modulo primes.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's comments on our manuscript extending the antifactor result to multigraphs. We respond to the major comments as follows.

read point-by-point responses

Referee: [Abstract] Abstract: the necessity of the condition that the number of perfect matchings is not divisible by q is asserted for multigraphs, yet no argument, counter-example, or reference establishing necessity is supplied; this claim is load-bearing for the stated extension.

Authors: The referee correctly notes that the manuscript asserts necessity without supplying supporting material. We will add a counterexample in the revised version to establish that the non-divisibility condition is indeed necessary for multigraphs. This example will show a q-regular bipartite multigraph with the number of perfect matchings divisible by q for which no such H exists. revision: yes
Referee: [Abstract] Abstract: the extension to multigraphs is stated to hold precisely when q is a prime power, but the manuscript supplies no indication of how the algebraic or combinatorial properties used in the 2020 simple-graph proof transfer to the multigraph setting under this hypothesis.

Authors: We agree that the abstract does not indicate the role of the prime power condition. The proof relies on linear algebra over the finite field F_q, which necessitates q being a prime power. We will revise the abstract to reference this and include a brief explanation in the introduction detailing how the original proof's algebraic components extend to the multigraph case under this condition. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript extends the 2020 theorem of Lu, Wang and Yan (distinct authors) to multigraphs when q is a prime power and the number of perfect matchings is not divisible by q. The abstract states the necessity of the latter condition for multigraphs but supplies no equations, lemmas or derivation steps that reduce any claim to a fitted parameter, self-definition or self-citation chain. No load-bearing step collapses by construction to its own inputs; the cited 2020 result is external and the extension is presented as relying on algebraic properties available precisely for prime-power q. This is the normal case of an honest non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard facts about bipartite graphs, perfect matchings, and the algebraic structure of prime-power regular graphs; no new entities or fitted parameters are introduced in the abstract.

axioms (1)

standard math Bipartite multigraphs admit perfect matchings whose count can be considered modulo q
Invoked when stating the non-divisibility condition

pith-pipeline@v0.9.0 · 5652 in / 1237 out tokens · 17240 ms · 2026-05-24T11:42:35.310622+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

Alon, Combinatorial Nullstellensatz, Combin

N. Alon, Combinatorial Nullstellensatz, Combin. Prob. Comput. 8 (1999), 7--29

work page 1999
[2]

N. Alon, S. Friedland and G. Kalai, Every 4-regular graph plus an edge contains a 3-regular subgraph, J. Combinatorial Theory, Ser. B 37 (1984), 92--93

work page 1984
[3]

N. Alon, S. Haber and M. Krivelevich, The number of F -matchings in almost every tree is a zero residue, Electronic J. Combin. 18 (2011), P30, 10pp

work page 2011
[4]

Brinkmann, Fast generation of cubic graphs, J

G. Brinkmann, Fast generation of cubic graphs, J. Graph Theory, 23(2) (1996), 139--149

work page 1996
[5]

Brinkmann, K

G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. M\'elot, House of Graphs: a database of interesting graphs. Discrete Applied Math. 161 (2013), 311--314. Available at http://hog.grinvin.org/

work page 2013
[6]

Goedgebeur, A counterexample to the pseudo

J. Goedgebeur, A counterexample to the pseudo

work page
[7]

H. Lu, W. Wang, and J. Yan, Anti-factors of Regular Bipartite Graphs, Discrete Mathematics & Theoretical Computer Science 22(1) (2020)

work page 2020
[8]

Seb o , Ear-Slicing for Matchings in Hypergraphs, Graphs Combin

A. Seb o , Ear-Slicing for Matchings in Hypergraphs, Graphs Combin. 36 (2020), 1947--1951

work page 2020
[9]

Tashkinov, Three regular parts of four regular graphs, Math

V.A. Tashkinov, Three regular parts of four regular graphs, Math. Notes 36 (1984), 612--623

work page 1984

[1] [1]

Alon, Combinatorial Nullstellensatz, Combin

N. Alon, Combinatorial Nullstellensatz, Combin. Prob. Comput. 8 (1999), 7--29

work page 1999

[2] [2]

N. Alon, S. Friedland and G. Kalai, Every 4-regular graph plus an edge contains a 3-regular subgraph, J. Combinatorial Theory, Ser. B 37 (1984), 92--93

work page 1984

[3] [3]

N. Alon, S. Haber and M. Krivelevich, The number of F -matchings in almost every tree is a zero residue, Electronic J. Combin. 18 (2011), P30, 10pp

work page 2011

[4] [4]

Brinkmann, Fast generation of cubic graphs, J

G. Brinkmann, Fast generation of cubic graphs, J. Graph Theory, 23(2) (1996), 139--149

work page 1996

[5] [5]

Brinkmann, K

G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. M\'elot, House of Graphs: a database of interesting graphs. Discrete Applied Math. 161 (2013), 311--314. Available at http://hog.grinvin.org/

work page 2013

[6] [6]

Goedgebeur, A counterexample to the pseudo

J. Goedgebeur, A counterexample to the pseudo

work page

[7] [7]

H. Lu, W. Wang, and J. Yan, Anti-factors of Regular Bipartite Graphs, Discrete Mathematics & Theoretical Computer Science 22(1) (2020)

work page 2020

[8] [8]

Seb o , Ear-Slicing for Matchings in Hypergraphs, Graphs Combin

A. Seb o , Ear-Slicing for Matchings in Hypergraphs, Graphs Combin. 36 (2020), 1947--1951

work page 2020

[9] [9]

Tashkinov, Three regular parts of four regular graphs, Math

V.A. Tashkinov, Three regular parts of four regular graphs, Math. Notes 36 (1984), 612--623

work page 1984