BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Bhargav Narayanan (Rutgers)
DTSTART;VALUE=DATE-TIME:20200414T130000Z
DTEND;VALUE=DATE-TIME:20200414T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/1
DESCRIPTION:Title: Thresholds\nby Bhargav Narayanan (Rutgers) as part of Oxford disc
rete mathematics and probability seminar\n\n\nAbstract\nI'll discuss our r
ecent proof of a conjecture of Talagrand\, a fractional version of the "ex
pectation-threshold" conjecture of Kahn and Kalai. As a consequence of thi
s result\, we resolve various (heretofore) difficult problems in probabili
stic combinatorics and statistical physics.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ron Peled (Tel Aviv)
DTSTART;VALUE=DATE-TIME:20200414T143000Z
DTEND;VALUE=DATE-TIME:20200414T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/2
DESCRIPTION:Title: Site percolation on planar graphs and circle packings\nby Ron Pel
ed (Tel Aviv) as part of Oxford discrete mathematics and probability semin
ar\n\n\nAbstract\nColor each vertex of an infinite graph blue with probabi
lity p and red with probability 1-p\, independently among vertices. For wh
ich values of p is there an infinite connected component of blue vertices?
The talk will focus on this classical percolation problem for the class o
f planar graphs. Recently\, Itai Benjamini made several conjectures in thi
s context\, relating the percolation problem to the behavior of simple ran
dom walk on the graph. We will explain how partial answers to Benjamini's
conjectures may be obtained using the theory of circle packings. Among the
results is the fact that the critical percolation probability admits a un
iversal lower bound for the class of recurrent plane triangulations. No pr
evious knowledge on percolation or circle packings will be assumed.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Agelos Georgakopoulos (Warwick)
DTSTART;VALUE=DATE-TIME:20200421T130000Z
DTEND;VALUE=DATE-TIME:20200421T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/3
DESCRIPTION:Title: The percolation density $\\theta(p)$ is analytic\nby Agelos Georg
akopoulos (Warwick) as part of Oxford discrete mathematics and probability
seminar\n\n\nAbstract\nWe prove that for Bernoulli bond percolation on
ℤd\, d≥2\, the percolation density θ(p) (defined as the probability o
f the origin lying in an infinite cluster) is an analytic function of the
parameter in the supercritical interval (p_c\,1]. This answers a question
of Kesten from 1981.\n The proof involves a little bit of elementary co
mplex analysis (Weierstrass M-test)\, a few well-known results from percol
ation theory (Aizenman-Barsky/Menshikov theorem)\, but above all combinato
rial ideas. We used a new notion of contours\, bounds on the number of par
titions of an integer\, and the inclusion-exclusion principle\, to obtain
a refinement of a classical argument of Peierls that settled the 2-dimensi
onal case in 2018. More recently\, we coupled these techniques with a reno
rmalisation argument to handle all dimensions.\n Joint work with Christ
oforos Panagiotis.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cristina Toninelli (Paris Dauiphine)
DTSTART;VALUE=DATE-TIME:20200421T143000Z
DTEND;VALUE=DATE-TIME:20200421T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/4
DESCRIPTION:Title: Bootstrap percolation and kinetically constrained spin models: critic
al time scales\nby Cristina Toninelli (Paris Dauiphine) as part of Oxf
ord discrete mathematics and probability seminar\n\n\nAbstract\nRecent yea
rs have seen a great deal of progress in understanding the behavior of boo
tstrap percolation models\, a particular class of monotone cellular automa
ta. In the two dimensional lattice there is now a quite complete understan
ding of their evolution starting from a random initial condition\, with a
universality picture for their critical behavior. Here we will consider th
eir non-monotone stochastic counterpart\, namely kinetically constrained m
odels (KCM). In KCM each vertex is resampled (independently) at rate one b
y tossing a p-coin iff it can be infected in the next step by the bootstra
p model. In particular infection can also heal\, hence the non-monotonicit
y. Besides the connection with bootstrap percolation\, KCM have an interes
t in their own : when p shrinks to 0 they display some of the most strikin
g features of the liquid/glass transition\, a major and still largely open
problem in condensed matter physics.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Grégory Miermont (ENS Lyon)
DTSTART;VALUE=DATE-TIME:20200428T130000Z
DTEND;VALUE=DATE-TIME:20200428T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/5
DESCRIPTION:Title: The breadth-first construction of scaling limits of graphs with finit
e excess\nby Grégory Miermont (ENS Lyon) as part of Oxford discrete m
athematics and probability seminar\n\n\nAbstract\nRandom graphs with finit
e excess appear naturally in at least two different settings: random graph
s in the critical window (aka critical percolation on regular and other cl
asses of graphs)\, and unicellular maps of fixed genus. In the first situa
tion\, the scaling limit of such random graphs was obtained by Addario-Ber
ry\, Broutin and Goldschmidt based on a depth-first exploration of the gra
ph and on the coding of the resulting forest by random walks. This idea or
iginated in Aldous' work on the critical random graph\, using instead a br
eadth-first search approach that seem less adapted to taking graph scaling
limits. We show hat this can be done nevertheless\, resulting in some new
identities for quantities like the radius and the two-point function of t
he scaling limit. We also obtain a similar "breadth-first" construction of
the scaling limit of unicellular maps of fixed genus. This is based on jo
int work with Sanchayan Sen.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Olivier Bernardi (Brandeis)
DTSTART;VALUE=DATE-TIME:20200428T143000Z
DTEND;VALUE=DATE-TIME:20200428T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/6
DESCRIPTION:Title: Percolation on triangulations\, and a bijective path to Liouville qua
ntum gravity\nby Olivier Bernardi (Brandeis) as part of Oxford discret
e mathematics and probability seminar\n\n\nAbstract\nAbstract: I will disc
uss the percolation model on planar triangulations\, and present a bijecti
on that is key to relating this model to some fundamental probabilistic ob
jects. I will attempt to achieve several goals:\n1. Present the site-perco
lation model on random planar triangulations.\n2. Provide an informal intr
oduction to several probabilistic objects: the Gaussian free field\, Schra
mm-Loewner evolutions\, and the Brownian map.\n3. Present a bijective enco
ding of percolated triangulations by certain lattice paths\, and explain i
ts role in establishing exact relations between the above-mentioned object
s.\nThis is joint work with Nina Holden\, and Xin Sun.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Liana Yepremyan (LSE)
DTSTART;VALUE=DATE-TIME:20200505T130000Z
DTEND;VALUE=DATE-TIME:20200505T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/7
DESCRIPTION:Title: Ryser's conjecture and more\nby Liana Yepremyan (LSE) as part of
Oxford discrete mathematics and probability seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benny Sudakov (ETH Zurich)
DTSTART;VALUE=DATE-TIME:20200505T143000Z
DTEND;VALUE=DATE-TIME:20200505T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/8
DESCRIPTION:Title: Multidimensional Erdős-Szekeres theorem\nby Benny Sudakov (ETH Z
urich) as part of Oxford discrete mathematics and probability seminar\n\n\
nAbstract\nAbstract: The classical Erdős-Szekeres theorem dating back alm
ost a hundred years states that any sequence of $(n-1)2+1$ distinct real n
umbers contains a monotone subsequence of length n. This theorem has been
generalised to higher dimensions in a variety of ways but perhaps the most
natural one was proposed by Fishburn and Graham more than 25 years ago. T
hey raise the problem of how large should a d-dimesional array be in order
to guarantee a "monotone" subarray of size $n \\times n \\times \\ldots \
\times n$. In this talk we discuss this problem and show how to improve th
eir original Ackerman-type bounds to at most a triple exponential. (Joint
work with M. Bucic and T. Tran)\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tamar Ziegler (Hebrew University Jerusalem)
DTSTART;VALUE=DATE-TIME:20200512T130000Z
DTEND;VALUE=DATE-TIME:20200512T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/9
DESCRIPTION:Title: Sections of high rank varieties and applications\nby Tamar Ziegle
r (Hebrew University Jerusalem) as part of Oxford discrete mathematics and
probability seminar\n\n\nAbstract\nI will describe some recent work with
D. Kazhdan where we obtain results in algebraic geometry\, inspired by que
stions in additive combinatorics\, via analysis over finite fields. Specif
ically we are interested in quantitative properties of polynomial rings th
at are independent of the number of variables. A sample application is the
following theorem : Let $V$ be a complex vector space\, $P$ a high rank p
olynomial of degree $d$\, and $X$ the null set of $P\, X=\\{v|P(v)=0\\}$.
Any function $f:X\\to C$ which is polynomial of degree $d$ on lines in $X$
is the restriction of a degree $d$ polynomial on $V$.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anand Pillay (Notre Dame)
DTSTART;VALUE=DATE-TIME:20200512T143000Z
DTEND;VALUE=DATE-TIME:20200512T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/10
DESCRIPTION:Title: Approximate subgroups with bounded VC dimension\nby Anand Pillay
(Notre Dame) as part of Oxford discrete mathematics and probability semin
ar\n\n\nAbstract\nThis is joint with Gabe Conant. We give a structure theo
rem for finite subsets A of arbitrary groups G such that A has "small trip
ling" and "bounded VC dimension". Roughly\, A will be a union of a bounded
number of translates of a coset nilprogession of bounded rank and step (u
p to a small error).\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gal Kronenberg (Oxford)
DTSTART;VALUE=DATE-TIME:20200519T130000Z
DTEND;VALUE=DATE-TIME:20200519T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/11
DESCRIPTION:Title: The maximum length of $K_r$-Bootstrap Percolation\nby Gal Kronen
berg (Oxford) as part of Oxford discrete mathematics and probability semin
ar\n\n\nAbstract\nHow long does it take for a pandemic to stop spreading?
When modelling an infection process\, especially these days\, this is one
of the main questions that comes to mind. In this talk\, we consider this
question in the bootstrap percolation setting.\nGraph-bootstrap percolatio
n\, also known as weak saturation\, was introduced by Bollobás in 1968. I
n this process\, we start with initial "infected" set of edges E0\, and we
infect new edges according to a predetermined rule. Given a graph H and a
set of previously infected edges E_t ⊆ E(Kn)\, we infect a non-infected
edge e if it completes a new copy of H in G=([n] \, Et ∪ {e}). A questi
on raised by Bollobás asks for the maximum time the process can run befor
e it stabilizes. Bollobás\, Przykucki\, Riordan\, and Sahasrabudhe consid
ered this problem for the most natural case where H=Kr. They answered the
question for r ≤ 4 and gave a non-trivial lower bound for every r ≥ 5.
They also conjectured that the maximal running time is o(n2) for every in
teger r. We disprove their conjecture for every r ≥ 6 and we give a bett
er lower bound for the case r=5\; in the proof we use the Behrend construc
tion. This is a joint work with József Balogh\, Alexey Pokrovskiy\, and T
ibor Szabó.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eyal Lubetzky (Courant)
DTSTART;VALUE=DATE-TIME:20200519T143000Z
DTEND;VALUE=DATE-TIME:20200519T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/12
DESCRIPTION:Title: Maximum height of 3D Ising interfaces\nby Eyal Lubetzky (Courant
) as part of Oxford discrete mathematics and probability seminar\n\n\nAbst
ract\nDobrushin (1972) showed that\, at low enough temperatures\, the inte
rface of the 3D Ising model - the random surface separating the plus and m
inus phases above and below the xy-plane - is localized: it has O(1) heigh
t fluctuations above a fixed point\, and its maximum height Mn on a box of
side length n is OP(log n). We study this interface and derive a shape th
eorem for its ``pillars'' conditionally on reaching an atypically large he
ight. We use this to analyze the maximum height Mn of the interface\, and
prove that at low temperature Mn/log n converges to cβ in probability. Fu
rthermore\, the sequence (Mn - E[Mn])n≥1 is tight\, and even though this
sequence does not converge\, its subsequential limits satisfy uniform Gum
bel tails bounds.\nJoint work with Reza Gheissari.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Catherine Greenhill (UNSW)
DTSTART;VALUE=DATE-TIME:20200526T083000Z
DTEND;VALUE=DATE-TIME:20200526T093000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/13
DESCRIPTION:Title: The small subgraph conditioning method and hypergraphs\nby Cathe
rine Greenhill (UNSW) as part of Oxford discrete mathematics and probabili
ty seminar\n\n\nAbstract\nThe small subgraph conditioning method is an ana
lysis of variance technique which was introduced by Robinson and Wormald i
n 1992\, in their proof that almost all cubic graphs are Hamiltonian. The
method has been used to prove many structural results about random regular
graphs\, mostly to show that a certain substructure is present with high
probability. I will discuss some applications of the small subgraph condit
ioning method to hypergraphs\, and describe a subtle issue which is absent
in the graph setting.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Wood (Monash)
DTSTART;VALUE=DATE-TIME:20200526T100000Z
DTEND;VALUE=DATE-TIME:20200526T110000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/14
DESCRIPTION:Title: Subgraph densities in a surface\nby David Wood (Monash) as part
of Oxford discrete mathematics and probability seminar\n\n\nAbstract\nWe s
tudy the following question at the intersection of extremal and structural
graph theory. Given a fixed graph H that embeds in a fixed surface Σ\, w
hat is the maximum number of copies of H in an n-vertex graph that embeds
in Σ? Exact answers to this question are known for specific graphs H when
Σ is the sphere. We aim for more general\, albeit less precise\, results
. We show that the answer to the above question is Θ(nf(H))\, where f(H)
is a graph invariant called the `flap-number' of H\, which is independent
of Σ. This simultaneously answers two open problems posed by Eppstein (19
93). When H is a complete graph we give more precise answers. This is join
t work with Tony Huynh and Gwenaël Joret\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dana Randall (Georgia Tech)
DTSTART;VALUE=DATE-TIME:20200609T130000Z
DTEND;VALUE=DATE-TIME:20200609T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/15
DESCRIPTION:Title: Markov Chains for Programmable Active Matter\nby Dana Randall (G
eorgia Tech) as part of Oxford discrete mathematics and probability semina
r\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (UIC)
DTSTART;VALUE=DATE-TIME:20200609T140000Z
DTEND;VALUE=DATE-TIME:20200609T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/16
DESCRIPTION:Title: First-order phase transitions and efficient sampling algorithms\
nby Will Perkins (UIC) as part of Oxford discrete mathematics and probabil
ity seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Allan Sly (Princeton)
DTSTART;VALUE=DATE-TIME:20200609T153000Z
DTEND;VALUE=DATE-TIME:20200609T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/17
DESCRIPTION:Title: Replica Symmetry Breaking for Random Regular NAESAT\nby Allan Sl
y (Princeton) as part of Oxford discrete mathematics and probability semin
ar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv)
DTSTART;VALUE=DATE-TIME:20200602T130000Z
DTEND;VALUE=DATE-TIME:20200602T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/18
DESCRIPTION:Title: An entropy proof of the Erdős-Kleitman-Rothschild theorem.\nby
Wojciech Samotij (Tel Aviv) as part of Oxford discrete mathematics and pro
bability seminar\n\n\nAbstract\nWe say that a graph G is H-free if G does
not contain H as a (not necessarily induced) subgraph. For a positive inte
ger n\, denote by ex(n\,H) the largest number of edges in an H-free graph
with n vertices (the Turán number of H). The classical theorem of Erdős\
, Kleitman\, and Rothschild states that\, for every r≥3\, there are 2ex(
n\,H)+o(n2) many Kr-free graphs with vertex set {1\,…\, n}. There exist
(at least) three different derivations of this estimate in the literature:
an inductive argument based on the Kővári-Sós-Turán theorem (and its
generalisation to hypergraphs due to Erdős)\, a proof based on Szemerédi
's regularity lemma\, and an argument based on the hypergraph container th
eorems. In this talk\, we present yet another proof of this bound that exp
loits connections between entropy and independence. This argument is an ad
aptation of a method developed in a joint work with Gady Kozma\, Tom Meyer
ovitch\, and Ron Peled that studied random metric spaces.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean Bertoin (University of Zürich)
DTSTART;VALUE=DATE-TIME:20200602T143000Z
DTEND;VALUE=DATE-TIME:20200602T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/19
DESCRIPTION:Title: Scaling exponents of step-reinforced random walks\nby Jean Berto
in (University of Zürich) as part of Oxford discrete mathematics and prob
ability seminar\n\n\nAbstract\nLet X1\, … be i.i.d. copies of some real
random variable X. For any ε2\, ε3\, … in {0\,1}\, a basic algorithm i
ntroduced by H.A. Simon yields a reinforced sequence X̂1\, X̂2\, … as
follows. If εn=0\, then X̂n is a uniform random sample from X̂1\, …\,
X̂n-1\; otherwise X̂n is a new independent copy of X. The purpose of th
is talk is to compare the scaling exponent of the usual random walk S(n)=X
1 +… + Xn with that of its step reinforced version Ŝ(n)=X̂1+… + X̂
n. Depending on the tail of X and on asy\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rob Morris (IMPA)
DTSTART;VALUE=DATE-TIME:20200331T130000Z
DTEND;VALUE=DATE-TIME:20200331T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/20
DESCRIPTION:Title: Erdős covering systems\nby Rob Morris (IMPA) as part of Oxford
discrete mathematics and probability seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louigi Addario-Berry (McGill)
DTSTART;VALUE=DATE-TIME:20200407T130000Z
DTEND;VALUE=DATE-TIME:20200407T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/21
DESCRIPTION:Title: Hipster random walks and their ilk\nby Louigi Addario-Berry (McG
ill) as part of Oxford discrete mathematics and probability seminar\n\nAbs
tract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Janos Pach (Rényi Institute)
DTSTART;VALUE=DATE-TIME:20201006T130000Z
DTEND;VALUE=DATE-TIME:20201006T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/22
DESCRIPTION:Title: The Schur-Erdős problem for graphs of bounded dimension\nby Jan
os Pach (Rényi Institute) as part of Oxford discrete mathematics and prob
ability seminar\n\n\nAbstract\nThere is a growing body of results in extre
mal combinatorics and Ramsey theory which give better bounds or stronger c
onclusions under the additional assumption of bounded VC-dimension. Schur
and Erdős conjectured that there exists a suitable constant $c$ with the
property that every graph with at least $2^{cm}$ vertices\, whose edges ar
e colored by $m$ colors\, contains a monochromatic triangle. We prove this
conjecture for edge-colored graphs such that the set system induced by th
e neighborhoods of the vertices with respect to each color class has bound
ed VC-dimension. This result is best possible up to the value of $c$.\n
Joint work with Jacob Fox and Andrew Suk.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nina Holden (ETH)
DTSTART;VALUE=DATE-TIME:20201006T143000Z
DTEND;VALUE=DATE-TIME:20201006T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/23
DESCRIPTION:Title: Liouville quantum gravity with matter central in (1\,25): a probabil
istic approach\nby Nina Holden (ETH) as part of Oxford discrete mathem
atics and probability seminar\n\n\nAbstract\nLiouville quantum gravity (LQ
G) is a theory of random fractal surfaces with origin in the physics liter
ature in the 1980s. Most literature is about LQG with matter central charg
e $c\\in(-\\infty\,1]$. We study a discretization of LQG which makes sense
for all c\\in(-\\infty\,25)$. Based on a joint work with Gwynne\, Pfeffer
\, and Remy.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Asaf Nachmias (Tel Aviv)
DTSTART;VALUE=DATE-TIME:20201013T130000Z
DTEND;VALUE=DATE-TIME:20201013T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/24
DESCRIPTION:Title: The local limit of uniform spanning trees\nby Asaf Nachmias (Tel
Aviv) as part of Oxford discrete mathematics and probability seminar\n\n\
nAbstract\nLet $G_n$ be a sequence of finite\, simple\, connected\, regula
r graphs with degrees tending to infinity and let Tn be a uniformly drawn
spanning tree of $G_n$. In joint work with Yuval Peres we show that the lo
cal limit of $T_n$ is the Poisson(1) branching process conditioned to surv
ive forever (that is\, the asymptotic frequency of the appearance of any s
mall subtree is given by the branching process). The proof is based on ele
ctric network theory and I hope to show most of it.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Caroline Terry (Ohio State)
DTSTART;VALUE=DATE-TIME:20201013T143000Z
DTEND;VALUE=DATE-TIME:20201013T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/25
DESCRIPTION:Title: Speeds of hereditary properties and mutual algebricity\nby Carol
ine Terry (Ohio State) as part of Oxford discrete mathematics and probabil
ity seminar\n\n\nAbstract\nA hereditary graph property is a class of finit
e graphs closed under isomorphism and induced subgraphs. Given a hereditar
y graph property $H$\, the speed of $H$ is the function which sends an int
eger n to the number of distinct elements in $H$ with underlying set $\\{1
\,...\,n\\}$. Not just any function can occur as the speed of hereditary g
raph property. Specifically\, there are discrete "jumps" in the possible s
peeds. Study of these jumps began with work of Scheinerman and Zito in the
90's\, and culminated in a series of papers from the 2000's by Balogh\, B
ollobás\, and Weinreich\, in which essentially all possible speeds of a h
ereditary graph property were characterized. In contrast to this\, many as
pects of this problem in the hypergraph setting remained unknown. In this
talk we present new hypergraph analogues of many of the jumps from the gra
ph setting\, specifically those involving the polynomial\, exponential\, a
nd factorial speeds. The jumps in the factorial range turned out to have s
urprising connections to the model theoretic notion of mutual algebricity\
, which we also discuss. This is joint work with Chris Laskowski.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Croydon (Kyoto)
DTSTART;VALUE=DATE-TIME:20201020T080000Z
DTEND;VALUE=DATE-TIME:20201020T090000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/26
DESCRIPTION:Title: Scaling limits of the two- and three-dimensional uniform spanning tr
ees\nby David Croydon (Kyoto) as part of Oxford discrete mathematics a
nd probability seminar\n\n\nAbstract\nI will introduce recent work on the
two- and three-dimensional uniform spanning trees (USTs) that establish th
e laws of these random objects converge under rescaling in a space whose e
lements are measured\, rooted real trees\, continuously embedded into Eucl
idean space. (In the three-dimensional case\, the scaling result is curren
tly only known along a particular scaling sequence.) I will also discuss v
arious properties of the intrinsic metrics and measures of the limiting sp
aces\, including their Hausdorff dimension\, as well as the scaling limits
of the random walks on the two- and three-dimensional USTs. In the talk\,
I will attempt to emphasise where the differences lie between the two cas
es\, and in particular the additional challenges that arise when it comes
to the three-dimensional model.\n The two-dimensional results are joint
with Martin Barlow (UBC) and Takashi Kumagai (Kyoto). The three-dimension
al results are joint with Omer Angel (UBC) and Sarai Hernandez-Torres (UBC
).\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anita Liebenau (UNSW)
DTSTART;VALUE=DATE-TIME:20201020T093000Z
DTEND;VALUE=DATE-TIME:20201020T103000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/27
DESCRIPTION:Title: The threshold bias of the clique-factor game\nby Anita Liebenau
(UNSW) as part of Oxford discrete mathematics and probability seminar\n\n\
nAbstract\nLet $r>3$ be an integer and consider the following game on the
complete graph $K_n$ for $n$ a multiple of $r$: Two players\, Maker and Br
eaker\, alternately claim previously unclaimed edges of $K_n$ such that in
each turn Maker claims one and Breaker claims $b$ edges. Maker wins if he
r graph contains a $K_r$-factor\, that is a collection of $n/r$ vertex-dis
joint copies of $K_r$\, and Breaker wins otherwise. In other words\, we co
nsider the $b$-biased $K_r$-factor Maker-Breaker game. We show that the th
reshold bias for this game is of order $n^2/(r+2)$. This makes a step towa
rds determining the threshold bias for making bounded-degree spanning grap
hs and extends a result of Allen\, Böttcher\, Kohayakawa\, Naves and Pers
on who resolved the case $r=3$ or $4$ up to a logarithmic factor.\n Joi
nt work with Rajko Nenadov.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Igor Kortchemski (Ecole Polytechnique)
DTSTART;VALUE=DATE-TIME:20201027T140000Z
DTEND;VALUE=DATE-TIME:20201027T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/28
DESCRIPTION:Title: The geometry of random minimal factorizations of a long cycle\nb
y Igor Kortchemski (Ecole Polytechnique) as part of Oxford discrete mathem
atics and probability seminar\n\n\nAbstract\nWe will be interested in the
structure of random typical minimal factorizations of the n-cycle into tra
nspositions\, which are factorizations of $(1\,\\ldots\,n)$ as a product o
f $n-1$ transpositions. We shall establish a phase transition when a certa
in amount of transpositions have been read one after the other. One of the
main tools is a limit theorem for two-type Bienaymé-Galton-Watson trees
conditioned on having given numbers of vertices of both types\, which is o
f independent interest. This is joint work with Valentin Féray.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Postle (Waterloo)
DTSTART;VALUE=DATE-TIME:20201027T153000Z
DTEND;VALUE=DATE-TIME:20201027T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/29
DESCRIPTION:Title: Further progress towards Hadwiger's conjecture\nby Luke Postle (
Waterloo) as part of Oxford discrete mathematics and probability seminar\n
\n\nAbstract\nIn 1943\, Hadwiger conjectured that every graph with no Kt m
inor is $(t-1)$-colorable for every $t\\geq 1$. In the 1980s\, Kostochka a
nd Thomason independently proved that every graph with no $K_t$ minor has
average degree $O(t(\\log t)^{1/2})$ and hence is $O(t(\\log t)^{1/2)}$-co
lorable. Recently\, Norin\, Song and I showed that every graph with no $K_
t$ minor is $O(t(\\log t)^\\beta)$-colorable for every $\\beta > 1/4$\, ma
king the first improvement on the order of magnitude of the $O(t(\\log t)^
{1/2})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (
\\log t)^\\beta)$-colorable for every $\\beta > 0$\; more specifically\, t
hey are $O(t (\\log \\log t)^6)$-colorable.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julian Sahasrabudhe (Cambridge)
DTSTART;VALUE=DATE-TIME:20201103T140000Z
DTEND;VALUE=DATE-TIME:20201103T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/30
DESCRIPTION:Title: Combinatorics from the zeros of polynomials\nby Julian Sahasrabu
dhe (Cambridge) as part of Oxford discrete mathematics and probability sem
inar\n\n\nAbstract\nLet $X$ be a random variable\, taking values in $\\{1\
,…\,n\\}$\, with standard deviation $\\sigma$ and let $f_X$ be its proba
bility generating function. Pemantle conjectured that if $\\sigma$ is larg
e and $f_X$ has no roots close to 1 in the complex plane then $X$ must app
roximate a normal distribution. In this talk\, I will discuss a complete r
esolution of Pemantle's conjecture. As an application\, we resolve a conje
cture of Ghosh\, Liggett and Pemantle by proving a multivariate central li
mit theorem for\, so called\, strong Rayleigh distributions. I will also d
iscuss how these sorts of results shed light on random variables that aris
e naturally in combinatorial settings. This talk is based on joint work wi
th Marcus Michelen.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shoham Letzter (UCL)
DTSTART;VALUE=DATE-TIME:20201103T153000Z
DTEND;VALUE=DATE-TIME:20201103T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/31
DESCRIPTION:Title: An improvement on Łuczak's connected matchings method\nby Shoha
m Letzter (UCL) as part of Oxford discrete mathematics and probability sem
inar\n\n\nAbstract\nA connected matching is a matching contained in a conn
ected component. A well-known method due to Łuczak reduces problems about
monochromatic paths and cycles in complete graphs to problems about monoc
hromatic matchings in almost complete graphs. We show that these can be fu
rther reduced to problems about monochromatic connected matchings in compl
ete graphs.\n \nI will describe Łuczak's reduction\, introduce the new
reduction\, and mention potential applications of the improved method.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vincent Beffara (Grenoble)
DTSTART;VALUE=DATE-TIME:20201110T140000Z
DTEND;VALUE=DATE-TIME:20201110T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/32
DESCRIPTION:Title: Critical behavior without FKG\nby Vincent Beffara (Grenoble) as
part of Oxford discrete mathematics and probability seminar\n\n\nAbstract\
nI will present work in progress with D. Gayet and F. Pouran (Grenoble) to
establish Russo-Seymour-Welsh (RSW) estimates for 2d statistical mechanic
s models that do not satisfy the FKG inequality. RSW states that critical
percolation has no characteristic length\, in the sense that large rectang
les are crossed by an open path with a probability that is bounded below b
y a function of their shape\, but uniformly in their size\; this ensures t
he polynomial decay of many relevant quantities and opens the way to deepe
r understanding of the critical features of the model. All the standard pr
oofs of RSW rely on the FKG inequality\, i.e. on the positive correlation
between increasing events\; we establish the stability of RSW under small
perturbations that do not preserve FKG\, which extends it for instance to
the high-temperature anti-ferromagnetic Ising model.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tom Hutchcroft (Cambridge)
DTSTART;VALUE=DATE-TIME:20201110T153000Z
DTEND;VALUE=DATE-TIME:20201110T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/33
DESCRIPTION:Title: Power-law bounds for critical long-range percolation\nby Tom Hut
chcroft (Cambridge) as part of Oxford discrete mathematics and probability
seminar\n\n\nAbstract\nIn long-range percolation on $\\mathbb{Z}^d$\, eac
h potential edge $\\{x\,y\\}$ is included independently at random with pro
bability roughly $\\beta\\|x-y\\|-d-\\alpha$\, where $\\alpha > 0$ contr
ols how long-range the model is and $\\beta > 0$ is an intensity paramete
r. The smaller $\\alpha$ is\, the easier it is for very long edges to app
ear. We are normally interested in fixing $\\alpha$ and studying the phas
e transition that occurs as $\\beta$ is increased and an infinite cluster
emerges. Perhaps surprisingly\, the phase transition for long-range perco
lation is much better understood than that of nearest neighbour percolatio
n\, at least when $\\alpha$ is small: It is a theorem of Noam Berger that
if $\\alpha < d$ then the phase transition is continuous\, meaning that
there are no infinite clusters at the critical value of $\\beta$. (Proving
the analogous result for nearest neighbour percolation is a notorious ope
n problem!) In my talk I will describe a new\, quantitative proof of Berge
r's theorem that yields power-law upper bounds on the distribution of the
cluster of the origin at criticality.\n As a part of this proof\, I w
ill describe a new universal inequality stating that on any graph\, the ma
ximum size of a percolation cluster is of the same order as its median wit
h high probability. This inequality can also be used to give streamlined n
ew proofs of various classical results on e.g. Erdős-Rényi random graphs
\, which I will hopefully have time to talk a little bit about also.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yuval Peled (Courant)
DTSTART;VALUE=DATE-TIME:20201117T140000Z
DTEND;VALUE=DATE-TIME:20201117T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/34
DESCRIPTION:Title: Minimum weight disk triangulations and fillings\nby Yuval Peled
(Courant) as part of Oxford discrete mathematics and probability seminar\n
\n\nAbstract\nWe study the minimum total weight of a disk triangulation us
ing any number of vertices out of $\\{1\,..\,n\\}$ where the boundary is f
ixed and the $n \\choose 3$ triangles have independent rate-1 exponential
weights. We show that\, with high probability\, the minimum weight is equa
l to $(c+o(1))n-1/2\\log n$ for an explicit constant $c$. Further\, we pro
ve that\, with high probability\, the minimum weights of a homological fil
ling and a homotopical filling of the cycle $(123)$ are both attained by t
he minimum weight disk triangulation. We will discuss a related open probl
em concerning simple-connectivity of random simplicial complexes\, where a
similar phenomenon is conjectured to hold. Based on joint works with Itai
Benjamini\, Eyal Lubetzky\, and Zur Luria.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ron Rosenthal (Technion)
DTSTART;VALUE=DATE-TIME:20201117T153000Z
DTEND;VALUE=DATE-TIME:20201117T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/35
DESCRIPTION:Title: Random Steiner complexes and simplical spanning trees\nby Ron Ro
senthal (Technion) as part of Oxford discrete mathematics and probability
seminar\n\n\nAbstract\nA spanning tree of $G$ is a subgraph of $G$ with th
e same vertex set as $G$ that is a tree. In 1981\, McKay proved an asympto
tic result regarding the number of spanning trees in random $k$-regular gr
aphs\, showing that the number of spanning trees $\\kappa_1(G_n)$ in a ran
dom $k$-regular graph on $n$ vertices satisfies $\\lim_{n \\to \\infty} (\
\kappa_1(G_n))^{1/n} = c_{1\,k}$ in probability\, where $c_{1\,k} = (k-1)^
{k-1} (k^2-2k)^{-(k-2)/2}$. \n\nIn this talk we will discuss a high-dimens
ional of the matching model for simplicial complexes\, known as random Ste
iner complexes. In particular\, we will prove a high-dimensional counterpa
rt of McKay's result and discuss the local limit of such random complexes.
\nBased on a joint work with Lior Tenenbaum.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Holroyd (Bristol)
DTSTART;VALUE=DATE-TIME:20201124T140000Z
DTEND;VALUE=DATE-TIME:20201124T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/36
DESCRIPTION:Title: Matching Random Points\nby Alexander Holroyd (Bristol) as part o
f Oxford discrete mathematics and probability seminar\n\n\nAbstract\nWhat
is fairness\, and to what extent is it practically achievable? I'll talk a
bout a simple mathematical model under which one might hope to understand
such questions. Red and blue points occur as independent homogeneous Poiss
on processes of equal intensity in Euclidean space\, and we try to match t
hem to each other. We would like to minimize the sum of a some function (s
ay\, a power\, $\\gamma$) of the distances between matched pairs. This doe
s not make sense\, because the sum is infinite\, so instead we satisfy our
selves with minimizing *locally*. If the points are interpreted as agents
who would like to be matched as close as possible\, the parameter $\\gamma
$ encodes a measure of fairness - large $\\gamma$ means that we try to avo
id occasional very bad outcomes (long edges)\, even if that means inconven
ience to others - small $\\gamma$ means everyone is in it for themselves.\
n In dimension 1 we have a reasonably complete picture\, with a phase t
ransition at $\\gamma=1$. For $\\gamma<1$ there is a unique minimal matchi
ng\, while for $\\gamma>1$ there are multiple matchings but no stationary
solution. In higher dimensions\, even existence is not clear in all cases.
\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Joret (Université Libre de Bruxelles)
DTSTART;VALUE=DATE-TIME:20201124T153000Z
DTEND;VALUE=DATE-TIME:20201124T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/37
DESCRIPTION:Title: Sparse universal graphs for planarity\nby Gwenaël Joret (Univer
sité Libre de Bruxelles) as part of Oxford discrete mathematics and proba
bility seminar\n\n\nAbstract\nThis talk will focus on the following two re
lated problems:\n (1) What is the minimum number of edges in a graph
containing all $n$-vertex planar graphs as subgraphs? A simple constructi
on of Babai\, Erdos\, Chung\, Graham\, and Spencer (1982) has $O(n^{3/2})$
edges\, which is the best known upper bound.\n (2) What is the minim
um number of *vertices* in a graph containing all $n$-vertex planar graphs
as *induced* subgraphs? Here steady progress has been achieved over the y
ears\, culminating in a $O(n^{4/3})$ bound due to Bonamy\, Gavoille\, and
Pilipczuk (2019).\n As it turns out\, a bound of $n^{1+o(1)}$ can be
achieved for each of these two problems. The two constructions are somewha
t different but are based on a common technique. In this talk I will first
give a gentle introduction to the area and then sketch these construction
s. The talk is based on joint works with Vida Dujmović\, Louis Esperet\,
Cyril Gavoille\, Piotr Micek\, and Pat Morin.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Emmanuel Breuillard (Cambridge)
DTSTART;VALUE=DATE-TIME:20210119T143000Z
DTEND;VALUE=DATE-TIME:20210119T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/38
DESCRIPTION:Title: A subspace theorem for manifolds\nby Emmanuel Breuillard (Cambri
dge) as part of Oxford discrete mathematics and probability seminar\n\n\nA
bstract\nThe Schmidt subspace theorem is a far-reaching generalization of
the Thue-Siegel-Roth theorem in diophantine approximation. In this talk I
will give an interpretation of Schmidt's subspace theorem in terms of the
dynamics of diagonal flows on homogeneous spaces and describe how the exce
ptional subspaces arise from certain rational Schubert varieties associate
d to the family of linear forms through the notion of Harder-Narasimhan fi
ltration and an associated slope formalism. This geometric understanding o
pens the way to a natural generalization of Schmidt's theorem to the setti
ng of diophantine approximation on submanifolds of $GL_d$\, which is our m
ain result. In turn this allows us to recover and generalize the main resu
lts of Kleinbock and Margulis regarding diophantine exponents of submanifo
lds. I will also mention an application to diophantine approximation on Li
e groups. Joint work with Nicolas de Saxcé.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Artem Chernikov (UCLA)
DTSTART;VALUE=DATE-TIME:20210119T160000Z
DTEND;VALUE=DATE-TIME:20210119T170000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/39
DESCRIPTION:Title: Hypergraph regularity and higher arity VC-dimension\nby Artem Ch
ernikov (UCLA) as part of Oxford discrete mathematics and probability semi
nar\n\n\nAbstract\nWe generalize the fact that all graphs omitting a fixed
finite bipartite graph can be uniformly approximated by rectangles (Alon-
Fischer-Newman\, Lovász-Szegedy)\, showing that hypergraphs omitting a fi
xed finite $(k+1)$-partite $(k+1)$-uniform hypergraph can be approximated
by $k$-ary cylinder sets. In particular\, in the decomposition given by hy
pergraph regularity one only needs the first $k$ levels: such hypergraphs
can be approximated using sets of vertices\, sets of pairs\, and so on up
to sets of $k$-tuples\, and on most of the resulting $k$-ary cylinder sets
\, the density is either close to 0 or close to 1. Moreover\, existence of
such approximations uniformly under all measures on the vertices is a cha
racterization. Our proof uses a combination of analytic\, combinatorial an
d model-theoretic methods\, and involves a certain higher arity generaliza
tion of the epsilon-net theorem from VC-theory. Joint work with Henry Tow
sner.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Richard Montgomery (Birmingham)
DTSTART;VALUE=DATE-TIME:20210126T140000Z
DTEND;VALUE=DATE-TIME:20210126T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/40
DESCRIPTION:Title: A solution to Erdős and Hajnal's odd cycle problem\nby Richard
Montgomery (Birmingham) as part of Oxford discrete mathematics and probabi
lity seminar\n\n\nAbstract\nI will discuss how to construct cycles of many
different lengths in graphs\, in particular answering the following two p
roblems on odd and even cycles. Erdős and Hajnal asked in 1981 whether th
e sum of the reciprocals of the odd cycle lengths in a graph diverges as t
he chromatic number increases\, while\, in 1984\, Erdős asked whether the
re is a constant $C$ such that every graph with average degree at least $C
$ contains a cycle whose length is a power of 2.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noga Alon (Princeton)
DTSTART;VALUE=DATE-TIME:20210126T153000Z
DTEND;VALUE=DATE-TIME:20210126T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/41
DESCRIPTION:Title: Random friends walking on random graphs\nby Noga Alon (Princeton
) as part of Oxford discrete mathematics and probability seminar\n\n\nAbst
ract\nLet $X$ and $Y$ be two $n$-vertex graphs. Identify the vertices of $
Y$ with $n$ people\, any two of whom are either friends or strangers (acco
rding to the edges and non-edges in $Y$)\, and imagine that these people a
re standing one at each vertex of $X$. At each point in time\, two friends
standing at adjacent vertices of $X$ may swap places\, but two strangers
may not. The friends-and-strangers graph $FS(X\,Y)$ has as its vertex set
the collection of all configurations of people standing on the vertices of
$X$\, where two configurations are adjacent when they are related via a s
ingle friendly swap. This provides a common generalization for the famous
15-puzzle\, transposition Cayley graphs of symmetric groups\, and early wo
rk of Wilson and of Stanley.\nI will describe several recent results and o
pen problems addressing the extremal and typical aspects of the notion\, f
ocusing on the result that the threshold probability for connectedness of
$FS(X\,Y)$ for two independent binomial random graphs $X$ and $Y$ in $G(n\
,p)$ is $p=p(n)=n-1/2+o(1)$.\nJoint work with Colin Defant and Noah Kravit
z.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lisa Sauermann (IAS)
DTSTART;VALUE=DATE-TIME:20210202T140000Z
DTEND;VALUE=DATE-TIME:20210202T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/42
DESCRIPTION:Title: On the extension complexity of low-dimensional polytopes\nby Lis
a Sauermann (IAS) as part of Oxford discrete mathematics and probability s
eminar\n\n\nAbstract\nIt is sometimes possible to represent a complicated
polytope as a projection of a much simpler polytope. To quantify this phen
omenon\, the extension complexity of a polytope $P$ is defined to be the m
inimum number of facets in a (possibly higher-dimensional) polytope from w
hich $P$ can be obtained as a (linear) projection. In this talk\, we discu
ss some results on the extension complexity of random $d$-dimensional poly
topes (obtained as convex hulls of random points on either on the unit sph
ere or in the unit ball)\, and on the extension complexity of polygons wit
h all vertices on a common circle. Joint work with Matthew Kwan and Yufei
Zhao\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robin Stephenson (Sheffield)
DTSTART;VALUE=DATE-TIME:20210209T140000Z
DTEND;VALUE=DATE-TIME:20210209T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/43
DESCRIPTION:Title: The scaling limit of a critical random directed graph\nby Robin
Stephenson (Sheffield) as part of Oxford discrete mathematics and probabil
ity seminar\n\n\nAbstract\nWe consider the random directed graph $D(n\,p)$
with vertex set $\\{1\,2\,…\,n\\}$ in which each of the $n(n-1)$ possib
le directed edges is present independently with probability $p$. We are in
terested in the strongly connected components of this directed graph. A ph
ase transition for the emergence of a giant strongly connected component i
s known to occur at $p = 1/n$\, with critical window $p = 1/n + \\lambda n
-4/3$ for $\\lambda \\in \\mathbb{R}$. We show that\, within this critical
window\, the strongly connected components of $D(n\,p)$\, ranked in decre
asing order of size and rescaled by $n-1/3$\, converge in distribution to
a sequence $(C_1\,C_2\,\\ldots)$ of finite strongly connected directed mul
tigraphs with edge lengths which are either 3-regular or loops. The conver
gence occurs in the sense of an $L^1$ sequence metric for which two direct
ed multigraphs are close if there are compatible isomorphisms between thei
r vertex and edge sets which roughly preserve the edge lengths. Our proofs
rely on a depth-first exploration of the graph which enables us to relate
the strongly connected components to a particular spanning forest of the
undirected Erdős-Rényi random graph $G(n\,p)$\, whose scaling limit is w
ell understood. We show that the limiting sequence $(C_1\,C_2\,\\ldots)$ c
ontains only finitely many components which are not loops. If we ignore th
e edge lengths\, any fixed finite sequence of 3-regular strongly connected
directed multigraphs occurs with positive probability.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nati Linial (Hebrew University of Jerusalem)
DTSTART;VALUE=DATE-TIME:20210216T140000Z
DTEND;VALUE=DATE-TIME:20210216T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/44
DESCRIPTION:Title: Geodesic Geometry on Graphs\nby Nati Linial (Hebrew University o
f Jerusalem) as part of Oxford discrete mathematics and probability semina
r\n\n\nAbstract\nWe investigate a graph theoretic analog of geodesic geome
try. In a graph $G=(V\,E)$ we consider a system of paths $P=\\{P_{u\,v}| u
\,v\\in V\\}$ where $P_{u\,v}$ connects vertices $u$ and $v$. This system
is consistent in that if vertices $y\,z$ are in $P_{u\,v}$\, then the sub-
path of $P_{u\,v}$ between them coincides with $P_{y\,z}$. A map $w:E\\to(
0\,\\infty)$ is said to induce $P$ if for every $u\,v\\in V$ the path $P_{
u\,v}$ is $w$-geodesic. We say that $G$ is metrizable if every consistent
path system is induced by some such $w$. As we show\, metrizable graphs ar
e very rare\, whereas there exist infinitely many 2-connected metrizable g
raphs.\nThis is the MSc thesis of Daniel Cizma done under my guidance.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Justin Salez (Université Paris-Dauphine)
DTSTART;VALUE=DATE-TIME:20210302T140000Z
DTEND;VALUE=DATE-TIME:20210302T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/45
DESCRIPTION:Title: Sparse expanders have negative Ollivier-Ricci curvature\nby Just
in Salez (Université Paris-Dauphine) as part of Oxford discrete mathemati
cs and probability seminar\n\n\nAbstract\nWe prove that bounded-degree exp
anders with non-negative Ollivier-Ricci curvature do not exist\, thereby s
olving a long-standing open problem suggested by Naor and Milman and publi
cized by Ollivier (2010). In fact\, this remains true even if we allow for
a vanishing proportion of large degrees\, large eigenvalues\, and negativ
ely-curved edges. To establish this\, we work directly at the level of Ben
jamini-Schramm limits. More precisely\, we exploit the entropic characteri
zation of the Liouville property on stationary random graphs to show that
non-negative curvature and spectral expansion are incompatible 'at infinit
y'. We then transfer this result to finite graphs via local weak convergen
ce and a relative compactness argument. We believe that this 'local weak l
imit' approach to mixing properties of Markov chains will have many other
applications.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Perla Sousi (Cambridge)
DTSTART;VALUE=DATE-TIME:20210302T153000Z
DTEND;VALUE=DATE-TIME:20210302T170000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/46
DESCRIPTION:Title: The uniform spanning tree in 4 dimensions\nby Perla Sousi (Cambr
idge) as part of Oxford discrete mathematics and probability seminar\n\n\n
Abstract\nA uniform spanning tree of $\\mathbb{Z}^4$ can be thought of as
the "uniform measure" on trees of $\\mathbb{Z}^4$. The past of 0 in the un
iform spanning tree is the finite component that is disconnected from infi
nity when 0 is deleted from the tree. We establish the logarithmic correct
ions to the probabilities that the past contains a path of length $n$\, th
at it has volume at least $n$ and that it reaches the boundary of the box
of side length $n$ around 0. Dimension 4 is the upper critical dimension f
or this model in the sense that in higher dimensions it exhibits "mean-fie
ld" critical behaviour. An important part of our proof is the study of the
Newtonian capacity of a loop erased random walk in 4 dimensions. This is
joint work with Tom Hutchcroft.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bénédicte Haas (Paris 13)
DTSTART;VALUE=DATE-TIME:20210309T140000Z
DTEND;VALUE=DATE-TIME:20210309T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/47
DESCRIPTION:Title: Tail asymptotics for extinction times of self-similar fragmentations
\nby Bénédicte Haas (Paris 13) as part of Oxford discrete mathematic
s and probability seminar\n\n\nAbstract\nSelf-similar fragmentation proces
ses are random models for particles that are subject to successive fragmen
tations. When the index of self-similarity is negative the fragmentations
intensify as the masses of particles decrease. This leads to a shattering
phenomenon\, where the initial particle is entirely reduced to dust - a se
t of zero-mass particles - in finite time which is what we call the extinc
tion time. Equivalently\, these extinction times may be seen as heights of
continuous compact rooted trees or scaling limits of heights of sequences
of discrete trees. Our objective is to set up precise bounds for the larg
e time asymptotics of the tail distributions of these extinction times.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nathanaël Berestycki (Vienna)
DTSTART;VALUE=DATE-TIME:20210202T153000Z
DTEND;VALUE=DATE-TIME:20210202T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/48
DESCRIPTION:Title: Free boundary dimers: random walk representation and scaling limit
a>\nby Nathanaël Berestycki (Vienna) as part of Oxford discrete mathemati
cs and probability seminar\n\n\nAbstract\nThe dimer model\, a classical mo
del of statistical mechanics\, is the uniform distribution on perfect matc
hings of a graph. In two dimensions\, one can define an associated height
function which turns the model into a random surface (with specified bound
ary conditions). In the 1960s\, Kasteleyn and Temperley/Fisher found an ex
act "solution" to the model\, computing the correlations in terms of a mat
rix called the Kasteleyn matrix. This exact solvability was the starting p
oint for the breakthrough work of Kenyon (2000) who proved that the centre
d height function converges to the Dirichlet (or zero boundary conditions)
Gaussian free field. This was the first proof of conformal invariance in
statistical mechanics.\n\nIn this talk\, I will focus on a natural modific
ation of the model where one allows the vertices on the boundary of the gr
aph to remain unmatched: this is the so-called monomer-dimer model\, or di
mer model with free boundary conditions. The main result that we obtain is
that the scaling limit of the height function of the monomer-dimer model
in the upper half-plane is the Neumann (or free boundary conditions) Gauss
ian free field. Key to this result is a somewhat miraculous random walk re
presentation for the inverse Kasteleyn matrix\, which I hope to discuss.\n
\nJoint work with Marcin Lis (Vienna) and Wei Qian (Paris).\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ramon van Handel (Princeton)
DTSTART;VALUE=DATE-TIME:20210216T153000Z
DTEND;VALUE=DATE-TIME:20210216T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/49
DESCRIPTION:Title: Some unusual extremal problems in convexity and combinatorics\nb
y Ramon van Handel (Princeton) as part of Oxford discrete mathematics and
probability seminar\n\n\nAbstract\nIt is a basic fact of convexity that th
e volume of convex bodies is a polynomial\, whose coefficients contain man
y familiar geometric parameters as special cases. A fundamental result of
convex geometry\, the Alexandrov-Fenchel inequality\, states that these co
efficients are log-concave. This proves to have striking connections with
other areas of mathematics: for example\, the appearance of log-concave se
quences in many combinatorial problems may be understood as a consequence
of the Alexandrov-Fenchel inequality and its algebraic analogues.\n\nThere
is a long-standing problem surrounding the Alexandrov-Fenchel inequality
that has remained open since the original works of Minkowski (1903) and Al
exandrov (1937): in what cases is equality attained? In convexity\, this q
uestion corresponds to the solution of certain unusual isoperimetric probl
ems\, whose extremal bodies turn out to be numerous and strikingly bizarre
. In combinatorics\, an answer to this question would provide nontrivial i
nformation on the type of log-concave sequences that can arise in combinat
orial applications. In recent work with Y. Shenfeld\, we succeeded to sett
le the equality cases completely in the setting of convex polytopes. I wil
l aim to describe this result\, and to illustrate its potential combinator
ial implications through a question of Stanley on the combinatorics of par
tially ordered sets.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vida Dujmović (Ottawa)
DTSTART;VALUE=DATE-TIME:20210209T153000Z
DTEND;VALUE=DATE-TIME:20210209T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/50
DESCRIPTION:Title: Product structure theory and its applications\nby Vida Dujmović
(Ottawa) as part of Oxford discrete mathematics and probability seminar\n
\n\nAbstract\nI will introduce product structure theory of graphs and show
how families of graphs that have such a structure admit short adjacency l
abeling scheme and small induced universal graphs. Time permitting\, I wil
l talk about another recent application of product structure theory\, name
ly vertex ranking (coloring).\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Corrine Yap (Rutgers)
DTSTART;VALUE=DATE-TIME:20210309T153000Z
DTEND;VALUE=DATE-TIME:20210309T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/51
DESCRIPTION:Title: A Topological Turán Problem\nby Corrine Yap (Rutgers) as part o
f Oxford discrete mathematics and probability seminar\n\n\nAbstract\nThe c
lassical Turán problem asks: given a graph $H$\, how many edges can an $4
n$-vertex graph have while containing no isomorphic copy of $H$? By viewin
g $(k+1)$-uniform hypergraphs as $k$-dimensional simplicial complexes\, we
can ask a topological version (first posed by Nati Linial): given a $k$-d
imensional simplicial complex $S$\, how many facets can an $n$-vertex $k$-
dimensional simplicial complex have while containing no homeomorphic copy
of $S$? Until recently\, little was known for $k > 2$. In this talk\, we g
ive an answer for general $k$\, by way of dependent random choice and the
combinatorial notion of a trace-bounded hypergraph. Joint work with Jason
Long and Bhargav Narayanan.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guillem Perarnau (Universitat Politècnica de Catalunya)
DTSTART;VALUE=DATE-TIME:20210427T130000Z
DTEND;VALUE=DATE-TIME:20210427T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/52
DESCRIPTION:Title: Maximum stationary values in directed random graphs\nby Guillem
Perarnau (Universitat Politècnica de Catalunya) as part of Oxford discret
e mathematics and probability seminar\n\n\nAbstract\nIn this talk we will
consider the extremal values of the stationary distribution of the sparse
directed configuration model. Under the assumption of linear $(2+\\eta)$-m
oments on the in-degrees and of bounded out-degrees\, we obtain tight comp
arisons between the maximum value of the stationary distribution and the m
aximum in-degree. Under the further assumption that the order statistics o
f the in-degrees have power-law behavior\, we show that the upper tail of
the stationary distribution also has power-law behavior with the same inde
x. Moreover\, these results extend to the PageRank scores of the model\, t
hus confirming a version of the so-called power-law hypothesis. Joint work
with Xing Shi Cai\, Pietro Caputo and Matteo Quattropani.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Roberto Oliveira (IMPA)
DTSTART;VALUE=DATE-TIME:20210427T143000Z
DTEND;VALUE=DATE-TIME:20210427T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/53
DESCRIPTION:Title: Reversible Markov chains with nonnegative spectrum\nby Roberto O
liveira (IMPA) as part of Oxford discrete mathematics and probability semi
nar\n\n\nAbstract\nThe title of the talk corresponds to a family of intere
sting random processes\, which includes lazy random walks on graphs and mu
ch beyond them. Often\, a key step in analysing such processes is to estim
ate their spectral gaps (ie. the difference between two largest eigenvalue
s). It is thus of interest to understand what else about the chain we can
know from the spectral gap. We will present a simple comparison idea that
often gives us the best possible estimates. In particular\, we re-obtain a
nd improve upon several known results on hitting\, meeting\, and intersect
ion times\; return probabilities\; and concentration inequalities for time
averages. We then specialize to the graph setting\, and obtain sharp ineq
ualities in that setting. This talk is based on work that has been in prog
ress for far too long with Yuval Peres.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annika Heckel (LMU München)
DTSTART;VALUE=DATE-TIME:20210504T130000Z
DTEND;VALUE=DATE-TIME:20210504T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/54
DESCRIPTION:Title: How does the chromatic number of a random graph vary?\nby Annika
Heckel (LMU München) as part of Oxford discrete mathematics and probabil
ity seminar\n\n\nAbstract\nHow much does the chromatic number of the rando
m graph $G(n\, 1/2)$ vary? Shamir and Spencer proved that it is contained
in some sequence of intervals of length about $n^{1/2}$. Alon improved thi
s slightly to $n^{1/2} / \\log n$. Until recently\, however\, no lower bou
nds on the fluctuations of the chromatic number of $G(n\, 1/2)$ were known
\, even though the question was raised by Bollobás many years ago. I will
talk about the main ideas needed to prove that\, at least for infinitely
many $n$\, the chromatic number of $G(n\, 1/2)$ is not concentrated on few
er than $n^{1/2-o(1)}$ consecutive values.\nI will also discuss the Zigzag
Conjecture\, made recently by Bollobás\, Heckel\, Morris\, Panagiotou\,
Riordan and Smith: this proposes that the correct concentration interval l
ength 'zigzags' between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$\, depending on
$n$.\nJoint work with Oliver Riordan.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jean-François Le Gall (Paris-Saclay)
DTSTART;VALUE=DATE-TIME:20210504T143000Z
DTEND;VALUE=DATE-TIME:20210504T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/55
DESCRIPTION:Title: Geodesics in random geometry\nby Jean-François Le Gall (Paris-S
aclay) as part of Oxford discrete mathematics and probability seminar\n\n\
nAbstract\nWe discuss the behavior of geodesics in the continuous models o
f random geometry known as the Brownian map and the Brownian plane. We say
that a point $x$ is a geodesic star with $m$ arms if $x$ is the endpoint
of $m$ disjoint geodesics. We prove that the set of all geodesic stars wit
h $m$ arms has dimension $5-m$\, for $m=1\,2\,3\,4$. This complements rece
nts results of Miller and Qian\, who derived upper bounds for these dimens
ions.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Cécile Mailler (Bath)
DTSTART;VALUE=DATE-TIME:20210511T140000Z
DTEND;VALUE=DATE-TIME:20210511T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/56
DESCRIPTION:Title: The ants walk: finding geodesics in graphs using reinforcement learn
ing\nby Cécile Mailler (Bath) as part of Oxford discrete mathematics
and probability seminar\n\n\nAbstract\nHow does a colony of ants find the
shortest path between its nest and a source of food without any means of c
ommunication other than the pheromones each ant leave behind itself?\nIn t
his joint work with Daniel Kious (Bath) and Bruno Schapira (Marseille)\, w
e introduce a new probabilistic model for this phenomenon. In this model\,
the nest and the source of food are two marked nodes in a finite graph. A
nts perform successive random walks from the nest to the food\, and the di
stribution of the $n$th walk depends on the trajectories of the $(n-1)$ pr
evious walks through some linear reinforcement mechanism.\nUsing stochasti
c approximation methods\, couplings with Pólya urns\, and the electric co
nductances method for random walks on graphs (which I will explain on some
simple examples)\, we prove that\, depending on the exact reinforcement r
ule\, the ants may or may not always find the shortest path(s) between the
ir nest and the source food.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Asaf Ferber (University of California\, Irvine)
DTSTART;VALUE=DATE-TIME:20210511T153000Z
DTEND;VALUE=DATE-TIME:20210511T163000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/57
DESCRIPTION:Title: Lower bounds for multicolor Ramsey numbers\nby Asaf Ferber (Univ
ersity of California\, Irvine) as part of Oxford discrete mathematics and
probability seminar\n\n\nAbstract\nWe present an exponential improvement t
o the lower bound on diagonal Ramsey numbers for any fixed number of color
s greater than two.\nThis is a joint work with David Conlon.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mihyun Kang (Graz)
DTSTART;VALUE=DATE-TIME:20210518T130000Z
DTEND;VALUE=DATE-TIME:20210518T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/58
DESCRIPTION:Title: Benjamini-Schramm local limits of sparse random planar graphs\nb
y Mihyun Kang (Graz) as part of Oxford discrete mathematics and probabilit
y seminar\n\n\nAbstract\nIn this talk we will discuss some classical and r
ecent results on local limits of random graphs. It is well known that the
limiting object of the local structure of the classical Erdos-Renyi random
graph is a Galton-Watson tree. This can nicely be formalised in the langu
age of Benjamini-Schramm or Aldous-Steele local weak convergence. Regardin
g local limits of sparse random planar graphs\, there is a smooth transiti
on from a Galton-Watson tree to a Skeleton tree. This talk is based on joi
nt work with Michael Missethan.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vincent Tassion (ETH)
DTSTART;VALUE=DATE-TIME:20210525T130000Z
DTEND;VALUE=DATE-TIME:20210525T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/59
DESCRIPTION:Title: Crossing probabilities for planar percolation\nby Vincent Tassio
n (ETH) as part of Oxford discrete mathematics and probability seminar\n\n
\nAbstract\nPercolation models were originally introduced to describe the
propagation of a fluid in a random medium. In dimension two\, the percolat
ion properties of a model are encoded by so-called crossing probabilities
(probabilities that certain rectangles are crossed from left to right). In
the eighties\, Russo\, Seymour and Welsh obtained general bounds on cross
ing probabilities for Bernoulli percolation (the most studied percolation
model\, where edges of a lattice are independently erased with some given
probability $1-p$). These inequalities rapidly became central tools to ana
lyze the critical behavior of the model.\nIn this talk I will present a ne
w result which extends the Russo-Seymour-Welsh theory to general percolati
on measures satisfying two properties: symmetry and positive correlation.
This is a joint work with Laurin Köhler-Schindler.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michael Krivelevich (Tel Aviv)
DTSTART;VALUE=DATE-TIME:20210525T143000Z
DTEND;VALUE=DATE-TIME:20210525T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/60
DESCRIPTION:Title: Cycle lengths in sparse random graphs\nby Michael Krivelevich (T
el Aviv) as part of Oxford discrete mathematics and probability seminar\n\
n\nAbstract\nWe study the set $L(G)$ of cycle lengths that appear in a spa
rse binomial random graph $G(n\,c/n)$ and in a random $d$-regular graph $G
_{n\,d}$. We show in particular that for most values of $c$\, for $G$ draw
n from $G(n\,c/n)$ the set $L(G)$ contains typically an interval $[\\omega
(1)\, (1-o(1))L_{\\max}(G)]$\, where $L_{\\max}(G)$ is the length of a lon
gest cycle (the circumference) of $G$. For the case of random $d$-regular
graphs\, $d\\geq 3$ fixed\, we obtain an accurate asymptotic estimate for
the probability of $L(G)$ to contain a full interval $[k\,n]$ for a fixed
$k\\geq 3$. Similar results are obtained also for the supercritical case
$G(n\,(1+\\epsilon)/n)$\, and for random directed graphs.\nA joint work wi
th Yahav Alon and Eyal Lubetzky.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/60/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Konstantin Tikhomirov (Georgia Tech)
DTSTART;VALUE=DATE-TIME:20210601T133000Z
DTEND;VALUE=DATE-TIME:20210601T143000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/61
DESCRIPTION:Title: Invertibility of random square matrices\nby Konstantin Tikhomiro
v (Georgia Tech) as part of Oxford discrete mathematics and probability se
minar\n\n\nAbstract\nConsider an $n$ by $n$ random matrix $A$ with i.i.d e
ntries. In this talk\, we discuss some results on the magnitude of the sma
llest singular value of $A$\, and\, in particular\, the problem of estimat
ing the singularity probability when the entries of $A$ are discrete.\n\nJ
oint with Oxford's Random Matrix Theory Seminar.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/61/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gérard Ben Arous (Courant Institute)
DTSTART;VALUE=DATE-TIME:20210601T143000Z
DTEND;VALUE=DATE-TIME:20210601T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/62
DESCRIPTION:Title: Random Determinants and the Elastic Manifold\nby Gérard Ben Aro
us (Courant Institute) as part of Oxford discrete mathematics and probabil
ity seminar\n\n\nAbstract\nThis is joint work with Paul Bourgade and Benja
min McKenna (Courant Institute\, NYU).\nThe elastic manifold is a paradigm
atic representative of the class of disordered elastic systems. These mode
ls describe random surfaces with rugged shapes resulting from a competitio
n between random spatial impurities (preferring disordered configurations)
\, on the one hand\, and elastic self-interactions (preferring ordered con
figurations)\, on the other. The elastic manifold model is interesting bec
ause it displays a depinning phase transition and has a long history as a
testing ground for new approaches in statistical physics of disordered med
ia\, for example for fixed dimension by Fisher (1986) using functional ren
ormalization group methods\, and in the high-dimensional limit by Mézard
and Parisi (1992) using the replica method.\nWe study the topology of the
energy landscape of this model in the Mézard-Parisi setting\, and compute
the (annealed) topological complexity both of total critical points and o
f local minima. Our main result confirms the recent formulas by Fyodorov a
nd Le Doussal (2020) and allows to identify the boundary between simple an
d glassy phases. The core argument relies on the analysis of the asymptoti
c behavior of large random determinants in the exponential scale.\n\nJoint
with Oxford's Random Matrix Theory Seminar.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/62/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amedeo Sgueglia (LSE)
DTSTART;VALUE=DATE-TIME:20210518T143000Z
DTEND;VALUE=DATE-TIME:20210518T153000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/63
DESCRIPTION:Title: Factors in randomly perturbed graphs\nby Amedeo Sgueglia (LSE) a
s part of Oxford discrete mathematics and probability seminar\n\n\nAbstrac
t\nWe study the model of randomly perturbed dense graphs\, which is the un
ion of any $n$-vertex graph $G_\\alpha$ with minimum degree at least $\\al
pha n$ and the binomial random graph $G(n\,p)$. In this talk\, we shall ex
amine the following central question in this area: to determine when $G_\\
alpha \\cup G(n\,p)$ contains $H$-factors\, i.e. spanning subgraphs cons
isting of vertex disjoint copies of the graph $H$. We offer several new sh
arp and stability results.\nThis is joint work with Julia Böttcher\, Olaf
Parczyk\, and Jozef Skokan.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/63/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sumit Mukherjee (Columbia)
DTSTART;VALUE=DATE-TIME:20211012T130000Z
DTEND;VALUE=DATE-TIME:20211012T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/64
DESCRIPTION:Title: Generalized birthday problem for October 12\nby Sumit Mukherjee
(Columbia) as part of Oxford discrete mathematics and probability seminar\
n\n\nAbstract\nSuppose there are $n$ students in a class. But assume that
not everybody is friends with everyone else\, and there is a graph which d
etermines the friendship structure. What is the chance that there are two
friends in this class\, both with birthdays on October 12? More generally\
, given a simple labelled graph $G_n$ on $n$ vertices\, color each vertex
with one of $c=c_n$ colors chosen uniformly at random\, independent from o
ther vertices. We study the question: what is the number of monochromatic
edges of color 1?\n\nAs it turns out\, the limiting distribution has three
parts\, the first and second of which are quadratic and linear functions
of a homogeneous Poisson point process\, and the third component is an ind
ependent Poisson. In fact\, we show that any distribution limit must belon
g to the closure of this class of random variables. As an application\, we
characterize exactly when the limiting distribution is a Poisson random v
ariable.\n\nThis talk is based on joint work with Bhaswar Bhattacharya and
Somabha Mukherjee.\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/64/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matija Bucić (Princeton/IAS)
DTSTART;VALUE=DATE-TIME:20211109T140000Z
DTEND;VALUE=DATE-TIME:20211109T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/65
DESCRIPTION:by Matija Bucić (Princeton/IAS) as part of Oxford discrete ma
thematics and probability seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/65/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mariana Olvera-Cravioto (UNC Chapel Hill)
DTSTART;VALUE=DATE-TIME:20211123T140000Z
DTEND;VALUE=DATE-TIME:20211123T150000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/66
DESCRIPTION:by Mariana Olvera-Cravioto (UNC Chapel Hill) as part of Oxford
discrete mathematics and probability seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/66/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ashwin Sah (MIT)
DTSTART;VALUE=DATE-TIME:20211026T130000Z
DTEND;VALUE=DATE-TIME:20211026T140000Z
DTSTAMP;VALUE=DATE-TIME:20240328T184111Z
UID:OxfordDMProb/67
DESCRIPTION:by Ashwin Sah (MIT) as part of Oxford discrete mathematics and
probability seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/OxfordDMProb/67/
END:VEVENT
END:VCALENDAR