Perfecting the Line Graph

Hartosh Singh Bal · 2025

Read Perfecting the Line Graph by Hartosh Singh Bal (2025) 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-2507-23231.txt.

Introduction

Bal, writing solo in twenty twenty-five, introduced a graph construction that always yields perfect graphs. A graph's line graph turns edges into vertices; it usually contains forbidden patterns. Bal instead takes the line graph of a graph's canonical bipartite double cover, producing a doubled edge-stage lift.

The construction's spectrum splits neatly into the ordinary line graph's spectrum plus a canonical signed refinement, so edge information is retained rather than lost. For every input graph the lift is perfect, meaning its coloring number equals its clique size in all induced subgraphs, and it is also claw-free and box-perfect. For regular inputs he gives an explicit spectral formula with control of the second eigenvalue and gap. Complete graphs and Paley graphs supply concrete families illustrating the theory.

Catalog record

CREATORHartosh Singh Bal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-23231

Browse the full library · About the Tower of Babel

Full text

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

Perfecting the Line Graph Hartosh Singh Bal Abstract This paper introduces two canonical constructions that transform arbitrary finite graphs into perfect graphs: the symmetric lift HL 2 ′ ​ ( G ) \mathrm{HL}^{\prime}_{2}(G) , which is purely structural and label-invariant, and the ordered lift HL 2 ​ ( G ) \mathrm{HL}_{2}(G) , which depends explicitly on vertex labeling and encodes directional information. Both lifts arise as line graphs of bipartite double covers and are box-perfect. The symmetric lift HL 2 ′ ​ ( G ) \mathrm{HL}^{\prime}_{2}(G) forms a canonical 2-cover of the line graph L ⁡ ( G ) L(G) . This involution decomposes HL 2 ′ ​ ( G ) \mathrm{HL}^{\prime}_{2}(G) into symmetric and antisymmetric components: the symmetric part recovers L ⁡ ( G ) L(G) , while the antisymmetric part yields a signed graph L − ​ ( G ) L^{-}(G) , the antisymmetric line graph, with +1/-1 edges encoding consistent vs. crossed overlaps. Thus, all adjacency and Laplacian eigenvalues of L ⁡ ( G ) L(G) , with multiplicities, appear within those of HL 2 ′ ​ ( G ) \mathrm{HL}^{\prime}_{2}(G) , despite L ⁡ ( G ) L(G) typically not being a subgraph. For regular graphs such as Paley graphs, this yields infinite families of sparse, highly structured regular and box-perfect expanders that also retain large cliques. The lift retains much of the spectral expansion of the base while improving the combinatorial expansion. Much the same behavior is observed with random regular base graphs, allowing for the possibility of the study of box-perfect random regular graphs. Finally, we generalize these constructions to parameterized lifts HL r , d ​ ( G ) \mathrm{HL}_{r,d}(G) and HL r , d ′ ​ ( G ) \mathrm{HL}_{r,d}^{\prime}(G) defined on ordered r r -tuples connected by Hamming distance constraints, which structurally encode the base graph and remain box-perfect. † † footnotetext: 2020 Mathematics Subject Classification . 05C75, 05C50, 05C69, 68Q17, 68R10. 1 Introduction Perfect graphs occupy a central place in graph theory. Their defining property—that in every induced subgraph, the chromatic number equals the clique number—makes them structurally elegant and algorithmically tractable [ 10 , 15 ] . Yet, despite their appeal, the known families of perfect graphs tend to fall into narrow categories: either highly regular (such as line graphs of bipartite graphs) or lacking expansion or combinatorial flexibility [ 3 , 8 ] . In this paper, we introduce a versatile new framework that lifts arbitrary finite graphs into perfect graphs. These lifts employ a straightforward but powerful two-step process: first, we take a bipartite double cover of the original graph, and then we construct its line graph. By definition, this ensures that the resulting graphs are claw-free and free of odd-length induced cycles (odd holes), properties that directly imply perfection [ 4 , 3 , 8 ] . In fact, since they are line graphs of bipartite graphs, all the lifted graphs in this paper are not only perfect but also box-perfect —their stable set polytopes admit efficient linear optimization under box constraints, a property of key algorithmic significance [ 10 ] . We present two distinct but complementary lifts: • the ordered lift \mathrm{HL}_{2}(G) , which depends explicitly on labeling the vertices and captures directional relationships; • the symmetric lift \mathrm{HL}^{\prime}_{2}(G) , which is purely structural and independent of vertex labels. A central contribution of our paper is showing that the symmetric lift \mathrm{HL}^{\prime}_{2}(G) is a canonical 2 -cover of the line graph L(G) , via the identification of each pair (u,v)\sim(v,u) . The quotient graph \mathrm{HL}^{\prime}_{2}(G)/{\sim} is isomorphic to L(G) , and this covering relationship explains why all adjacency and Laplacian eigenvalues of L(G) , including multiplicities, appear within those of \mathrm{HL}^{\prime}_{2}(G) . Thus, the symmetric lift not only perfects the structure of the line graph but also fully retains its spectral content. The symmetric lift further admits a natural decomposition under the involution that reverses directed edges, yielding an antisymmetric component: a signed graph L^{-}(G) , the antisymmetric line graph. This signed refinement encodes overlaps with +1 for shared tails or heads and -1 for crossed endpoints, completing the spectral picture via the multiset union \mathrm{Spec}(\mathrm{HL}^{\prime}_{2}(G))=\mathrm{Spec}(L(G))\cup\mathrm{Spec}(L^{-}(G)) . Moreover, the pair (L(G),L^{-}(G)) distinguishes graphs with isomorphic line graphs through sign patterns, refining Whitney’s theorem and enabling conflict-aware applications in optimization and expanders. The ordered lift \mathrm{HL}_{2}(G) also guarantees perfection but encodes directional and labeling constraints. Each lift \mathrm{HL}_{2}(G) , under a fixed labeling, forms a perfect subgraph of the line graph L(G) and of the symmetric lift \mathrm{HL}^{\prime}_{2}(G) . The ordered lifts are structurally coherent, perfect subgraphs that retain directional semantics—useful in applications such as Label Cover and Unique Games. One of the key theoretical outcomes of this framework is the construction of explicit families of perfect expanders. We show that when G is a regular expander—such as a Paley graph—the symmetric lift \mathrm{HL}^{\prime}_{2}(G) produces a new perfect graph that retains expansion, with a provably large spectral gap and has a large clique number. These constructions yield infinite families of sparse, algebraically defined perfect graphs that are simultaneously highly connected and structurally tractable—features not found in classical examples of perfect graphs. We analyze these lifts explicitly in classical graph families. For complete graphs K_{n} , the symmetric lift \mathrm{HL}^{\prime}_{2}(K_{n}) provides a new, regular, perfect refinement of the Johnson graphs J(n,2) [ 12 ] . In the case of Paley graphs, the symmetric lift produces explicit, highly structured perfect graphs with provable spectral bounds [ 16 , 13 , 9 ] , and spectral expansion comparable to the base graph. Moreover, the lift actually improves the combinatorial expansion of the base even when accounting for the near-doubling of the degree. This behaviour is also observed empirically in the case of random regular graphs of degree d on n vertices. The symmetric lift of these graphs is a degree 2d-2 box-perfect graph on nd/2 vertices, which tends too preserve the spectral expansion of the base as n grows large while amplifying the combinatorial expansion. In Section 7 , we generalize both constructions to parameterized lifts \mathrm{HL}_{r,d}(G) and \mathrm{HL}^{\prime}_{r,d}(G) . These broader families act on ordered r -tuples of vertices, defining adjacency through specified Hamming-distance conditions. The resulting infinite classes of perfect graphs exhibit richer combinational, algebraic, and spectral properties than classical examples, opening many avenues for further theoretical investigation and practical application. Beyond their intrinsic combinational and spectral significance, the canonical lifts \mathrm{HL}_{2}(G) and \mathrm{HL}^{\prime}_{2}(G) introduced here also have notable implications beyond classical graph theory. In companion works, we explore two important applications of these constructions. First, the label-sensitive ordered lift \mathrm{HL}_{2}(G) is leveraged to provide tractable yet structurally rich host graphs for Label-Cover instances and dictatorship tests, enabling polynomial-time approximations and direct empirical assessment of the Unique Games Conjecture [ 1 ] . Second, we demonstrate in a separate work that iterative application of the symmetric lift \mathrm{HL}^{\prime}_{2}(G) can generate large-scale graph structures exhibiting robust quantum coherence, offering a novel combinational foundation for designing quantum memory architectures and interference-based quantum technologies [ 2 ] . 2 The Ordered Lift {HL}_{2}(G) and the Symmetric Lift {HL}^{\prime}_{2}(G) We now define two lifts of a labeled graph G , called the Ordered and Symmetric lifts. These lifts produce perfect

Read the complete text