English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The semi-random graph process is a single-player game that begins with anempty graph on $n$ vertices. In each round, a vertex $u$ is presented to theplayer independently and uniformly at random. The player then adaptivelyselects a vertex $v$ and adds the edge $uv$ to the graph. For a fixed monotonegraph property, the objective of the player is to force the graph to satisfythis property with high probability in as few rounds as possible.  We focus on the problem of constructing a subgraph isomorphic to anarbitrary, fixed graph $G$. Let $\omega = \omega(n)$ be any function tending toinfinity as $n \to \infty$. In (Omri Ben-Eliezer et al. "Semi-random graphprocess". In: Random Structures & Algorithms 56.3 (2020), pp. 648-675) it wasproved that asymptotically almost surely one can construct $G$ in less than$n^{(d-1)/d} \omega$ rounds where $d \ge 2$ is the degeneracy of $G$. It wasalso proved that the result is sharp for $G = K_{d+1}$, that is, asymptoticallyalmost surely it takes at least $n^{(d-1)/d} / \omega$ rounds to create$K_{d+1}$. Moreover, the authors conjectured that their general upper bound issharp for all graphs $G$. We prove this conjecture here.  We also consider a natural generalization of the process to $s$-uniformhypergraphs, the semi-random hypergraph process in which $r \ge 1$ vertices arepresented at random, and the player then selects $s-r \ge 1$ vertices to forman edge of size~$s$. Our results for graphs easily generalize to hypergraphswhen $r=1$; the threshold for constructing a fixed $s$-uniform hypergraph $G$is, again, determined by the degeneracy of $G$. However, new challenges aremounting when $r \ge 2$; thresholds are not even known for completehypergraphs. We provide bounds for this family and determine thresholds forsome sparser hypergraphs.

Subgraph Games in the Semi-Random Graph Process and Its Generalization to Hypergraphs