Semicircle laws with combined variance for non-uniform Erd\H{o}s-Rényi hypergraphs

This paper characterizes the limiting spectral distribution of the random adjacency matrix for non-uniform and inhomogeneous Erdős-Rényi hypergraphs, establishing that under specific conditions, the distribution converges to a semicircle law with a variance defined as a convex combination of variances from uniform cases.

The Gist

Imagine you are trying to understand the "vibe" of a massive, chaotic party.

In a normal party (a standard graph), people only talk to one other person at a time. You can map this out easily: Person A talks to Person B, Person C talks to Person D. If you draw lines between everyone who is talking, you get a web of connections. Mathematicians have long known that if you look at the "energy" or "spectrum" of this web (specifically, the patterns of how connected everyone is), it follows a very predictable shape called the Semicircle Law. It looks like a perfect hill.

But real life isn't that simple. Sometimes, a group of three people are deep in conversation, or a committee of five is debating a topic. These are hyperedges (groups of people interacting all at once). When you have a mix of pairs, trios, and groups of ten all talking simultaneously, the math gets incredibly messy. This is a non-uniform hypergraph.

This paper is like a master chef figuring out how to predict the "flavor profile" of a soup that has every possible ingredient in it, in random amounts.

Here is the breakdown of what the authors (Avena, Bisi, and Bordiga) discovered, using some everyday analogies:

1. The Problem: The "Messy Party"

Imagine a party where:

• Some people are chatting in pairs (like normal friends).
• Some are in small groups of 3.
• Some are in huge groups of 20.
• The likelihood of a group forming depends on its size (maybe big groups are rare, or maybe they are super common).

The authors wanted to know: If we look at the "connectivity map" of this chaotic party, does it still form that nice, predictable Semicircle Hill? Or does the mix of group sizes make the shape jagged and unpredictable?

2. The Tool: The "Magic Gaussian Filter"

To solve this, the authors used a clever trick called Gaussianization.

