Estimating the probability that the Erdős-Rényi random graph Gn,m is H-free, for a fixed graph H, is one of the fundamental problems in random graph theory. If H is non-bipartite and m is such that ...each edge of Gn,m belongs to a copy of H′ for every H′⊆H, in expectation, then it is known that Gn,m is H-free with probability exp(−Θ(m)). The KŁR conjecture, slightly rephrased, states that if we further condition on uniform edge distribution, the archetypal property of random graphs, the probability of being H-free becomes superexponentially small in the number of edges. While being interesting on its own, the conjecture has received significant attention due to its connection with the sparse regularity lemma, and the many results in random graphs that follow. It was proven by Balogh, Morris, and Samotij and, independently, by Saxton and Thomason, as one of the first applications of the hypergraph containers method. We give a new direct proof using induction.
We study the fixation time of the identity of the leader, that is, the most massive component, in the general setting of Aldous's multiplicative coalescent, which in an asymptotic sense describes the ...evolution of the component sizes of a wide array of near‐critical coalescent processes, including the classical Erdős‐Rényi process. We show tightness of the fixation time in the “Brownian” regime, explicitly determining the median value of the fixation time to within an optimal O(1) window. This generalizes Łuczak's result for the Erdős‐Rényi random graph using completely different techniques. In the heavy‐tailed case, in which the limit of the component sizes can be encoded using a thinned pure‐jump Lévy process, we prove that only one‐sided tightness holds. This shows a genuine difference in the possible behavior in the two regimes.
Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the ...deterministic setting, ignoring the impact of stochasticity in both the graph topology and the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response and autoregressive moving average graph filters, when operating on random time-varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that 1) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and 2) there are meaningful upper bounds for the variance of the filter output. We conclude this paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm and yield a (up to) four times complexity reduction, with a very little difference from the optimal solution.
We describe the R package hergm that implements hierarchical exponential-family random graph models with local dependence. Hierarchical exponential-family random graph models with local dependence ...tend to be superior to conventional exponential-family random graph models with global dependence in terms of goodness-of-fit. The advantage of hierarchical exponential-family random graph models is rooted in the local dependence induced by them. We discuss the notion of local dependence and the construction of models with local dependence along with model estimation, goodness-of-fit, and simulation. Simulation results and three applications are presented.
Site percolation on pseudo‐random graphs Diskin, Sahar; Krivelevich, Michael
Random structures & algorithms,
September 2023, 2023-09-00, 20230901, Letnik:
63, Številka:
2
Journal Article
Recenzirano
Odprti dostop
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.
Spanning trees in random graphs Montgomery, Richard
Advances in mathematics (New York. 1965),
11/2019, Letnik:
356
Journal Article
Recenzirano
Odprti dostop
For each Δ>0, we prove that there exists some C=C(Δ) for which the binomial random graph G(n,Clogn/n) almost surely contains a copy of every tree with n vertices and maximum degree at most Δ. In ...doing so, we confirm a conjecture by Kahn.
Covering cycles in sparse graphs Mousset, Frank; Škorić, Nemanja; Trujić, Miloš
Random structures & algorithms,
July 2022, 2022-07-00, 20220701, Letnik:
60, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Let k≥2 be an integer. Kouider and Lonc proved that the vertex set of every graph G with n≥n0(k) vertices and minimum degree at least n/k can be covered by k−1 cycles. Our main result states that for ...every α>0 and p=p(n)∈(0,1, the same conclusion holds for graphs G with minimum degree (1/k+α)np that are sparse in the sense that eG(X,Y)≤p|X||Y|+o(np|X||Y|/log3n)∀X,Y⊆V(G). In particular, this allows us to determine the local resilience of random and pseudorandom graphs with respect to having a vertex cover by a fixed number of cycles. The proof uses a version of the absorbing method in sparse expander graphs.
Dense subgraphs in random graphs Balister, Paul; Bollobás, Béla; Sahasrabudhe, Julian ...
Discrete Applied Mathematics,
05/2019, Letnik:
260
Journal Article
Recenzirano
Odprti dostop
For a constant γ∈0,1 and a graph G, let ωγ(G) be the largest integer k for which there exists a k-vertex subgraph of G with at least γk2 edges. We show that if 0<p<γ<1 then ωγ(Gn,p) is concentrated ...on a set of two integers. More precisely, with α(γ,p)=γlogγp+(1−γ)log1−γ1−p, we show that ωγ(Gn,p) is one of the two integers closest to 2α(γ,p)(logn−loglogn+logeα(γ,p)2)+12, with high probability. While this situation parallels that of cliques in random graphs, a new technique is required to handle the more complicated ways in which these “quasi-cliques” may overlap.
PDF
