Optimality of Random Regular Graphs in Sparse Network Designs

Abstract

The problems of designing sparse networks arise frequently in resource allocation and operations research. In production systems, for example, sparse process flexibility designs are used to handle uncertain demand effectively: the goal is to construct the sparsest bipartite graph between supply and demand that still achieves an expected fulfilled demand comparable to that of a fully flexible system. In middle-mile transportation, sparse delivery-route subgraphs that sustain large matchings after random node deletions help reduce delivery costs; here, the goal is to design the sparsest graph whose maximum matching size remains comparable to that of the fully connected graph under node deletions. The design of sparse networks has been studied extensively, with state-of-the-art results providing order-wise optimal designs for both bipartite and unipartite networks (Chen et al., 2015; Feng et al., 2024). However, identifying designs that achieve the sharp theoretical limit -- where the average degree asymptotically matches the lower bound of any graph to achieve a given loss level, has remained open. In this paper, we prove that the random regular graph achieves this sharp optimal condition in both bipartite and unipartite settings. Numerical experiments further validate this optimality. Our results highlight a practical guideline for sparse flexibility networks: designs that combine degree regularity with dispersed edge placement can achieve optimal performance under uncertainty.

Amply regular graphs with μ close to half the valency and group divisible designs
Wei Jin, Jack H. Koolen, Chenhui Lv
arXiv23 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Edge universality of random regular graphs of growing degrees
Jiaoyang Huang, Horng‐Tzer Yau
The Annals of Probability28 Aug 2026Peer-reviewedLicence not statedFull text16 citedStatisticsOpenAlex
When are random regular triangle-free graphs bipartite?
Gregory DeCamillis, Pu Gao
arXiv5 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
Xifan Yu
arXiv4 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
The singularity probability of dense random regular graphs
Zeyan Song, Hanchao Wang, Shengyan Yin +1
arXiv7 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{li2026optimality,
  title = {{Optimality of Random Regular Graphs in Sparse Network Designs}},
  author = {Weijia Li and Xiaochun Niu and Yehua Wei and Jiaming Xu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2606.14995},
  eprint = {2606.14995},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.14995},
}

RIS

TY  - UNPB
TI  - Optimality of Random Regular Graphs in Sparse Network Designs
AU  - Weijia Li
AU  - Xiaochun Niu
AU  - Yehua Wei
AU  - Jiaming Xu
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2606.14995
UR  - https://arxiv.org/abs/2606.14995
AB  - The problems of designing sparse networks arise frequently in resource allocation and operations research. In production systems, for example, sparse process flexibility designs are used to handle uncertain demand effectively: the goal is to construct the sparsest bipartite graph between supply and demand that still achieves an expected fulfilled demand comparable to that of a fully flexible system. In middle-mile transportation, sparse delivery-route subgraphs that sustain large matchings after random node deletions help reduce delivery costs; here, the goal is to design the sparsest graph whose maximum matching size remains comparable to that of the fully connected graph under node deletions. The design of sparse networks has been studied extensively, with state-of-the-art results providing order-wise optimal designs for both bipartite and unipartite networks (Chen et al., 2015; Feng et al., 2024). However, identifying designs that achieve the sharp theoretical limit -- where the average degree asymptotically matches the lower bound of any graph to achieve a given loss level, has remained open. In this paper, we prove that the random regular graph achieves this sharp optimal condition in both bipartite and unipartite settings. Numerical experiments further validate this optimality. Our results highlight a practical guideline for sparse flexibility networks: designs that combine degree regularity with dispersed edge placement can achieve optimal performance under uncertainty.
ER  -

Abstract

Related

Cite