arxiv: 2604.23882 · v1 · submitted 2026-04-26 · 🧮 math.CO

Recognition: unknown

Pair-Trace Absorption Certificates for Regular Induced Subgraphs

Arthur F. Ramos , David Barros Hulak , Ruy J. G. B. de Queiroz

Authors on Pith no claims yet

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

classification 🧮 math.CO

keywords regular induced subgraphsq-modular setsabsorption certificatestrace classeseven parity cutsfixed-core absorptionErdős–Fajtlowicz–Staton problem

0 comments

The pith

A connected graph of q-heavy two-point traces on core U absorbs every top-bit defect by deleting at most q(|U|-1) tail vertices, or else an even parity cut of U blocks it.

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

The paper studies a fixed-core absorption problem: given a q-modular witness set A and retained core U inside A, when can deletions of equal-trace q-tuples from A minus U turn U into a 2q-modular witness for regular induced subgraphs. It supplies a finite absorption-or-obstruction certificate together with an exact quotient formula that expresses the deletion-tail obstruction in complement-orbit coordinates via oriented differences rather than sums. Equal-trace q-tuples absorb precisely the span of their trace classes inside the vector space F_2^U modulo the all-ones vector. In particular, when the traces form a connected graph of q-heavy two-point traces on U (plus one odd trace if |U| is even), every top-bit defect is absorbed after at most q(|U|-1) deletions. Failure produces an explicit even-parity cut of U as the obstruction.

Core claim

The central claim is that a connected graph of q-heavy two-point traces on U, together with one odd trace when |U| is even, absorbs every top-bit defect by deleting at most q(|U|-1) tail vertices; if absorption fails, the obstruction is an explicit even parity cut of U. This follows from the exact quotient formula for the deletion-tail obstruction in complement-orbit coordinates (using oriented differences n_B - n_{U∖B}) and from the fact that equal-trace q-tuples absorb exactly the span of their trace classes in F_2^U / 1_U. The paper also records the parity base, the terminal modular criterion, and a conditional modular-witness threshold theorem that explains relevance to the Erdős–Fajtlow

What carries the argument

The absorption-or-obstruction certificate built from the quotient formula in complement-orbit coordinates, where equal-trace q-tuples absorb the span of trace classes in F_2^U modulo the all-ones vector.

If this is right

The parity base and terminal modular criterion follow directly from the certificate.
A conditional modular-witness threshold theorem holds and accounts for the link to the Erdős–Fajtlowicz–Staton problem.
The paper records these consequences without claiming a solution or improved general lower bound for that problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same oriented-difference formula may apply to absorption problems in other induced-subgraph settings beyond the q-modular case.
The even-parity-cut obstruction supplies a concrete search target for computational checks on small cores U.

Load-bearing premise

The starting set A is q-modular with retained core U and deletions are limited to equal-trace q-tuples whose traces lie inside the span described in F_2^U modulo the all-ones vector.

What would settle it

An explicit counter-example q-modular set A with core U in which the connected q-heavy two-point traces absorb strictly more (or fewer) than q(|U|-1) defects, or in which the obstruction is not an even-parity cut of U.

read the original abstract

We study a fixed-core absorption problem for regular induced subgraphs. A set is q-modular if all induced degrees are congruent modulo q. Given a q-modular witness A and a retained core U subset A, we ask when deleting equal-trace q-tuples from A\U can make U into a 2q-modular witness. The main contribution is a finite absorption-or-obstruction certificate. We give an exact quotient formula for the deletion-tail obstruction in complement-orbit coordinates: the correct expression uses oriented differences n_B - n_{U\B}, not sums. Equal-trace q-tuples absorb exactly the span of their trace classes in F_2^U / 1_U. In particular, a connected graph of q-heavy two-point traces on U, together with one odd trace when |U| is even, absorbs every top-bit defect by deleting at most q(|U|-1) tail vertices. If fixed-core absorption fails, the obstruction is an explicit even parity cut of U. We also record the parity base, the terminal modular criterion, and a conditional modular-witness threshold theorem explaining the relevance to the Erdos-Fajtlowicz-Staton problem. The paper does not claim to solve that problem or to improve the general lower bound for F(n).

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

The paper gives a concrete finite certificate for absorbing defects into a 2q-modular core via bounded tail deletions or else an explicit even-parity-cut obstruction, using an oriented-difference quotient over F2.

read the letter

The punchline is that this work supplies an explicit absorption-or-obstruction certificate for the fixed-core problem. When a connected graph of q-heavy two-point traces on U is present, plus one odd trace if |U| is even, you can clear every top-bit defect by deleting at most q(|U|-1) tail vertices. If that fails, the blocker is a concrete even-parity cut of U. The exact quotient formula uses oriented differences n_B - n_{U/B} rather than sums, and the equal-trace q-tuples absorb precisely the span they generate in F2^U / 1_U. That is the main technical contribution, and it is new in this modular setting.

Referee Report

0 major / 3 minor

Summary. The paper develops a fixed-core absorption framework for q-modular witnesses of regular induced subgraphs. Given a q-modular set A with retained core U, it characterizes when deletions of equal-trace q-tuples from A minus U can produce a 2q-modular witness on U. The central results are an exact quotient formula for the deletion-tail obstruction expressed in complement-orbit coordinates via oriented differences n_B - n_{U/B} (rather than sums), the statement that equal-trace q-tuples absorb precisely the span of their trace classes in F_2^U / 1_U, and the concrete absorption certificate: a connected graph of q-heavy two-point traces on U, augmented by one odd trace when |U| is even, absorbs all top-bit defects using at most q(|U|-1) deletions. When absorption fails, the obstruction is an explicit even-parity cut of U. Additional material records the parity base, the terminal modular criterion, and a conditional modular-witness threshold theorem relating the work to the Erdős–Fajtlowicz–Staton problem (without claiming a solution or improved lower bound).

