{"id":"arxiv/2610.18600","url":"https://arxiv.org/abs/2610.18600","tags":["math.CO"],"score":0,"title":"Saturation and semisaturation of oriented graphs","domain":"math.CO","source":"arxiv","authors":["Vladimir Bošković","Balázs Keszegh"],"reviews":0,"subject":"math.CO","summary":"We consider a natural extension of the classical saturation problem to oriented graphs, defined as the minimum number of edges in an oriented graph $H$ on $n$ vertices that avoids a fixed oriented graph $G$, but adding any missing edge to $H$ creates a copy of $G$. Our main result shows that saturation functions of oriented graphs attain at least four distinct orders of magnitude. In particular, if $G$ is acyclic, then its saturation function is bounded if and only if $G$ contains an isolated edge; otherwise, it is linear. Certain tournaments together with an isolated edge give further…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}