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

CREATORTing-Wei Chao *, Zixuan Xu *
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39240
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.13600

Browse the full library · About the Tower of Babel