Significance. If the derivations hold, the work supplies explicit, finite certificates and linear-algebraic obstructions for a natural absorption question in extremal graph theory. The use of the quotient space F_2^U / 1_U together with the spanning-tree deletion bound q(|U|-1) yields a parameter-light, connectivity-based guarantee that is directly falsifiable from the trace graph. The dual obstruction statement as an even-parity cut is the expected matroidal counterpart. These tools may assist systematic study of modular witnesses without resolving the full Erdős–Fajtlowicz–Staton conjecture.

minor comments (3)

The definitions of 'q-heavy two-point trace', 'top-bit defect', and 'complement-orbit coordinates' appear before the main theorems but would benefit from a short illustrative example with |U|=3 or |U|=4 to fix notation.
The statement of the quotient formula (oriented differences rather than sums) is given in the abstract and introduction; a self-contained derivation or reference to the precise linear-algebraic identity used would improve readability.
The connectivity hypothesis on the two-point trace graph is load-bearing for the deletion bound; a brief remark on how this connectivity follows from the initial q-modular witness (or when it must be checked separately) would clarify the scope of the certificate.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful and positive evaluation of our manuscript. The summary accurately reflects the fixed-core absorption framework, the quotient formula using oriented differences in complement-orbit coordinates, the linear-algebraic absorption certificates in F_2^U / 1_U, and the connection to the Erdős–Fajtlowicz–Staton problem without overclaiming. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained linear algebra

full rationale

The paper's central claims rest on the vector space structure of F_2^U / 1_U and the spanning property of the two-point trace graph. Connectivity of that graph ensures the vectors e_i + e_j generate the (|U|-1)-dimensional quotient, and adjoining one odd trace completes the basis when |U| is even; the deletion bound q(|U|-1) is then the length of a spanning tree in this graph. The obstruction characterization as an even-parity cut is the orthogonal complement under the standard dot product. These steps follow directly from the definitions of q-modular sets, equal-trace tuples, and the quotient formula without any fitted parameters, self-citations used as load-bearing uniqueness theorems, or reductions of predictions to their own inputs. The argument is internally consistent and does not rely on renaming known results or smuggling ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The paper rests on standard mathematical axioms of graph theory and finite-field linear algebra with no data-fitted free parameters; new entities are definitional rather than postulated physical objects.

axioms (2)

standard math Induced subgraphs preserve degree congruences modulo q when the set is q-modular
Invoked in the definition of q-modular and 2q-modular witnesses throughout the absorption problem.
domain assumption The vector space F_2^U / 1_U correctly models trace classes under deletion
Central to the statement that equal-trace q-tuples absorb exactly the span of their trace classes.

invented entities (2)

q-modular witness no independent evidence
purpose: A set in which all induced degrees are congruent modulo q
Core definitional object for the fixed-core absorption problem; no independent evidence supplied beyond the paper's framework.
deletion-tail obstruction no independent evidence
purpose: The explicit combinatorial object that certifies when absorption fails
Characterized as an even parity cut; introduced to complete the absorption-or-obstruction dichotomy.

pith-pipeline@v0.9.0 · 5535 in / 1801 out tokens · 54090 ms · 2026-05-08T05:42:27.367426+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 1 canonical work pages · 1 internal anchor

[1]

N. Alon, M. Krivelevich and B. Sudakov,Large nearly regular induced sub- graphs, SIAM J. Discrete Math.22(2008) 1325–1337

2008
[2]

Caro and R

Y. Caro and R. Yuster,Induced subgraphs with many repeated degrees, Dis- crete Math.343(2020) 111828

2020
[3]

Chung and R.L

F.R.K. Chung and R.L. Graham, Erd˝ os on Graphs: His Legacy of Unsolved Problems (A K Peters, Wellesley, MA, 1998)

1998
[4]

Ramsey numbers for regular induced subgraphs

P.W. Dyson and B.D. McKay,Ramsey numbers for regular induced subgraphs (2026), arXiv:2604.08215 [math.CO]

work page internal anchor Pith review Pith/arXiv arXiv 2026
[5]

Erd˝ os,Some of my favorite solved and unsolved problems in graph theory, Quaestiones Math.16(1993) 333–350

P. Erd˝ os,Some of my favorite solved and unsolved problems in graph theory, Quaestiones Math.16(1993) 333–350

1993
[6]

Fajtlowicz, T

S. Fajtlowicz, T. McColgan, T. Reid and W. Staton,Ramsey numbers for induced regular subgraphs, Ars Combin.39(1995) 149–154

1995
[7]

Krivelevich, B

M. Krivelevich, B. Sudakov and N. Wormald,Regular induced subgraphs of a random graph, Random Structures Algorithms38(2011) 235–250

2011
[8]

Lampis,Algorithmic meta-theorems for restrictions of treewidth, Algo- rithmica64(2012) 19–37

M. Lampis,Algorithmic meta-theorems for restrictions of treewidth, Algo- rithmica64(2012) 19–37. This article is distributed under the terms of the Creative Commons Attribution- NonCommercial-NoDerivatives 4.0 International License https://creativecommons.org/licens- es/by-nc-nd/4.0/

2012