pith. sign in

arxiv: 2604.14671 · v1 · submitted 2026-04-16 · 🧮 math.CO · cs.IT· math.IT

On the independence number of de Bruijn graphs

Pietro Majer , Matteo Novaga This is my paper

Pith reviewed 2026-05-10 11:22 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT
keywords de Bruijn graphsindependence numberasymptotic formulavariational problemphase reductionrotation orbitslifting theorem
0
0 comments X

The pith

The independence number of the de Bruijn graph B(k,q) equals λ_{k-1} q^k plus a smaller term, where λ_{k-1} is the value of a variational problem on the unit (k-1)-cube.

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

The paper derives the leading asymptotic growth of the largest set of length-k sequences over q symbols with no two adjacent under a single-symbol shift. This independence number controls the size of maximal codes with forbidden overlaps. The growth rate is shown to be governed by the supremum of a functional defined over all measurable labelings of the unit cube of dimension k-1. Separate analysis of the binary case for odd prime k produces explicit optimal constructions for k=11 and k=13 that lift to every alphabet size.

Core claim

The independence number α(k,q) of the de Bruijn graph B(k,q) satisfies α(k,q) = λ_{k-1} q^k + o(q^k), where λ_{k-1} arises as the maximum value of a variational problem on the unit (k-1)-dimensional cube. For odd prime k the binary case q=2 is reduced to a phase problem on rotation orbits; the resulting constructions for k=11 and k=13 are certified optimal and combine with an existing lifting theorem to yield exact formulas for α(11,q) and α(13,q) that hold for every q ≥ 2.

What carries the argument

The variational problem on the unit (k-1)-cube that computes the asymptotic density constant λ_{k-1}, together with phase reduction of independent sets onto rotation orbits in the binary case.

If this is right

  • For every fixed k the ratio α(k,q)/q^k converges to the constant λ_{k-1} as q tends to infinity.
  • The constant λ_3 for k=4 lies between 91/240 and 11/28.
  • Exact closed-form expressions for α(11,q) and α(13,q) are now known for every alphabet size q ≥ 2.
  • The same phase-reduction technique extends the known exact cases k=3,5,7 to k=11 and k=13.

Where Pith is reading between the lines

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

  • If the variational problem admits an explicit maximizer for additional k, the asymptotic constant could be evaluated in closed form.
  • The lifting theorem may apply to other small odd-prime orders once optimal binary constructions are found.
  • The cube variational formulation may transfer to density questions in other shift spaces or overlap graphs.

Load-bearing premise

The asymptotic density of maximum independent sets in the de Bruijn graph is exactly captured by the supremum of the variational functional over the (k-1)-cube.

What would settle it

An independent set in B(11,2) whose size exceeds the construction obtained from the phase reduction on rotation orbits would show that the claimed optimality and the resulting exact formula for all q are incorrect.

read the original abstract

We derive the asymptotic formula $\alpha(k,q)=\lambda_{k-1}q^k+o(q^k)$, where $\alpha(k,q)$ is the independence number of the de Bruijn graph $B(k,q)$, and $\lambda_{k-1}$ is a constant arising from a variational problem on the unit $(k-1)$-dimensional cube. When $k=4$, we show the bounds $91/240\le \lambda_3\le 11/28$. For odd prime $k$, we analyse the binary case $q=2$ via a phase reduction on rotation orbits. For $k=11$ and $k=13$ this yields certified optimal constructions, which combined with a lifting theorem by Lichiardopol give exact formulas for $\alpha(11,q)$ and $\alpha(13,q)$ for all $q\ge2$, extending the known cases $k=3,5,7$.

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.

Referee Report

2 major / 2 minor

Summary. The paper claims to derive the asymptotic formula α(k,q)=λ_{k-1}q^k + o(q^k) for the independence number of the de Bruijn graph B(k,q), with λ_{k-1} obtained from a variational problem on the unit (k-1)-cube. For k=4 it establishes the bounds 91/240 ≤ λ_3 ≤ 11/28. For odd primes k it analyzes the binary case via phase reduction on rotation orbits; for k=11 and k=13 this produces certified optimal constructions that, combined with Lichiardopol's lifting theorem, yield exact formulas for α(11,q) and α(13,q) for all q≥2, extending the known cases k=3,5,7.

Significance. If the variational characterization is shown to be tight and the binary constructions are verified as optimal, the work supplies both a general asymptotic framework and concrete exact results for previously open cases. The combination of variational methods, certified constructions, and the lifting theorem constitutes a substantive contribution to the study of independence numbers in de Bruijn graphs.

major comments (2)
  1. [derivation of the asymptotic formula] The central asymptotic claim rests on the variational problem on the (k-1)-cube correctly capturing the normalized independence density; the manuscript must supply the precise statement of the variational problem together with the argument establishing that the discrete maximum converges to its value (including justification of the o(q^k) error term).
  2. [phase reduction for odd prime k] For k=11 and k=13 the exact formulas depend on the binary constructions being optimal; the phase-reduction analysis must explicitly confirm that the constructed independent sets attain the variational supremum, so that the lifting theorem applies without gap.
minor comments (2)
  1. [Abstract] The notation o(q^k) should be accompanied by an explicit statement that the limit is taken as q→∞ with k fixed.
  2. [application of the lifting theorem] Clarify the precise statement of Lichiardopol's lifting theorem as used in the paper, including any hypotheses that must be verified for the given constructions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below, indicating the revisions we will incorporate.

