Search

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree. [ABSTRACT FROM AUTHOR]

In 2004, Frieze, Krivelevich and Martin established the emergence of a giant component in random subgraphs of pseudo‐random graphs. We study several typical properties of the giant component, most notably its expansion characteristics. We establish an asymptotic vertex expansion of connected sets in the giant by a factor of Õϵ2$$ \overset{\widetilde }{O}\left({\epsilon}^2\right) $$. From these expansion properties, we derive that the diameter of the giant is whpOϵ(logn)$$ {O}_{\epsilon}\left(\log n\right) $$, and that the mixing time of a lazy random walk on the giant is asymptotically Oϵlog2n$$ {O}_{\epsilon}\left({\log}^2n\right) $$. We also show similar asymptotic expansion properties of (not necessarily connected) linear‐sized subsets in the giant, and the typical existence of a large expander as a subgraph. [ABSTRACT FROM AUTHOR]

We show that with high probability the random graph Gn,1/2$$ {G}_{n,1/2} $$ has an induced subgraph of linear size, all of whose degrees are congruent to r(modq)$$ r\kern0.3em \left(\operatorname{mod}\kern0.3em q\right) $$ for any fixed r$$ r $$ and q≥2$$ q\ge 2 $$. More generally, the same is true for any fixed distribution of degrees modulo q$$ q $$. Finally, we show that with high probability we can partition the vertices of Gn,1/2$$ {G}_{n,1/2} $$ into q+1$$ q+1 $$ parts of nearly equal size, each of which induces a subgraph all of whose degrees are congruent to r(modq)$$ r\kern0.3em \left(\operatorname{mod}\kern0.3em q\right) $$. Our results resolve affirmatively a conjecture of Scott, who addressed the case q=2$$ q=2 $$. [ABSTRACT FROM AUTHOR]

We study the set L(G)$$ \mathcal{L}(G) $$ of lengths of all cycles that appear in a random d‐regular graph G on n vertices for d≥3$$ d\ge 3 $$ fixed, as well as in binomial random graphs on n vertices with a fixed average degree c>1$$ c>1 $$. Fundamental results on the distribution of cycle counts in these models were established in the 1980s and early 1990s, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in n. Here we derive, for a random d‐regular graph, the limiting probability that L(G)$$ \mathcal{L}(G) $$ simultaneously contains the entire range {ℓ,...,n}$$ \left\{\ell, \dots, n\right\} $$ for ℓ≥3$$ \ell \ge 3 $$, as an explicit expression θℓ=θℓ(d)∈(0,1)$$ {\theta}_{\ell }={\theta}_{\ell }(d)\in \left(0,1\right) $$ which goes to 1 as ℓ→∞$$ \ell \to \infty $$. For the random graph 풢(n,p) with p=c/n$$ p=c/n $$, where c≥C0$$ c\ge {C}_0 $$ for some absolute constant C0$$ {C}_0 $$, we show the analogous result for the range {ℓ,...,(1−o(1))Lmax(G)}$$ \left\{\ell, \dots, \left(1-o(1)\right){L}_{\mathrm{max}}(G)\right\} $$, where Lmax$$ {L}_{\mathrm{max}} $$ is the length of a longest cycle in G. The limiting probability for 풢(n,p) coincides with θℓ$$ {\theta}_{\ell } $$ from the d‐regular case when c is the integer d−1$$ d-1 $$. In addition, for the directed random graph 풟(n,p) we show results analogous to those on 풢(n,p), and for both models we find an interval of cε2n$$ c{\varepsilon}^2n $$ consecutive cycle lengths in the slightly supercritical regime p=1+εn$$ p=\frac{1+\varepsilon }{n} $$. [ABSTRACT FROM AUTHOR]

We prove that a random graph G(n,p), with p above the Hamiltonicity threshold, is typically such that for any r‐coloring of its edges there exists a Hamilton cycle with at least (2/(r+1)−o(1))n edges of the same color. This estimate is asymptotically optimal. [ABSTRACT FROM AUTHOR]

We investigate the genus g(n,m) of the Erdős‐Rényi random graph G(n,m), providing a thorough description of how this relates to the function m = m(n), and finding that there is different behavior depending on which "region" m falls into. Results already exist for m≤n2+O(n2/3) and m=ωn1+1j for j∈N, and so we focus on the intermediate cases. We establish that g(n,m)=(1+o(1))m2 whp (with high probability) when n ≪ m = n1 + o(1), that g(n,m) = (1 + o(1))μ(λ)m whp for a given function μ(λ) when m∼λn for λ>12, and that g(n,m)=(1+o(1))8s33n2 whp when m=n2+s for n2/3 ≪ s ≪ n. We then also show that the genus of a fixed graph can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of ϵn edges will whp result in a graph with genus Ω(n), even when ϵ is an arbitrarily small constant! We thus call this the "fragile genus" property. [ABSTRACT FROM AUTHOR]

Abstract: We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of G ∼ G ( n , 1 + ɛ n ) in terms of ɛ. We then apply this result to prove the following conjecture by Frieze and Pegden. For every ɛ > 0, there exists ℓ ɛ such that w.h.p. G ∼ G ( n , 1 + ɛ n ) is not homomorphic to the cycle on 2 ℓ ɛ + 1 vertices. We also consider the coloring properties of biased random tournaments. A p‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p. We show that for p = Θ ( 1 n ) the chromatic number of a p‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case p = 1 + ɛ n we use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse Θ ( ɛ 3 ) n edges to make it 2‐colorable. [ABSTRACT FROM AUTHOR]

We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph [ABSTRACT FROM AUTHOR]

ABSTRACT In this paper we analyze biased Maker-Breaker games and Avoider-Enforcer games, both played on the edge set of a random board [ABSTRACT FROM AUTHOR]

For a given finite graph G of minimum degree at least k, let G p be a random subgraph of G obtained by taking each edge independently with probability p. We prove that (i) if [ABSTRACT FROM AUTHOR]

The problem of packing Hamilton cycles in random and pseudorandom graphs has been studied extensively. In this paper, we look at the dual question of covering all edges of a graph by Hamilton cycles and prove that if a graph with maximum degree Δ satisfies some basic expansion properties and contains a family of [ABSTRACT FROM AUTHOR]