Finite deletion-induced saturation for every non-complete graph
A graph $G$ is deletion-induced-saturated for $H$ if $G$ has an edge, contains no induced copy of $H$, and deleting any edge of $G$ creates an induced copy of $H$. We prove, with finite certificate verification, that a finite graph $H$ admits such a finite graph $G$ if and only if $H$ is not complete. This resolves the deletion conjecture of Fan, Hajebi, Hajebi and Spirkl. The main step transfers suitable free amalgamations to finite extensions using a local lifting theorem of Auinger, Bitterlich and Otto. A second criterion treats edge addition by protecting specified nonedges and then…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.21388
curl -X POST /api/v1/records/arxiv/2609.21388/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.21388/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'