Think of the actual party interactions as real, messy, discrete events (someone either joins a group or they don't). It's like counting individual raindrops hitting a roof. It's hard to predict the exact pattern of every single drop.

The authors proved that if the party is big enough and not too "sparse" (meaning there are enough conversations happening), you can replace the real, messy raindrops with a smooth, continuous Gaussian (bell curve) rain.

The Analogy:
Imagine trying to predict the water level in a bucket.

• Real World: You are dropping individual, heavy rocks (discrete connections) into the bucket. The splash is chaotic.
• Gaussian World: You turn on a smooth, steady hose (Gaussian noise). The water rises smoothly.

The paper proves that for this specific type of party, the "water level" (the spectral distribution) ends up looking exactly the same whether you drop rocks or turn on the hose. This allows them to use simpler, smoother math to predict the outcome.

3. The Result: A "Weighted" Semicircle

Once they smoothed out the math, they found the answer. The shape is still a Semicircle! But it's not the standard one. It's a Semicircle with a specific, custom variance (width).

Think of the final shape as a smoothie.

• You have a "Pair Smoothie" (from the 2-person groups).
• You have a "Triplet Smoothie" (from the 3-person groups).
• You have a "Group-of-10 Smoothie."

The final shape of the spectrum is a blend of all these smoothies.

• If the party is mostly pairs, the final shape looks like the Pair Smoothie.
• If it's mostly groups of 10, it looks like the Group-of-10 Smoothie.
• If it's a mix, the final shape is a weighted average of all of them.

The "weight" of each smoothie depends on two things:

1. How many people are in the group? (Size)
2. How likely is that group to form? (Probability)

The authors gave a precise formula to calculate exactly how much of each "smoothie" goes into the final mix.

4. The "Dominant" vs. "Balanced" Regimes

The paper also explains what happens when one type of group takes over.

• Dominant Regime: Imagine a party where 99% of the interactions are pairs, and only 1% are groups of 10. The "Group-of-10" noise is so faint that it disappears. The final shape is determined entirely by the pairs.
• Balanced Regime: Imagine a party where pairs and groups of 10 are both very common. Now, both contribute to the final shape. The resulting Semicircle is a unique blend, wider or narrower depending on the specific mix.

5. Why Does This Matter?

In the real world, systems are rarely uniform.

• Social Media: You have likes (pairs), comments (small groups), and viral threads (huge groups).
• Chemistry: Molecules react in pairs, but sometimes complex catalysts involve 5 or 6 atoms at once.
• Neuroscience: Neurons fire individually, but sometimes entire clusters fire together.

This paper gives scientists a "rulebook" to predict the behavior of these complex, mixed-size systems. It tells us that even in a chaotic, non-uniform world, if things are connected enough, the underlying order (the Semicircle) still emerges, but with a "fingerprint" (variance) that tells you exactly how the different types of connections are mixing.

In short: They took a messy, multi-sized, random network, proved you can treat it like a smooth Gaussian wave, and showed that the resulting pattern is a perfect, predictable hill whose width is a precise recipe of all the different group sizes involved.

Technical Summary

1. Problem Statement and Motivation

The paper addresses the spectral properties of non-uniform, inhomogeneous Erdős–Rényi (ER) random hypergraphs.

• Context: While spectral theory for random graphs (2-uniform hypergraphs) and uniform random hypergraphs is well-developed, real-world systems often involve interactions of varying sizes (non-uniform) and varying probabilities (inhomogeneous).
• The Model: The authors consider a hypergraph $H(n, \mathbf{r}, \mathbf{p})$ with $n$ vertices.
  • Non-uniformity: Hyperedges can have different sizes $r_1, \dots, r_k$.
  • Inhomogeneity: The probability $p_i$ of a hyperedge of size $r_i$ existing depends on its size.
  • Scaling: Both hyperedge sizes $r_i$ and connection probabilities $p_i$ are allowed to scale with $n$.
• The Object of Study: The adjacency matrix $A$, where the entry $A_{uv}$ counts the number of hyperedges containing both vertices $u$ and $v$. Unlike standard graphs, entries in $A$ are not independent (unless all $r_i=2$) and are not binary (entries can be $>1$).
• Goal: To characterize the Expected Limiting Spectral Distribution (ELSD) of the normalized, centered adjacency matrix $H_n$ in the non-sparse regime. Specifically, the authors aim to determine if the distribution converges to a semicircle law and, if so, to derive an explicit formula for its variance.

2. Methodology

The authors employ a two-step methodology combining Gaussianization techniques and random matrix theory (specifically relating to the Gaussian Orthogonal Ensemble, GOE).

A. Matrix Representation and Normalization

The adjacency matrix $A$ is decomposed into a sum of matrices corresponding to uniform sub-hypergraphs. The centered and scaled matrix is defined as:
$$H_n = \frac{A - \mathbb{E}[A]}{\sqrt{n}\sigma^2}$$
where $\sigma^2$ is the variance of the off-diagonal entries. This ensures the second moment of $H_n$ is bounded and non-vanishing.

B. Gaussianization (The Lindeberg-Chatterjee Approach)

A central technical contribution is the proof that the discrete, dependent entries of $H_n$ can be replaced by Gaussian random variables without altering the limiting spectral distribution.

• Technique: They adapt Chatterjee's extension of the Lindeberg replacement method (2005).
• Mechanism: They bound the distance between the Stieltjes transforms of the empirical spectral distributions (ESD) of the original matrix $H_n(X)$ and a Gaussianized counterpart $H_n(Z)$, where $Z$ is a vector of independent Gaussian variables with matching means and variances.
• Conditions: They establish a Pastur-type condition (Assumption 3.7) involving tail probabilities of the entries. They prove that if this condition holds, the difference in Stieltjes transforms vanishes as $n \to \infty$.
• Simplification: They provide a more practical, though stricter, non-sparsity condition (Assumption 3.2) based on the generalized average degree, which implies the Pastur-type condition.

C. Analysis of the Gaussianized Model

Once the model is Gaussianized, the matrix $H_n(Z)$ is analyzed.

• Although $H_n(Z)$ has zero diagonal and correlated off-diagonal entries (unlike a standard GOE), it can be represented as a finite-rank perturbation of a scaled GOE matrix with the diagonal removed.
• Standard results on finite-rank perturbations imply that the bulk spectrum still follows a semicircle law, provided the perturbation does not create outliers that dominate the variance calculation in the limit.

3. Key Contributions and Results

A. The Main Theorem (Convergence to Semicircle Law)

Theorem 3.4 states that under the non-sparsity condition and regularity assumptions on the parameters, the ELSD of $H_n$ converges weakly to a semicircle law $\nu_{s^2}$ with a specific variance $s^2$.

The variance is given by:
$$s^2 = \sum_{i=1}^k w_i (1 - c_i)^2$$
where:

• $c_i = \lim_{n \to \infty} r_i/n$ (the asymptotic relative size of hyperedges).
• $w_i$ are weights defined by the limit of the ratio of the variance contribution of size $r_i$ to the total variance:
  $$w_i = \lim_{n \to \infty} \frac{\binom{n-2}{r_i-2} p_i(1-p_i)}{\sum_{j=1}^k \binom{n-2}{r_j-2} p_j(1-p_j)}$$
• Interpretation: The limiting variance is a convex combination of the variances arising from uniform cases, weighted by the relative "strength" (variance contribution) of each hyperedge size class.

B. Gaussianization Conditions

Theorem 3.10 formalizes the Gaussianization result. It proves that the model is "Gaussianizable" if:

1. The Pastur-type condition holds (a tail decay condition on the entries).
2. Or, more simply, if the non-sparsity condition holds:
   $$\frac{(\sum r_i d_i)^2}{r_{\max}^{16} \xi^2 (\sum d_i/r_i)} \to \infty$$
   where $d_i$ is the average degree for size $r_i$, and $\xi$ is a weighted sum of inverse squared sizes.

C. Regime Analysis (Dominant vs. Balanced)

The paper analyzes how different hyperedge sizes compete:

• Dominant Regime: If one class of hyperedges (say $r_1$) has a significantly higher average degree relative to its size compared to others, it dictates the limiting variance ($s^2 \approx (1-c_1)^2$).
• Balanced Regime: If multiple classes contribute significantly, the variance is a true mixture of their individual contributions.
• Example: In the case of superimposed Erdős–Rényi graphs ($r_i=2$), the result recovers the standard semicircle law with variance 1 (if non-sparse).

D. Recovery of Known Results

The framework generalizes and recovers previous results:

• Uniform Hypergraphs: Recovers the results of Mukherjee et al. (2024).
• Standard Graphs: Recovers the results of Ding and Jiang (2010) for $G(n,p)$.
• Superpositions: Analyzes superpositions of random graphs with different connection probabilities.

4. Significance and Implications

• Generalization: This is one of the first rigorous treatments of the spectral distribution for non-uniform random hypergraphs. It moves beyond the restrictive assumption that all hyperedges must be of the same size.
• Explicit Variance Formula: The derivation of the variance $s^2$ as a convex combination provides a clear physical intuition: the spectral spread is determined by the "effective" variance of the interactions, weighted by how prevalent and large each interaction type is.
• Methodological Advance: The successful application of Chatterjee's Gaussianization technique to a setting with dependent entries (due to the hypergraph structure) and non-identical distributions (due to inhomogeneity) is a significant technical achievement. It demonstrates that the universality of the semicircle law extends to complex, heterogeneous higher-order networks.
• Limitations and Future Work: The paper focuses on the non-sparse regime (dense or moderately dense graphs). The sparse regime (where average degrees are bounded) requires different tools (local weak convergence) and is left for future work, as the current method relies on the concentration of measure in dense settings.

Summary Conclusion

The paper establishes that for a broad class of non-uniform, inhomogeneous random hypergraphs, the bulk spectrum of the adjacency matrix converges to a semicircle law. The key novelty is the explicit characterization of the limiting variance as a weighted average of the variances of the constituent uniform sub-models, governed by the trade-off between hyperedge sizes and connection probabilities. This provides a robust theoretical foundation for analyzing the spectral properties of complex, heterogeneous higher-order networks.