Avoiding a giant component
This paper deals with random graphs. A sequence of events \(\{E_n\}\) is said to occur with high probability if \(\lim_{n\to\infty} P[E_n]= 1\). Suppose \(e_1, e_1';e_2,e_2';\dots\) is a sequence of ordered pairs of edges selected uniformly at random from the edge set of \(K_n\) (a complete graph with \(n\) vertices). At stage \(i\) we choose one of \(e_i\), \(e_i'\) to be an edge in our graph. The following is the main result of this paper indicating that choices can be made so that with high probability the size of the largest component of the graph formed at stage \(0.535n\) is polylogarithmic in \(n\).NEWLINENEWLINENEWLINETheorem: There is an algorithmic \(A\) and a positive constant \(c_0> 0.535\) such that with high probability the size of the largest component in \(G_A= G_A(m)\), with \(m= c_0n\) is bounded by \((\log n)^{O(1)}\).
- Critical random graphs and the differential equations technique
- The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
- Waiter-client and client-waiter Hamiltonicity games on random graphs
- The Bohman-Frieze process near criticality
- Delaying satisfiability for random 2SAT
- Getting a directed Hamilton cycle two times faster
- Sharp thresholds for half-random games. I.
- Hamiltonicity thresholds in Achlioptas processes
- Ramsey games with giants
- Random k-SAT and the power of two choices
- The evolution of subcritical Achlioptas processes
- Choice-driven phase transition in complex networks
- Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
- The Kőnig graph process
- Avoiding small subgraphs in Achlioptas processes
- scientific article; zbMATH DE number 1545679 (Why is no real title available?)
- Achlioptas process phase transitions are continuous
- Addendum to ‘avoiding a giant component’
- The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
- Explosive percolation in Erdős-Rényi-like random graph processes
- On the power of choice for Boolean functions
- The triangle-free process and the Ramsey number \(R(3,k)\)
- Recent advances in percolation theory and its applications
- Aggregation models with limited choice and the multiplicative coalescent
- Product rule wins a competitive game
- Creating a Giant Component
- Convergence of Achlioptas processes via differential equations with unique solutions
- Small subgraphs in random graphs and the power of multiple choices
- A phase transition for avoiding a giant component
- Bounded-size rules: the barely subcritical regime
- Embracing the giant component
- Coloring the edges of a random graph without a monochromatic giant component
- LATIN 2004: Theoretical Informatics
- Explosive percolation in the human protein homology network
- Given enough choice, simple local rules percolate discontinuously
- Sharp thresholds in adaptive random graph processes
- Connected components and evolution of random graphs: An algebraic approach
- Fast construction on a restricted budget
- Phase transitions for modified Erdős--Rényi processes
- Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
- Constructing Hamilton cycles and perfect matchings efficiently (extended abstract)
- Building Hamiltonian cycles in the semi-random graph process in less than 2n rounds
- On the pre- and post-positional semi-random graph processes
- A geometric Achlioptas process
- Birth control for giants
This page was built for publication: Avoiding a giant component
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2748427)
