Pair-Trace Absorption Certificates for Regular Induced Subgraphs

2026

Read Pair-Trace Absorption Certificates for Regular Induced Subgraphs (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23882.txt.

Introduction

Ramos, Hulak, and de Queiroz study fixed-core absorption for regular induced subgraphs. Q-modularity means all induced degrees agree modulo q, and the question is when deleting equal-trace q-tuples from outside a retained core can make the core a 2q-modular witness. Their key result is a finite absorption-or-obstruction certificate, plus an exact formula for the deletion-tail quotient. A connected graph of heavy traces plus one odd trace, when needed, absorbs every top-bit defect.

Catalog record

YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54219
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.23882

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pair-Trace Absorption Certificates for Regular Induced Subgraphs Abstract We study a fixed-core absorption problem for regular induced subgraphs. A set is q q -modular if all induced degrees are congruent modulo q q . Given a q q -modular witness A A and a retained core U ⊆ A U\subseteq A , we ask when deleting equal-trace q q -tuples from A ∖ U A\setminus U synchronizes the degrees on U U modulo 2 ​ q 2q . 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 n_{B}-n_{U\setminus B} , not sums. Equal-trace q q -tuples absorb exactly the span of their trace classes in 𝔽 2 U / ⟨ 𝟏 U ⟩ \mathbb{F}_{2}^{U}/\langle\mathbf{1}_{U}\rangle . In particular, a connected graph of q q -heavy two-point traces on U U , together with one odd trace when | U | |U| is even, absorbs every top-bit defect by deleting at most q ⁡ ( | U | − 1 ) q(|U|-1) tail vertices. If fixed-core absorption fails, the obstruction is an explicit even parity cut of U U . We also record the parity base, the terminal modular criterion, and a conditional modular-witness threshold theorem explaining the relevance to the Erdős–Fajtlowicz–Staton problem. The paper does not claim to solve that problem or to improve the general lower bound for F ⁡ ( n ) F(n) . keywords regular induced subgraphs, modular degree conditions, dyadic lifting, graph Ramsey theory \newauthor Arthur F. RamosA. F. RamosMicrosoft, Redmond, WA, USA[[email protected]] \newauthor David Barros HulakD. B. HulakIndependent researcher[[email protected]] \newauthor Ruy J. G. B. de QueirozR. J. G. B. de QueirozCentro de Informática Universidade Federal de Pernambuco Recife, Brazil[[email protected]] [Pair-Trace Certificates] \classnbr 05C35, 05C55, 05C50 1 Introduction All graphs in this paper are finite, simple, and undirected. For a graph G and a set S\subseteq V(G) , write G[S] for the induced subgraph on S , and write \deg_{S}(v) for the degree of v inside G[S] . Define f(G)=\max\{|S|:G[S]\text{ is regular}\},\qquad F(n)=\min_{|V(G)|=n}f(G). Equivalently, F(n) is the largest integer k such that every n -vertex graph contains a regular induced subgraph on at least k vertices. The Erdős–Fajtlowicz–Staton problem asks whether \frac{F(n)}{\log n}\to\infty. The problem appears in work of Erdős and in the finite Ramsey-number formulation studied by Fajtlowicz, McColgan, Reid, and Staton [ Erdos1993 , FMRS1995 ] ; it is also discussed in [ ChungGraham1998 ] . See also the later work on nearly regular induced subgraphs [ AKS2008 ] , repeated degrees [ CaroYuster2020 ] , random graphs [ KrivelevichSudakovWormald2011 ] , and recent regular-induced Ramsey numbers [ DysonMcKay2026 ] . The classical Ramsey argument gives F(n)\geq c\log n , since every graph contains a clique or an independent set of logarithmic order. The exact regular induced version is much more rigid than approximate regularity or repeated-degree variants: deleting a vertex changes the degree of every surviving neighbor. The present paper is not a new Ramsey-number computation, a result on nearly regular induced subgraphs, or a repeated-degree theorem. Its object is a modular obstruction calculus for lifting induced degree congruences on a fixed core. The Ramsey-type threshold is included only to explain why such local lifting certificates are relevant. This paper develops a modular approach to the problem. The guiding idea is to first find a large induced set whose degrees are equal modulo 2 , then lift the congruence to modulo 4 , then to modulo 8 , and so on. Once a set U of order at most q has all internal degrees congruent modulo q , the induced graph G[U] is genuinely regular. The main purpose of the paper is to give a graph-theoretic certificate for one fixed-core dyadic absorption step. We also isolate the exact kind of lifting theorem that would imply a positive answer to the Erdős–Fajtlowicz–Staton problem, but the paper’s proved results are the local obstruction and absorption theorems. The resulting fixed-core mechanism has a simple three-part form. First, a proposed dyadic lift has an exact quotient obstruction. Second, a connected q -heavy pair-trace reservoir forces the rank-rich condition and hence absorbs every top-bit defect. Third, if equal-trace absorption fails for the fixed core, then failure is witnessed by an explicit even parity cut. 1.1 Main results The main results of the paper are as follows. • Conditional threshold theorem. If the dyadic lift from 2 to 4 , and the lifts from q to 2q for q\geq 4 , can be carried out with polynomial loss and exact modular-witness output size, then F(n)/\log n\to\infty . This is Theorem 4.1 . • Exact tail obstruction. The deletion-tail obstruction is the quotient class of \rho_{R} modulo constant functions. In complement-orbit coordinates it is controlled by oriented differences n_{B}-n_{U\setminus B} , not by sums. This is Proposition 6.1 and Corollary 6.3 . • Complete twin-block absorption criterion. For a fixed core U , equal-trace q -tuples can correct precisely the span of their trace classes in \mathbb{F}_{2}^{U}/\langle\mathbf{1}_{U}\rangle . This gives an if-and-only-if linear-algebra criterion for one absorption step. This is Theorem 8.13 . • Rank-rich and structured reservoir absorption. If the traces occurring at multiplicity at least q span \mathbb{F}_{2}^{U}/\langle\mathbf{1}_{U}\rangle , then every top-bit defect on U can be synchronized by deleting at most q(|U|-1) tail vertices. A connected q -heavy pair-trace graph, together with one odd trace when |U| is even, is a concrete graph-theoretic sufficient condition for this rank-rich hypothesis. A separate random trace-reservoir theorem, with an explicit uniform-distribution bound, gives a model/certification version. These are Theorems 8.15 , 8.17 , 8.22 , and Corollary 8.24 . • Dual obstruction certificate. Failure of twin-block absorption is equivalent to the existence of a linear functional that annihilates all available trace classes but detects the top-bit defect. Equivalently, there is an even subset Y\subseteq U meeting every available trace in even parity while meeting the top-bit defect in odd parity. The same linear algebra gives an algorithm that outputs either a deletion certificate or this parity cut. This is Corollary 8.28 and Theorem 8.30 . • Calibration classes. Perfect graphs contain regular induced subgraphs of order at least \sqrt{n} , and graphs of neighborhood diversity at most t contain regular induced subgraphs of order at least n/t . These elementary calibrations show that hard examples must have neither large homogeneous sets nor low trace complexity. 2 Modular witnesses Definition 2.1 . For an integer q\geq 1 , a set U\subseteq V(G) is called q -modular if \deg_{U}(u)\equiv\deg_{U}(v)\pmod{q} for all u,v\in U . Lemma 2.2 (Terminal modular criterion) . If U is q -modular and |U|\leq q , then G[U] is regular. Proof 2.3 . Every degree in G[U] lies in the interval [0,|U|-1] , whose length is at most q-1 . Two integers in this interval that are congruent modulo q must be equal. Hence all degrees in G[U] are equal. 3 The parity base The dyadic program starts from the following standard parity fact. Lemma 3.1 (Parity partition) . Every graph G on n vertices contains an induced subgraph on at least n/2 vertices in which all degrees are even. Proof 3.2 . Work over

Read the complete text