On the pre- and post-positional semi-random graph processes (Q7009619)

This paper studies and compares two versions of an evolving graph process, where each step is a combination of a random choice and a strategic choice of a player with a particular goal. More precisely, in each step, an edge is added to the graph. In an earlier version of this model, in the so-called post-positional semi-random graph process, within a step, the first vertex of the edge is chosen uniformly at random, and the other endpoint of the edge is chosen by the player. In the pre-positional semi-random process, defined and analysed in the current paper, it is the other way around: the player chooses a vertex first, and the other endpoint is chosen uniformly at random. These types of models are related to load-balancing schemes and the Achlioptas process as well.\N\NThe first main result of the paper states that the number of necessary steps to achieve that the graph is \(k\)-connected is linear compared to the number of vertices, with the coefficient depending on \(k\). Going further, the authors provide sharp bounds for the number of necessary steps for the graph to contain a copy of a given subgraph. Graphs containing a bipartite subgraph with \(m\) edges are also examined, with \(m =o(n^2)\), where \(n\) is the number of vertices. So far, there is no difference between the pre-positional and post-positional processes from the point of view of necessary steps. On the other hand, in Theorem 5, the authors present a problem about multigraphs, where the post-positional process is significantly faster.\N\NThe proofs of the results achieved in the paper combine the analysis of the min-degree process, coupling techniques, and appropriately chosen stopping times. Furthermore, block decomposition of graphs, block-cut trees, also play an important role in finding the upper bounds on the expected number of necessary steps to achieve \(k\)-connectivity.