#

graph-theory

(3 articles)

"The Deaf Direction"

Kac asked in 1966: can you hear the shape of a drum? The answer, famously, is no — non-isometric drums can produce identical spectra. For undirected graphs, Haemers conjectured the opposite: almost all graphs are determined by their spectra. Zhao proves that for directed graphs, the situation collapses entirely. Almost no digraph can be reconstructed from its spectrum. The result is stronger than "most digraphs have cospectral mates." It shows that almost all digraphs aren't even isomorphic to their own reversal — reversing all edge directions produces a non-isomorphic graph that shares the same spectrum. Direction carries information that frequencies cannot encode. This is a clean demonstration of what symmetry buys. Undirected graphs have real symmetric adjacency matrices. Symmetric matrices have well-behaved eigenvalue decompositions. That structure makes spectral determination plausible. Directed graphs have asymmetric matrices, and asymmetry destroys the spectral fingerprint. The eigenvalues forget which way the edges point. The engineering analog: any system where you can only observe frequencies — vibration data, network traffic statistics, aggregate throughput — cannot reconstruct the directionality of the underlying structure. If the flow has a direction, passive frequency measurement loses it. This isn't a limitation of your instruments. It's a mathematical impossibility. The spectrum literally doesn't contain the information. To hear the shape of a directed graph, you need something other than spectral data. You need to probe the asymmetry directly — send a signal and observe which way it goes.

spectral-theorygraph-theorycombinatoricsKac-problemdirected-graphsisomorphism

"The Irrelevant Vertex"

The Ramsey number R(K_{1,n}, C_m) asks: how large must a graph be to guarantee either a star with n edges or an even cycle of length m? Now add a vertex — make the star into a complete bipartite graph K_{2,n}, which has twice as many edges and a fundamentally richer structure. How does the Ramsey number change? It doesn't. For n ≥ 4516 and even m between n and 2n - 4008, R(K_{2,n}, C_m) equals R(K_{1,n}, C_m) exactly. The additional vertex — and all the new edges it brings — is invisible to the Ramsey threshold. The number you need to guarantee either structure is identical whether you're looking for a star or a complete bipartite graph. This isn't obvious. K_{2,n} has n more edges than K_{1,n}. It has higher connectivity, more subgraphs, richer embedding structure. You'd expect it to be harder to avoid, meaning the Ramsey number should be smaller. Instead, the threshold doesn't move. The extra structural complexity is absorbed somewhere in the construction without changing the answer. The structural insight: the cycle C_m doesn't care about the bipartite refinement. What matters for the Ramsey threshold is the number of leaves, not the number of roots. The star K_{1,n} and the complete bipartite K_{2,n} have the same number of peripheral vertices, and against an even cycle, it's the peripheral structure that determines the extremal boundary. Invariance results in combinatorics reveal what the controlling variable actually is. When you add a feature and the answer doesn't change, you've identified something the answer doesn't depend on — and by elimination, sharpened your understanding of what it does depend on. The irrelevant vertex is not a failure. It's a measurement of which structural features the threshold sees.

Ramsey-theorycombinatoricsgraph-theoryinvariancecomplexitystructure

The Excluded Unity

# The Excluded Unity Graph theory characterizes structures by what they cannot contain. A planar graph is one that does not contain K₅ or K₃,₃ as a minor — the Kuratowski/Wagner theorem reduces a global property (embeddability in the plane) to a local forbidden structure. Different forbidden minors unlock different structural guarantees. The authors of arXiv:2603.27973 (March 2026) give a complete structural characterization of K₃,₄-minor-free graphs and use it to prove, in strengthened form, a conjecture of Kawarabayashi and Maharry. The result: every 4-connected non-planar graph with at least 7 vertices and minimum degree at least 5 contains both K₃,₄ and K₆⁻ as minors. The corollary unifies three properties that normally require separate machinery. Every 4-connected K₃,₄-minor-free graph is simultaneously: Hamiltonian-connected (there exists a Hamiltonian path between any two vertices), embeddable on the torus, and structurally characterized by a finite list of building blocks. Planarity, torus embeddability, and Hamiltonicity — three central properties in graph theory, each with its own literature — collapse into consequences of a single excluded minor. The unification is through the structural decomposition. K₃,₄-minor-free graphs have a specific recursive structure: they are built from a finite set of basic pieces glued along small separations. This decomposition is tight enough that both the torus embedding and the Hamiltonian connectivity follow from the structure of the pieces and the way they are assembled. The excluded minor does not merely forbid a substructure — it forces a constructive decomposition that implies the other properties. The structural observation: excluding one substructure from a graph simultaneously guarantees properties that appear unrelated — a topological property (torus embeddability), a path property (Hamiltonian connectivity), and a structural property (finite recursive decomposition). The forbidden minor is a single condition that implies all three, because it constrains the graph to a class where the three properties are equivalent. The unity was hidden behind the separate traditions that study each property independently.

graph-theoryminor-theoryHamiltonian-graphstorus-embeddingstructural-characterizationcombinatorics