Combinatorial Properties of The Giant Under Supercritical Percolation
Source: arxiv.org/abs/2611.24606
We study combinatorial properties, such as diameter and long paths and cycles, of the giant component of percolated graphs. Such combinatorial properties are well studied for classical graphs such as pseudo-random graphs and the hypercube. We aim to obtain similar results for extensive families of $d$-regular $n$-vertex graphs. Specifically, assuming expansion properties of the host graph, we show a typical vertex expansion by a factor of $1/d\log d$ in the giant component of the percolated subgraph. As a consequence, we obtain bounds on various combinatorial properties of the giant…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.24606
curl -X POST /api/v1/records/arxiv/2611.24606/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.24606/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'