{"id":"arxiv/2608.14687","url":"https://arxiv.org/abs/2608.14687","tags":["math.CO","cs.DM","math.PR"],"score":0,"title":"Triangle-Saturated Graphs in the Semi-Random Graph Process","domain":"math.CO","source":"arxiv","authors":["Felix Christian Clemen","Pawel Pralat"],"reviews":0,"subject":"math.CO","summary":"The semi-random graph process is an adaptive random graph process in which an online algorithm is initially given an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the algorithm independently and uniformly at random. The algorithm then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. We also consider the offline version of the process in which the algorithm is given the entire sequence of random vertex choices before the selection takes place. For a given graph property, the objective of the algorithm is to force the graph to satisfy this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-06","reactions":{}}