Guillem Perarnau

Guillem Perarnau

Auto-generated profile, based on publicly available information

Guillem Perarnau

School of Mathematics University of Birmingham Birmingham UK

Research Focus & Metrics

Academic Career Length

17Years (2010-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 February 2016 in European Journal of Combinatorics
Verified
Journal Article
Closed access
NBNicolas Bousquet
Nicolas Bousquet
GPGuillem Perarnau
Guillem Perarnau

19 September 2016 in Advances in Applied Probability
Verified
Journal Article
Open access
PDF file
JDJ. Díaz
J. Díaz
DMD. Mitsche
D. Mitsche
GPG. Perarnau
G. Perarnau
XPX. Pérez-Giménez
X. Pérez-Giménez
Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper we improve the known upper bounds for values of r=ω(√logn) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on dE(u, v) conditional on dE(u, v).

1 January 2020 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
MCMatthew Coulson
Matthew Coulson
GPGuillem Perarnau
Guillem Perarnau
A famous theorem of Dirac states that any graph on $n$ vertices with minimum degree at least $n/2$ has a Hamilton cycle. Such graphs are called Dirac graphs. Strengthening this result, we show the existence of rainbow Hamilton cycles in $\mu n$-bounded colorings of Dirac graphs for sufficiently small $\mu >0$.

7 February 2012 in The Electronic Journal of Combinatorics
Verified
Journal Article
Open access
PDF file
FFFlorent Foucaud
Florent Foucaud
GPGuillem Perarnau
Guillem Perarnau
An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If $\gamma^{\text{ID}}(G)$ denotes the minimum size of an identifying code of a graph $G$, it was conjectured by F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud that there exists a constant $c$ such that if a connected graph $G$ with $n$ vertices and maximum degree $d$ admits an identifying code, then $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{d}+c$. We use probabilistic tools to show that for any $d\geq 3$, $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d)}$ holds for a large class of graphs containing, among others, all regular graphs and all graphs of bounded clique number. This settles the conjecture (up to constants) for these classes of graphs. In the general case, we prove $\gamma^{\text{ID}}(G)\leq n-\tfrac{n}{\Theta(d^{3})}$. In a second part, we prove that in any graph $G$ of minimum degree $\delta$ and girth at least 5, $\gamma^{\text{ID}}(G)\leq(1+o_\delta(1))\tfrac{3\log\delta}{2\delta}n$. Using the former result, we give sharp estimates for the size of the minimum identifying code of random $d$-regular graphs, which is about $\tfrac{\log d}{d}n$.

26 January 2017 in Probability Theory and Related Fields
Verified
Journal Article
Open access
PDF file
FJFelix Joos
Felix Joos
GPGuillem Perarnau
Guillem Perarnau
DRDieter Rautenbach
Dieter Rautenbach
BRBruce Reed
Bruce Reed
For a fixed degree sequence \({\mathcal {D}}=(d_1,\ldots ,d_n)\), let \(G({\mathcal {D}})\) be a uniformly chosen (simple) graph on \(\{1,\ldots ,n\}\) where the vertex i has degree \(d_i\). In this paper we determine whether \(G({\mathcal {D}})\) has a giant component with high probability, essentially imposing no conditions on \({\mathcal {D}}\). We simply insist that the sum of the degrees in \({\mathcal {D}}\) which are not 2 is at least \(\lambda (n)\) for some function \(\lambda \) going to infinity with n. This is a relatively minor technical condition, and when \({\mathcal {D}}\) does not satisfy it, both the probability that \(G({\mathcal {D}})\) has a giant component and the probability that \(G({\mathcal {D}})\) has no giant component are bounded away from 1.

2 January 2019
Verified
Book Chapter
Closed access
SCSitan Chen
Sitan Chen
MDMichelle Delcourt
Michelle Delcourt
AMAnkur Moitra
Ankur Moitra
GPGuillem Perarnau
Guillem Perarnau
LPLuke Postle
Luke Postle