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 consider bond percolation on high-dimensional product graphs $G=\square _{i=1}^tG^{(i)}$ , where $\square$ denotes the Cartesian product. We call the $G^{(i)}$ the base graphs and the product graph $G$ the host graph. Very recently, Lichev (J. Graph Theory , 99(4):651–670, 2022) showed that, under a mild requirement on the isoperimetric properties of the base graphs, the component structure of the percolated graph $G_p$ undergoes a phase transition when $p$ is around $\frac{1}{d}$ , where $d$ is the average degree of the host graph. In the supercritical regime, we strengthen Lichev's result by showing that the giant component is in fact unique, with all other components of order $o(|G|)$ , and determining the sharp asymptotic order of the giant. Furthermore, we answer two questions posed by Lichev (J. Graph Theory , 99(4):651–670, 2022): firstly, we provide a construction showing that the requirement of bounded degree is necessary for the likely emergence of a linear order component; secondly, we show that the isoperimetric requirement on the base graphs can be, in fact, super-exponentially small in the dimension. Finally, in the subcritical regime, we give an example showing that in the case of irregular high-dimensional product graphs, there can be a polynomially large component with high probability, very much unlike the quantitative behaviour seen in the Erdős-Rényi random graph and in the percolated hypercube, and in fact in any regular high-dimensional product graphs, as shown by the authors in a companion paper (Percolation on high-dimensional product graphs. arXiv:2209.03722 , 2022). [ABSTRACT FROM AUTHOR]

Let G$$ G $$ be an n$$ n $$‐vertex graph, where δ(G)≥δn$$ \delta (G)\ge \delta n $$ for some δ:=δ(n)$$ \delta := \delta (n) $$. A result of Bohman, Frieze and Martin from 2003 asserts that if α(G)=Oδ2n$$ \alpha (G)=O\left({\delta}^2n\right) $$, then perturbing G$$ G $$ via the addition of ωlog(1/δ)δ3$$ \omega \left(\frac{\log \left(1/\delta \right)}{\delta^3}\right) $$ random edges, a.a.s. yields a Hamiltonian graph. We prove several improvements and extensions of the aforementioned result. In particular, keeping the bound on α(G)$$ \alpha (G) $$ as above and allowing for δ=Ω(n−1/3)$$ \delta =\Omega \left({n}^{-1/3}\right) $$, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a pancyclic graph. Moreover, we prove similar results for sparser graphs, and assuming the correctness of Chvátal's toughness conjecture, we handle graphs having larger independent sets. Finally, under milder conditions, we determine the correct order of magnitude of the number of random edges whose addition to G$$ G $$ a.a.s. yields a graph containing an almost spanning cycle. [ABSTRACT FROM AUTHOR]

We consider vertex percolation on pseudo‐random d$$ d $$‐regular graphs. The previous study by the second author established the existence of phase transition from small components to a linear (in nd$$ \frac{n}{d} $$) sized component, at p=1d$$ p=\frac{1}{d} $$. In the supercritical regime, our main result recovers the sharp asymptotic of the size of the largest component, and shows that all other components are typically much smaller. Furthermore, we consider other typical properties of the largest component such as the number of edges, existence of a long cycle and expansion. In the subcritical regime, we strengthen the upper bound on the likely component size. [ABSTRACT FROM AUTHOR]

We propose the following extension of Dirac's theorem: if G $G$ is a graph with n≥3 $n\ge 3$ vertices and minimum degree δ(G)≥n∕2 $\delta (G)\ge n\unicode{x02215}2$, then in every orientation of G $G$ there is a Hamilton cycle with at least δ(G) $\delta (G)$ edges oriented in the same direction. We prove an approximate version of this conjecture, showing that minimum degree n+8k2 $\frac{n+8k}{2}$ guarantees a Hamilton cycle with at least (n+k)∕2 $(n+k)\unicode{x02215}2$ edges oriented in the same direction. We also study the analogous problem for random graphs, showing that if the edge probability p=p(n) $p=p(n)$ is above the Hamiltonicity threshold, then, with high probability, in every orientation of G~G(n,p) $G\unicode{x0007E}G(n,p)$ there is a Hamilton cycle with (1−o(1))n $(1-o(1))n$ edges oriented in the same direction. [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 provide a short and self‐contained proof of the classical result of Kostochka and of Thomason, ensuring that every graph of average degree d $d$ has a complete minor of order Ω(d∕logd) ${\rm{\Omega }}(d\unicode{x02215}\sqrt{{\rm{log}}d})$. [ABSTRACT FROM AUTHOR]

We consider supercritical site percolation on the $d$ -dimensional hypercube $Q^d$. We show that typically all components in the percolated hypercube, besides the giant, are of size $O(d)$. This resolves a conjecture of Bollobás, Kohayakawa, and Łuczak from 1994. [ABSTRACT FROM AUTHOR]

We study the Turán number of long cycles in random and pseudo‐random graphs. Denote by ex(G(n,p),H)$\operatorname{ex}(G(n,p),H)$ the random variable counting the number of edges in a largest subgraph of G(n,p)$G(n,p)$ without a copy of H$H$. We determine the asymptotic value of ex(G(n,p),Ct)$\operatorname{ex}(G(n,p), C_t)$, where Ct$C_t$ is a cycle of length t$t$, for p⩾Cn$p\geqslant \frac{C}{n}$ and Alogn⩽t⩽(1−ε)n$A \log n \leqslant t \leqslant (1 - \varepsilon)n$. The typical behaviour of ex(G(n,p),Ct)$\operatorname{ex}(G(n,p), C_t)$ depends substantially on the parity of t$t$. In particular, our results match the classical result of Woodall on the Turán number of long cycles, and can be seen as its random version, showing that the transference principle holds here as well. In fact, our techniques apply in a more general sparse pseudo‐random setting. We also prove a robustness‐type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density. Finally, we also present further applications of our main tool (the Key Lemma) for proving results on Ramsey‐type problems about cycles in sparse random graphs. [ABSTRACT FROM AUTHOR]

We show that for any d=d(n) with d0(ϵ)≤d=o(n), with high probability, the size of a largest induced cycle in the random graph G(n,d/n) is (2±ϵ)ndlogd. This settles a long‐standing open problem in random graph theory. [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 present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $\hat{R}_{\mathrm{ind}}(P_n)\leq 5 \cdot 10^7n$ , thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and Łuczak. We also provide a bound for the k-colour version, showing that $\hat{R}_{\mathrm{ind}}^k(P_n)=O(k^3\log^4k)n$. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,\frac{1+\varepsilon}{n})$ , contains typically an induced path of length $\Theta(\varepsilon^2) n$. [ABSTRACT FROM AUTHOR]

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique and its algorithmic version, enhanced with a roll-back idea allowing a sequential retracing of previously performed embedding steps. We use this method to obtain the following results. [ABSTRACT FROM AUTHOR]