Discrepancy of random graphs and hypergraphs

Jie Ma, Humberto Naves, Benny SudakovRandom Struct. Algorithms 2015 · DOI

TL;DR

This paper determines the discrepancy of random $k$-uniform hypergraphs up to a constant factor, answering a long-standing question. The authors provide tight bounds for both dense and sparse hypergraphs, revealing how the distribution of edges can deviate from its expected uniform spread.

What Problem Does This Paper Address?

The core problem this paper tackles is understanding the "discrepancy" of random hypergraphs. Imagine a hypergraph as a collection of vertices and edges, where each edge can connect more than two vertices (unlike a standard graph). The discrepancy of a hypergraph is a measure of how uniformly its edges are distributed among the vertices. Specifically, it quantifies the maximum deviation of the number of edges incident to a subset of vertices from what would be expected if the edges were perfectly spread out.

This concept is crucial in combinatorics and has connections to the theory of quasi-random graphs. While bounds for the discrepancy of graphs and hypergraphs have been established, determining the exact behavior for random hypergraphs, especially the expected discrepancy between two independent random hypergraphs, remained an open question. This paper addresses this by providing precise, tight bounds for this discrepancy, answering a question posed by Bollobás and Scott.

Methods

The authors introduce and utilize the concept of probabilistic discrepancy, denoted as discp(G, H), which measures the deviation of the overlap between two random hypergraphs under a random permutation of vertices. They show that the difference between the standard discrepancy disc(G, H) and discp(G, H) is small, allowing them to focus on bounding discp(G, H).

Key techniques include:

  • Concentration Inequalities: The paper heavily relies on Chernoff-type bounds (Lemma 2.1) and Janson's inequality (Lemma 2.2) to control the probability of deviations from expected values for sums of independent or weakly dependent random variables.
  • Hypergeometric Distribution Bounds: Lemma 2.4 provides crucial lower bounds for sums related to the hypergeometric distribution, which are essential for the dense case.
  • Greedy Algorithms and Matching: For the sparse case, a greedy algorithm is employed to construct a partial matching that ensures a large overlap between the two hypergraphs. This involves iteratively selecting vertices and their neighbors to satisfy specific codegree conditions.
  • Auxiliary Bipartite Graphs: To analyze the overlap, the authors construct auxiliary bipartite graphs that capture the relationships between vertices and edges of the original hypergraphs.
  • Probabilistic Argumentation: The proofs involve careful probabilistic arguments, including union bounds and analyzing the expected number of certain events, to establish results that hold with high probability.

Datasets

Not discussed in the paper. The paper deals with theoretical random graph and hypergraph models, not empirical datasets.

Key Insights and Ideas

  • Tight Bounds for Random Hypergraphs: The paper provides the first tight, constant-factor bounds for the discrepancy between two random $k$-uniform hypergraphs, settling a significant open problem.
  • Phase Transition in Discrepancy: The results reveal a clear distinction between dense and sparse hypergraphs. The behavior of the discrepancy changes dramatically based on the product of edge densities and the total number of possible edges ($pqN$).
  • Role of Edge Density: The discrepancy is shown to be directly related to the product of edge probabilities ($pq$) and the total number of possible edges ($N$), with a logarithmic factor appearing in the dense case.
  • Connection to Overlap: The problem of discrepancy is closely linked to the overlap between random hypergraphs, and the methods developed leverage this connection effectively.
  • Techniques for Sparse Hypergraphs: The development of a greedy algorithm for constructing partial matchings with specific codegree properties is a novel contribution for analyzing sparse random structures.

Key Results

The paper establishes tight bounds for the discrepancy disc(G, H) between two random $k$-uniform hypergraphs $G$ and $H$ on $n$ vertices with edge probabilities $p$ and $q$, respectively. Let $N = \binom{n}{k}$.

  • Dense Case: If $pqN > 3 \log n$, then with high probability (w.h.p.), disc(G, H) = \Theta_k(pqN \log n).
  • Sparse Case: If $pqN < \log n$:
  • If $pN \ge \frac{5}{30} \log n$, then w.h.p., disc(G, H) = \Theta_k\left(\sqrt{\frac{pqN \log n}{n}}\right).
  • If $pN < \frac{5}{30} \log n$, then w.h.p., disc(G, H) = \Theta_k\left(\left(\frac{pq}{N}\right)^{1/k} n \log n\right).

These results are shown to be optimal up to constant factors.

Limitations and Future Work

  • Constant Factors: While the paper provides asymptotic bounds, the exact constant factors are not optimized, as the authors state they prioritized a simpler presentation.
  • Range of $p$ and $q$: The paper focuses on $p, q \le 1/2$. While they mention that the case $p, q > 1/2$ can be reduced to the $p, q \le 1/2$ case by considering complements, the intermediate range where one probability is small and the other is large is not explicitly detailed, though the authors suggest the proof is similar.
  • Open Problems: The authors explicitly mention that there are a substantial number of open problems related to discrepancy theory and its applications in their related work [4]. This suggests that this paper opens up avenues for further research.

Summary updated

BibTeX
@article{ma2015discrepancy,
  author = {Jie Ma and Humberto Naves and Benny Sudakov},
  title = {{Discrepancy of random graphs and hypergraphs}},
  journal = {Random Struct. Algorithms},
  year = {2015},
  doi = {10.1002/rsa.20522},
}
Figure