Vertex-minor universality of a random graph
Ting-Wei Chao *, Zixuan Xu * · 2026
Read Vertex-minor universality of a random graph by Ting-Wei Chao *, Zixuan Xu * (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13600.txt.
Description
Ting-Wei Chao and Zixuan Xu confirm a conjecture on vertex-minor universality of random graphs. A vertex-minor is obtained by vertex deletions and local complementation, which complements the induced graph on a vertex neighborhood. A graph is k-vertex-minor universal if every k-vertex graph appears as a vertex-minor on any k-subset. Prior work showed random graphs meet this at a square-root scale with high probability. Chao and Xu confirm the conjectured bound up to an extra logarithm factor.
Catalog record
| CREATOR | Ting-Wei Chao *, Zixuan Xu * |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39240 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.13600