Ausgewählte Publikationen (Stand: April 2021)

Publications

Anzahl der Treffer: 29
Erstellt: Wed, 27 Mar 2024 23:22:34 +0100 in 0.0819 sec


Espuny Díaz, Alberto; Morris, Patrick; Perarnau, Guillem; Serra, Oriol
Speeding up random walk mixing by starting from a uniform vertex. - In: Electronic journal of probability, ISSN 1083-6489, Bd. 29 (2024), 26, S. 1-25

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to the slow diffusion caused by these bottlenecks. In this paper we provide a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order (log n)2, speeding up the mixing to order logn. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erd˝os-Rényi graph is logarithmic.



https://doi.org/10.1214/24-EJP1091
Espuny Díaz, Alberto; Janzer, Barnabás; Kronenberg, Gal; Lada, Joanna
Long running times for hypergraph bootstrap percolation. - In: European journal of combinatorics, Bd. 115 (2024), 103783, S. 1-18

Consider the hypergraph bootstrap percolation process in which, given a fixed r-uniform hypergraph H and starting with a given hypergraph G0, at each step we add to G0 all edges that create a new copy of H. We are interested in maximising the number of steps that this process takes before it stabilises. For the case where H = Kr+1(r) with r ≥ 3, we provide a new construction for G0 that shows that the number of steps of this process can be of order Θ (nr). This answers a recent question of Noel and Ranganathan. To demonstrate that different running times can occur, we also prove that, if H is K4(3) minus an edge, then the maximum possible running time is 2n − ⌊log2(n−2)⌋ − 6. However, if H is K5(3) minus an edge, then the process can run for Θ (n3) steps.



https://doi.org/10.1016/j.ejc.2023.103783
Espuny Díaz, Alberto; Person, Yury
Spanning F-cycles in random graphs. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 32 (2023), 5, S. 833-850

We extend a recent argument of Kahn, Narayanan and Park ((2021) Proceedings of the AMS 149 3201-3208) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of C4 that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning Kr-cycles.



https://doi.org/10.1017/S0963548323000172
Espuny Díaz, Alberto; Hyde, Joseph
Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph. - In: European journal of combinatorics, Bd. 0 (2023), 0, 103848

Let G be a graph obtained as the union of some n-vertex graph Hn with minimum degree δ (Hn) ≥ αn and a d-dimensional random geometric graph Gd (n,r). We investigate under which conditions for r the graph G will a.a.s. contain the kth power of a Hamilton cycle, for any choice of Hn. We provide asymptotically optimal conditions for r for all values of α, d and k. This has applications in the containment of other spanning structures, such as F-factors.



https://doi.org/10.1016/j.ejc.2023.103848
Espuny Díaz, Alberto; Girao, Antonio
Hamiltonicity of graphs perturbed by a random regular graph. - In: Random structures & algorithms, ISSN 1098-2418, Bd. 62 (2023), 4, S. 857-886

https://doi.org/10.1002/rsa.21122
Espuny Díaz, Alberto;
Hamiltonicity of graphs perturbed by a random geometric graph. - In: Journal of graph theory, ISSN 1097-0118, Bd. 103 (2023), 1, S. 12-22

We study Hamiltonicity in graphs obtained as the union of a deterministic n-vertex graph H with linear degrees and a d-dimensional random geometric graph G d (n, r) for any d ≥ 1. We obtain an asymptotically optimal bound on the minimum r for which a.a.s. H ∪ G d (n, r) is Hamiltonian. Our proof provides a linear time algorithm to find a Hamilton cycle in such graphs.



https://doi.org/10.1002/jgt.22901
Aigner-Horev, Elad; Person, Yury
An asymmetric random Rado theorem: 1-statement. - In: Journal of combinatorial theory, Bd. 193 (2023), 105687, S. 1-32

A classical result by Rado characterises the so-called partition-regular matrices A, i.e. those matrices A for which any finite colouring of the positive integers yields a monochromatic solution to the equation Ax=0. We study the asymmetric random Rado problem for the (binomial) random set [n]p in which one seeks to determine the threshold for the property that any r-colouring, r≥2, of the random set has a colour i∈[r] admitting a solution for the matrical equation Aix=0, where A1,…,Ar are predetermined partition-regular matrices pre-assigned to the colours involved. We prove a 1-statement for the asymmetric random Rado property. In the symmetric setting our result retrieves the 1-statement of the symmetric random Rado theorem established in a combination of results by Rödl and Ruciânski [34] and by Friedgut, Rödl and Schacht [11]. We conjecture that our 1-statement in fact unveils the threshold for the asymmetric random Rado property, yielding a counterpart to the so-called Kohayakawa-Kreuter conjecture concerning the threshold for the asymmetric random Ramsey problem in graphs. We deduce the aforementioned 1-statement for the asymmetric random Rado property after establishing a broader result generalising the main theorem of Friedgut, Rödl and Schacht from [11]. The latter then serves as a combinatorial framework through which 1-statements for Ramsey-type problems in random sets and (hyper)graphs alike can be established in the asymmetric setting following a relatively short combinatorial examination of certain hypergraphs. To establish this framework we utilise a recent approach put forth by Mousset, Nenadov and Samotij [26] for the Kohayakawa-Kreuter conjecture.



https://doi.org/10.1016/j.jcta.2022.105687
Aigner-Horev, Elad; Person, Yury
On sparse random combinatorial matrices. - In: Discrete mathematics, Bd. 345 (2022), 11, 113017

Let Qn,d denote the random combinatorial matrix whose rows are independent of one another and such that each row is sampled uniformly at random from the subset of vectors in {0,1}n having precisely d entries equal to 1. We present a short proof of the fact that P[det⁡(Qn,d)=0]=O(n1/2log3/2⁡nd)=o(1), whenever ω(n1/2log3/2⁡n)=d≤n/2. In particular, our proof accommodates sparse random combinatorial matrices in the sense that d=o(n) is allowed. We also consider the singularity of deterministic integer matrices A randomly perturbed by a sparse combinatorial matrix. In particular, we prove that P[det⁡(A+Qn,d)=0]=O(n1/2log3/2⁡nd), again, whenever ω(n1/2log3/2⁡n)=d≤n/2 and A has the property that (1,-d) is not an eigenpair of A.



https://doi.org/10.1016/j.disc.2022.113017
Condon, Padraig; Espuny Díaz, Alberto; Girão, António; Kühn, Daniela; Osthus, Deryk
Hamiltonicity of random subgraphs of the hypercube. - In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, (2021), S. 889-898

https://dl.acm.org/doi/10.5555/3458064.3458120
Espuny Díaz, Alberto; Girão, António
Hamiltonicity of randomly perturbed graphs. - In: Extended abstracts EuroComb 2021, (2021), S. 38-44

The theory of randomly perturbed graphs deals with the properties of graphs obtained as the union of a deterministic graph H and a random graph G. We study Hamiltonicity in two distinct settings. In both of them, we assume H is some deterministic graph with minimum degree at least αn, for some α (possibly depending on n). We first consider the case when G is a random geometric graph, and obtain an asymptotically optimal result. We then consider the case when G is a random regular graph, and obtain different results depending on the regularity.