On bipartite coverings of graphs and multigraphs

Noga AlonarXiv 2023 · DOI · arXiv

Abstract

In this paper, Noga Alon provides a shorter, purely combinatorial proof that strengthens classical bounds on the "capacity" of bipartite graph coverings. By linking graph theory to coding theory and utilizing the probabilistic method, the research establishes tighter lower and upper bounds for covering both simple graphs and multigraphs, improving upon previous results derived from more complex analytic tools.

Introduction

In graph theory, a bipartite covering of a graph $G$ is a collection of bipartite graphs $B_1, B_2, \dots, B_m$ such that every edge of $G$ is contained in at least one $B_j$. The efficiency of such a covering is measured by its capacity, defined as the sum of the number of vertices in each bipartite graph in the collection: $\sum_{j=1}^m |V(B_j)|$.

The study of bipartite coverings dates back to the 1960s. Hansel (1964) established that covering a complete graph $K_n$ requires a capacity of at least $n \log_2 n$. This was later generalized by Katona and Szemerédi to any graph based on its vertex degrees. Recently, the problem was extended to multigraphs ($K_n^\lambda$), where every pair of vertices is connected by $\lambda$ parallel edges. Alon’s work addresses gaps in the multigraph case and provides a new, stronger lower bound for general graphs that outperforms the classical Katona-Szemerédi result.

Methodology

Alon avoids the heavy machinery of "graphons" (analytic limits of dense graphs) used in previous studies, opting instead for elegant combinatorial and probabilistic techniques:

  • The Probabilistic Method: To establish lower bounds, the paper employs uniform random binary vectors. By defining specific events related to how vertices are distributed across the two sides of a bipartite graph, Alon utilizes the properties of binomial distributions and disjoint events to bound the capacity.
  • Convexity and Jensen’s Inequality: The proofs frequently apply convexity arguments to transform probabilistic inequalities into concrete lower bounds on the sum of vertex counts.
  • Coding Theory: For upper bounds on multigraphs, Alon maps the problem to binary error-correcting codes. He demonstrates that the minimum length of a code with distance $\lambda$ and $n$ codewords provides a constructive method for building a bipartite covering, leveraging established results like the Gilbert-Varshamov bound.

Key Insights and Results

Strengthening General Graph Bounds

The most significant insight for general graphs is that capacity is constrained by the size of independent sets ($\alpha_i$) containing each vertex $i$. Alon proves that the capacity is at least: $$\sum_{i=1}^n \log_2(n/\alpha_i)$$ Since $\alpha_i$ is always less than or equal to $n$ minus the degree of vertex $i$, this bound is strictly stronger than the classical degree-based bound. This is particularly evident in binomial random graphs $G(n, 0.5)$, where the classical bound yields a value around $n$, while Alon’s bound gives roughly $n \log n - n \log \log n$, which is nearly tight.

Multigraphs as Codes

Alon realizes that covering a multigraph $\lambda$ times is equivalent to finding a binary code where every pair of codewords differs in at least $\lambda$ positions. This bridge between graph theory and coding theory simplifies the problem significantly.

  • Theorem 1.1 (Multigraph Lower Bound): Establishes a new lower bound for $K_n^\lambda$ that includes a term involving $\lfloor(\lambda-1)/2\rfloor \log(\frac{2 \log n}{\lambda-1})$. This narrows the gap between the known lower and upper bounds.
  • Theorem 1.2 (Multigraph Upper Bound): Shows that the capacity is at most $n \cdot k(n, \lambda)$, where $k$ is the length of an optimal error-correcting code. This provides specific bounds for different regimes of $\lambda$, such as when $\lambda$ is small or proportional to $\log n$.
  • Theorem 1.4 (General Graph Strengthening): Formalizes the capacity of any bipartite covering as at least $\sum_{i=1}^n \log_2(n/\alpha_i)$, providing significantly better results for sparse or random graphs.

Conclusion

While this work narrows the "additive gap" for multigraph coverings, it does not completely close it. For certain ranges of $\lambda$, there remains a gap of $\Omega(\lambda n \log \log n)$ between the best known upper and lower bounds. Future research may focus on finding more precise coding-theoretic constructions or refined probabilistic arguments to eliminate this remaining uncertainty.

Summary updated

Abstract

A bipartite covering of a (multi)graph $G$ is a collection of bipartite graphs, so that each edge of $G$ belongs to at least one of them. The capacity of the covering is the sum of the numbers of vertices of these bipartite graphs. In this note we establish a (modest) strengthening of old results of Hansel and of Katona and Szemerédi, by showing that the capacity of any bipartite covering of a graph on $n$ vertices in which the maximum size of an independent set containing vertex number $i$ is $α_i$, is at least $\sum_i \log_2 (n/α_i).$ We also obtain slightly improved bounds for a recent result of Kim and Lee about the minimum possible capacity of a bipartite covering of complete multigraphs.
BibTeX
@misc{alon2023bipartite,
  author = {Noga Alon},
  title = {{On bipartite coverings of graphs and multigraphs}},
  year = {2023},
  eprint = {2307.16784},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.16784},
}
Figure