On the pre- and post-positional semi-random graph processes
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.
- A fully adaptive strategy for Hamiltonian cycles in the semi-random graph process
- Avoiding a giant component
- Balanced allocations (extended abstract)
- Cliques, chromatic number, and independent sets in the semi-random process
- Differential equations for random processes and random graphs
- Hamilton cycles in the semi-random graph process
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 1405894 (Why is no real title available?)
- scientific article; zbMATH DE number 3217680 (Why is no real title available?)
- scientific article; zbMATH DE number 3270498 (Why is no real title available?)
- scientific article; zbMATH DE number 3020563 (Why is no real title available?)
- Perfect matchings in the semirandom graph process
- Power of \(k\) choices in the semi-random graph process
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Semi-random graph process
- Subgraph games in the semi-random graph process and its generalization to hypergraphs
- The connectivity threshold for the min‐degree random graph process
- Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
This page was built for publication: On the pre- and post-positional semi-random graph processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7009619)
