Turán's theorem, from edges to eigenvalues

The rich are loopy: a spectral framework for loop structure in the rich club

The rich club coefficient $\phi(k)$ quantifies whether high-degree nodes interconnect more densely than expected, but it is blind to the structure of those interconnections and offers no principled way to select the degree threshold $k$. We introduce the *cycle core* $H_k$, the maximal subgraph of vertices with degree at least $k$ that forms cycles among themselves. The nested sequence $H_1 \supseteq H_2 \supseteq \cdots$ reveals how the cycle core evolves as the degree threshold increases, capturing structure that $\phi(k)$ cannot see. We develop two spectral tools for this sequence. The first is structural: the *$k$-blocking operator* $\mathbf{M}_k$ generalizes the non-backtracking matrix by blocking $k - 1$ directions at each node. We prove that its spectrum is equivalent to that of a modified non-backtracking matrix weighted with a specific function of the nodes' degrees. Thus, $\mathbf{M}_k$ couples cycle structure with the degree sequence of the graph. We show the spectral radius of $\mathbf{M}_k$ peaks at an intrinsic threshold $k^*$, yielding the *optimal rich club* $H_{k^*}$ without null models or parameter tuning. The second tool is dynamical: the $k$-blocking walk defines a sub-stochastic Markov chain whose leading eigenvalue $\lambda_1(k)$ measures how long a process can persist on the cycle core before being expelled to the periphery. We evaluate the framework on fifteen networks spanning different domains, wherein $H_{k^*}$ closely recovers the published rich clubs.

A Gentle Introduction To Graph Theory

So many things in the world would have never come into existence if there hadn’t been a problem that needed solving. This truth applies to…

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial size in $O(n^{1.9992})$ time and APSP on directed $n$-vertex graphs with polynomially bounded integer weights in $O(n^{2.9995})$ time. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix--Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

The Cost of Representing Higher-Order Dynamics on Graphs: A Theoretical Framework

Can graphs represent the dynamics of higher-order (multi-body) interactions, or are hypergraphs necessary? We decompose network dynamics into three components: the combinatorial structure (graph or hypergraph), per-edge coupling functions, and per-node aggregation functions. Within this framework, we prove that graphs can always reproduce the trajectories of any hypergraph dynamics by absorbing the coupling logic into the aggregation. This generalizes a recent result by Peixoto et al., who showed the same under the assumption of flat dynamics. However, the graph representation pays a price in parsimony: when the coupling and aggregation functions are polynomials of degree at most D, the graph aggregation requires Θ(k^D/D!) parameters relative to the hypergraph alternative, where k is the interaction size. Without symmetry, the comparison can reverse. The framework also clarifies two other recent contributions by Moutuou and by Lacasa, and identifies overlooked modeling degrees of freedom including partial interaction symmetries and the role of non-additive aggregation.

GLEE: Geometric Laplacian Eigenmap Embedding

Graph embedding seeks to build a low-dimensional representation of a graph G. This low-dimensional representation is then used for various downstream tasks. One popular approach is Laplacian Eigenmaps (LE), which constructs a graph embedding based on the spectral properties of the Laplacian matrix of G. The intuition behind it, and many other embedding techniques, is that the embedding of a graph must respect node similarity: similar nodes must have embeddings that are close to one another. Here, we dispose of this distance-minimization assumption. Instead, we use the Laplacian matrix to find an embedding with geometric properties instead of spectral ones, by leveraging the so-called simplex geometry of G. We introduce a new approach, Geometric Laplacian Eigenmap Embedding, and demonstrate that it outperforms various other techniques (including LE) in the tasks of graph reconstruction and link prediction.

Theory Beyond Theorems and Proofs: A Guest Post

Scott’s foreword: I’m extremely grateful to my brilliant colleagues, Pravesh Kothari, Raghu Meka, and Prasad Raghavendra, for sharing the guest post below about how theoretical computer…

vouchgraph

A semi-live graph of all vouches on atvouch.dev

Notes for a Theory | Alberto Garutti

Brad's Thoughts on the Social Graph

I've been thinking a lot about the social graph for awhile now: aggregating the graph, decentralization, social network portability, etc.

General Theory of Natural Equivalences

Samuel Eilenberg, Saunders MacLane, General Theory of Natural Equivalences, Transactions of the American Mathematical Society, Vol. 58, No. 2 (Sep., 1945), pp. 231-294

Terence Tao (@tao@mathstodon.xyz)

In traditional mathematics (or "Math 1.0"), a breakthrough proof of a long-standing open conjecture generates a large amount of subsequent activity and excitement in the field. The authors of the proof are invited to give many talks, and meet with other experts in the area. Workshops are set up to discuss the proof, as well as other recent developments. As a result, new connections and collaborations are formed, followup problems are shared, and other mathematicians (both junior and senior) are attracted to the field (including in some cases the authors themselves, if they initially came from a different subject). As a result of all this activity, the proofs naturally become digested, streamlined, placed in context with other results in the field, and ultimately become part of the textbooks and lecture notes for the next generation of mathematicians in the field. (1/4)

Tim Berners-Lee, Giant Global Graph (2007)

A new vision for the web where the users master their data and link them to everybody's benefit in a giant global graph.

How I Vibed a Proof of Conway’s Conjecture — overreacted

You can just prove things, apparently.