{"id":"arxiv/2603.13600","url":"https://arxiv.org/abs/2603.13600","tags":["math.CO"],"score":0,"title":"Vertex-minor universality of a random graph","domain":"math.CO","source":"arxiv","authors":["Ting-Wei Chao","Zixuan Xu"],"reviews":0,"subject":"math.CO","summary":"Given a graph $G$ and a vertex $v\\in V(G)$, a local complementation at $v$ on $G$ is an operation that replaces the induced graph on the neighborhood of $v$ by its complement. A graph $H$ is a vertex-minor if $H$ can be obtained from $G$ by a sequence of vertex deletions and local complementation. A graph is said to be $k$-vertex-minor universal if it contains every $k$-vertex graph on any $k$-subset of vertices as a vertex minor. Previously, Ascoli--Fredrickson--Fredrickson--McFarland--Post proved that with high probability $G(n,1/2)$ is $Ω(\\sqrt{n})$-vertex-minor universal. Furthermore,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-13","reactions":{}}