read point-by-point responses

  1. Referee: [derivation of the asymptotic formula] The central asymptotic claim rests on the variational problem on the (k-1)-cube correctly capturing the normalized independence density; the manuscript must supply the precise statement of the variational problem together with the argument establishing that the discrete maximum converges to its value (including justification of the o(q^k) error term).

    Authors: We agree that the presentation of the asymptotic formula requires greater explicitness. In the revised manuscript we will state the variational problem in full: maximize the integral of a measurable density function f on the unit (k-1)-cube subject to the pointwise constraint that f(x) + f(y) ≤ 1 whenever x and y differ by a shift corresponding to an edge in the de Bruijn graph. We will then supply the convergence argument, showing that the normalized independence number of B(k,q) approaches this continuous supremum λ_{k-1} by a standard discretization-plus-approximation argument that controls the boundary and discretization errors, thereby justifying the o(q^k) remainder. These additions will appear in a new subsection of the main text. revision: yes

  2. Referee: [phase reduction for odd prime k] For k=11 and k=13 the exact formulas depend on the binary constructions being optimal; the phase-reduction analysis must explicitly confirm that the constructed independent sets attain the variational supremum, so that the lifting theorem applies without gap.

    Authors: We accept the need for an explicit optimality check. The phase-reduction constructions for k=11 and k=13 were obtained precisely so that their densities equal the value of the variational supremum on the cube for the binary case. In the revision we will add a short verification subsection that computes the achieved density of each construction and shows it coincides with the numerically or analytically obtained variational maximum; this equality removes any gap and permits direct application of Lichiardopol’s lifting theorem to obtain the exact formulas for all q ≥ 2. revision: yes

Circularity Check

0 steps flagged

No significant circularity; asymptotic and exact results rest on independent variational analysis and external theorem

full rationale

The paper defines λ_{k-1} via an external variational problem on the (k-1)-cube and derives the asymptotic α(k,q)=λ_{k-1}q^k + o(q^k) from it without fitting parameters to independence data. For k=4 the stated bounds follow directly from that variational setup. The exact formulas for k=11,13 arise from explicit constructions certified as optimal (via the variational upper bound) combined with Lichiardopol's cited lifting theorem, which is external and not a self-citation. No equation or claim reduces by construction to a fitted input, self-definition, or load-bearing self-citation chain. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the correctness of a variational characterization for the asymptotic density and on the applicability of the cited Lichiardopol lifting theorem to the phase-reduced constructions; no new entities are postulated and no parameters are fitted to data beyond the definition of λ.

axioms (1)
  • domain assumption The lifting theorem by Lichiardopol applies to the optimal constructions obtained via phase reduction on rotation orbits for odd prime k.
    Invoked to obtain exact formulas for all q ≥ 2 from the binary case.

pith-pipeline@v0.9.0 · 5452 in / 1637 out tokens · 36000 ms · 2026-05-10T11:22:28.857098+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Alhakim and M

    A. Alhakim and M. Akinwande,A recursive construction of nonbinary de Bruijn sequences, Des. Codes Cryptogr.60(2011), no. 2, 155–169

    work page 2011

  2. [2]

    van Aardenne-Ehrenfest and N

    T. van Aardenne-Ehrenfest and N. G. de Bruijn,Circuits and trees in oriented linear graphs, Simon Stevin28 (1951), 203–217. ON THE INDEPENDENCE NUMBER OF DE BRUIJN GRAPHS 33

    work page 1951

  3. [3]

    D. A. Cartwright, M. A. Cueto, and E. A. Tobis,The maximum independent sets of de Bruijn graphs of diameter 3, Electron. J. Combin.18(2011), no. 1, Paper P194

    work page 2011

  4. [4]

    D.-Z. Du, F. Cao, and D. F. Hsu,De Bruijn digraphs, Kautz digraphs, and their generalizations, inCombina- torial Network Theory, Kluwer Acad. Publ., Dordrecht, 1996, pp. 65–105

    work page 1996

  5. [5]

    N. G. de Bruijn,A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch.49(1946), 758–764

    work page 1946

  6. [6]

    Etzion,Sequences and the de Bruijn Graph: Properties, Constructions, and Applications, Academic Press, London, 2024

    T. Etzion,Sequences and the de Bruijn Graph: Properties, Constructions, and Applications, Academic Press, London, 2024

    work page 2024

  7. [7]

    Fredricksen and J

    H. Fredricksen and J. Maiorana,Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Math. 23(1978), no. 3, 207–210

    work page 1978

  8. [8]

    Fredricksen,A survey of full length nonlinear shift register cycle algorithms, SIAM Rev.24(1982), no

    H. Fredricksen,A survey of full length nonlinear shift register cycle algorithms, SIAM Rev.24(1982), no. 2, 195–221

    work page 1982

  9. [9]

    Lichiardopol,Independence number of de Bruijn graphs, Discrete Math.306(2006), no

    N. Lichiardopol,Independence number of de Bruijn graphs, Discrete Math.306(2006), no. 12, 1145–1160

    work page 2006

  10. [10]

    Majer and M

    P. Majer and M. Novaga,Monotone paths in random hypergraphs, Electron. J. Combin.19(2012), no. 2, Paper 17

    work page 2012

  11. [11]

    Ralston,De Bruijn sequences—a model example of the interaction of discrete mathematics and computer science, Math

    A. Ralston,De Bruijn sequences—a model example of the interaction of discrete mathematics and computer science, Math. Mag.55(1982), no. 3, 131–143

    work page 1982

  12. [12]

    W. T. Trotter and P. Winkler,Ramsey theory and sequences of random variables, Combin. Probab. Comput. 7(1998), no. 2, 221–238. Dipartimento di Matematica, Universit`a di Pisa, Largo Bruno Pontecorvo 5, 56127 Pisa, Italy Email address:pietro.majer@unipi.it Dipartimento di Matematica, Universit`a di Pisa, Largo Bruno Pontecorvo 5, 56127 Pisa, Italy Email ad...

    work page 1998