BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:David Gamarnik (MIT)
DTSTART:20200413T130000Z
DTEND:20200413T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/1
DESCRIPTION:Title: Over
lap gap property: a provable barrier to fast optimization in probabilistic
combinatorial structures\nby David Gamarnik (MIT) as part of Extremal
and probabilistic combinatorics webinar\n\n\nAbstract\nMany combinatorial
optimization problems defined on random instances\, such as random graphs
\, exhibit an apparent gap between the optimal values\, which can be compu
ted by non-constructive means\, and the best values achievable by fast (po
lynomial time) algorithms. Through a combined effort of mathematicians\, c
omputer scientists and statistical physicists\, it became apparent that a
potential\, and in some cases\, a provable barrier for designing fast algo
rithms bridging this gap is an intricate topology of nearly optimal soluti
ons\, in particular the presence of a certain Overlap Gap Property (OGP)\,
which we will introduce in this talk. We will demonstrate how for many su
ch problems the onset of the OGP phase transition indeed nearly coincides
with algorithmically hard regimes and provides a provable barrier to a bro
ad class of polynomial time algorithms. Our examples will include the prob
lem of finding a largest independent set of a random graph\, finding a lar
gest cut in a random hypergraph\, the problem of finding a ground state of
a p-spin model\, and also many models in high-dimensional statistics and
machine learning fields. The classes of algorithms ruled out by the OGP in
clude local algorithms\, Markov Chain Monte Carlo\, Approximate Message Pa
ssing and low-degree polynomial based algorithms.\n\nJoint work with Madhu
Sudan\, Wei-Cuo Chen\, Dmitry Panchenko\, Mustazee Rahman\, Aukosh Jagann
ath and Alex Wein.\n
LOCATION:https://researchseminars.org/talk/EPC/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ehud Friedgut (Weizmann Institute of Science)
DTSTART:20200420T130000Z
DTEND:20200420T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/2
DESCRIPTION:Title: Five
and a half proofs of one theorem\nby Ehud Friedgut (Weizmann Institut
e of Science) as part of Extremal and probabilistic combinatorics webinar\
n\n\nAbstract\nThe Erdos-Ko-Rado theorem is the cornerstone of the modern
field of extremal combinatorics. In this talk we consider one of the varia
nts of this theorem\, in the setting of the product measure on the discret
e cube\, and present (time permitting) several different proofs of it\, us
ing a surprisingly eclectic set of tools.\n
LOCATION:https://researchseminars.org/talk/EPC/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matija Bucić (ETH Zurich)
DTSTART:20200504T130000Z
DTEND:20200504T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/3
DESCRIPTION:Title: Tour
nament quasirandomness from local counting\nby Matija Bucić (ETH Zuri
ch) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstr
act\nA well-known theorem of Chung and Graham states that if h>3 then a to
urnament T is quasirandom if and only if T contains each h-vertex tourname
nt the "correct number" of times as a subtournament. In this talk we inves
tigate the relationship between quasirandomness of T and the count of a si
ngle h-vertex tournament H in T. We consider two types of counts\, the glo
bal one and the local one.\n\nWe first observe that if T has the correct g
lobal count of H and h>6 then quasirandomness of T is only forced if H is
transitive. The next natural question when studying quasirandom objects as
ks whether possessing the correct local counts of H is enough to force qua
sirandomness of T. A tournament H is said to be locally forcing if it has
this property.\n\nVariants of the local forcing problem have been studied
before in both the graph and hypergraph settings. Perhaps the closest anal
ogue of our problem was considered by Simonovits and Sós who looked at wh
ether having "correct counts" of a fixed graph H as an induced subgraph of
G implies G must be quasirandom\, in an appropriate sense. They proved th
at this is indeed the case when H is regular and conjectured that it holds
for all H (except the path on 3 vertices).\n\nContrary to the Simonovits-
Sós conjecture\, in the tournament setting we prove that a constant propo
rtion of all tournaments are not locally forcing. In fact\, any locally fo
rcing tournament must itself be strongly quasirandom. On the other hand\,
unlike the global forcing case\, we construct infinite families of non-tra
nsitive locally forcing tournaments.\n
LOCATION:https://researchseminars.org/talk/EPC/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jinyoung Park (Rutgers University)
DTSTART:20200511T130000Z
DTEND:20200511T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/4
DESCRIPTION:Title: The
number of maximal independent sets in the Hamming cube\nby Jinyoung Pa
rk (Rutgers University) as part of Extremal and probabilistic combinatoric
s webinar\n\n\nAbstract\nLet $Q_n$ be the $n$-dimensional Hamming cube (hy
percube) and $N = 2^n$. We prove that the number of maximal independent se
ts in $Q_n$ is asymptotically $2n2^{N/4}$\, as was conjectured by Ilinca a
nd Kahn in connection with a question of Duffus\, Frankl and Rödl. The va
lue is a natural lower bound derived from a connection between maximal ind
ependent sets and induced matchings. The proof of the upper bound draws on
various tools\, among them “stability” results for maximal independen
t set counts and old and new results on isoperimetric behavior in $Q_n$. T
his is joint with Jeff Kahn.\n
LOCATION:https://researchseminars.org/talk/EPC/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Institute of Technology)
DTSTART:20200518T130000Z
DTEND:20200518T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/5
DESCRIPTION:Title: Coun
ting extensions in random graphs\nby Lutz Warnke (Georgia Institute of
Technology) as part of Extremal and probabilistic combinatorics webinar\n
\n\nAbstract\nWe consider rooted subgraphs in random graphs\, i.e.\, exten
sion counts such as (a) the number of triangles containing a given `root'
vertex\, or (b) the number of paths of length three connecting two given `
root' vertices. \n\nIn 1989 Spencer gave sufficient conditions for the eve
nt that\, whip\, all roots of the binomial random graph G(n\,p) have the s
ame asymptotic number of extensions\, i.e.\, (1 \\pm \\epsilon) times thei
r expected number. \n\nFor the important strictly balanced case\, Spencer
also raised the fundamental question whether these conditions are necessar
y. \n\nWe answer this question by a careful second moment argument\, and d
iscuss some intriguing problems that remain open.\n\nJoint work with Matas
Sileikis\, see arXiv:1911.03012\n\nPassword: the first 6 prime numbers (8
digits in total)\n
LOCATION:https://researchseminars.org/talk/EPC/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexey Pokrovskiy (Birkbeck College)
DTSTART:20200427T130000Z
DTEND:20200427T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/6
DESCRIPTION:Title: Proo
f of Ringel's conjecture\nby Alexey Pokrovskiy (Birkbeck College) as p
art of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nRin
gel conjectured that the edges of the complete graph on 2n+1 vertices can
be decomposed into disjoint copies of any n-edge tree T. This talk will be
about a recent proof of this conjecture for sufficiently large n. This is
joint work with Richard Montgomery and Benny Sudakov.\n
LOCATION:https://researchseminars.org/talk/EPC/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gábor Tardos (Alfréd Rényi Institute)
DTSTART:20200525T130000Z
DTEND:20200525T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/7
DESCRIPTION:Title: Plan
ar point sets determine many pairwise crossing segments\nby Gábor Tar
dos (Alfréd Rényi Institute) as part of Extremal and probabilistic combi
natorics webinar\n\n\nAbstract\nWhat is the largest number $f(n)$ such tha
t $n$ points in the plane (no three on a line) always determine $f(n)$ pai
rwise crossing segments. This natural question was asked by Aronov\, Erdo
̋s\, Goddard\, Kleitman\, Klugerman\, Pach\, and Schulman in 1991 and the
y proved $f(n)=\\Omega(\\sqrt{n})$. The prevailing conjecture was that thi
s bound is far from optimal and $f(n)$ is probably linear in $n$. Neverthe
less\, this lower bound was not improved till last year\, when we proved
with János Pach and Natan Rubin an almost (but not quite) linear lower bo
und. Our result gives $f(n)>n/\\exp(O(\\sqrt{\\log n}))$. Determining whet
her $f(n)$ is truly linear is an intriguing open problem.\n\nPassword: the
first 6 prime numbers (8 digits in total)\n
LOCATION:https://researchseminars.org/talk/EPC/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joonkyung Lee (Universität Hamburg)
DTSTART:20200601T130000Z
DTEND:20200601T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/8
DESCRIPTION:Title: On t
ripartite common graphs\nby Joonkyung Lee (Universität Hamburg) as pa
rt of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nA gr
aph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge
-colouring of the complete graph $K_N$ is minimised by the random colourin
g. Burr and Rosta\, extending a famous conjecture by Erdős\, conjectured
that every graph is common\, which was disproved by Thomason and by Sidore
nko in late 1980s. Collecting new examples for common graphs had not seen
much progress since then\, although very recently\, a few more graphs are
verified to be common by the flag algebra method or the recent progress on
Sidorenko's conjecture.\n\nOur contribution here is to give a new class o
f tripartite common graphs. The first example class is so-called triangle
trees\, which generalises two theorems by Sidorenko and hence answers a qu
estion by Jagger\, Šťovíček\, and Thomason from 1996. We also prove t
hat\, somewhat surprisingly\, given any tree T\, there exists a triangle t
ree such that the graph obtained by adding $T$ as a pendant tree is still
common. Furthermore\, we show that some complete tripartite graphs\, e.g.\
, the octahedron graph $K_{2\,2\,2}$\, are common and conjecture that ever
y complete tripartite graph is common.\n\nJoint work with Andrzej Grzesik\
, Bernard Lidický\, and Jan Volec.\n
LOCATION:https://researchseminars.org/talk/EPC/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Jenssen (University of Birmingham)
DTSTART:20200608T130000Z
DTEND:20200608T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/9
DESCRIPTION:Title: A pr
oof of the Upper Matching Conjecture for large graphs\nby Matthew Jens
sen (University of Birmingham) as part of Extremal and probabilistic combi
natorics webinar\n\n\nAbstract\nWe show that the `Upper Matching Conjectur
e' of Friedland\, Krop\, and Markström and the analogous conjecture of Ka
hn for independent sets in regular graphs hold for all large enough graphs
as a function of the degree. That is\, for every $d$ and every large enou
gh $n$ divisible by $2d$\, a union of $n \\over 2d$ copies of the complete
$d$-regular bipartite graph maximises the number of independent sets and
matchings of any given size over all $d$-regular graphs on $n$ vertices. F
or the proof\, we'll discuss two different approaches to these problems\,
both inspired by statistical physics. This is joint work with Ewan Davies
and Will Perkins.\n
LOCATION:https://researchseminars.org/talk/EPC/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Asaf Ferber (UC Irvine)
DTSTART:20200615T130000Z
DTEND:20200615T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/10
DESCRIPTION:Title: Ind
uced subgraphs with prescribed degrees mod q\nby Asaf Ferber (UC Irvin
e) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstra
ct\nA classical result of Galai asserts that the vertex-set of every graph
can be partitioned into two sets such that each induces a graph with all
degrees even. Scott studied the (harder) problem of
\ndet
ermining for which graphs can we find a partition into arbitrary many part
s\, each of which induces a graph with all odd degrees.\n\nIn this talk we
discuss various extensions of this problem to arbitrary residues mod $q\\
geq 3$. Among other results\, we show that for every $q$\, a typical graph
$G(n\,1/2)$ can be equi-partitioned (up to divisibility conditions) into
$q+1$ sets\, each of which spans a graph with a prescribed degree sequence
.\n
\nSwitching to
a completely unrelated problem: based on idea of the main key lemma of th
e above results\, we give non-trivial bound (but weaker than known results
) on the singularity probability of a random symmetric Bernoulli matrix. T
he new argument avoids both decoupling and distance from random hyperplane
s and it turns this problem into a simple and elegant exercise.\n
\nThe first part of the ta
lk is based on a joint work with Liam Hardiman (UCI) and Michael Krivelevi
ch (Tel Aviv University).\n
LOCATION:https://researchseminars.org/talk/EPC/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annika Heckel (LMU Munich)
DTSTART:20200622T130000Z
DTEND:20200622T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/11
DESCRIPTION:Title: Non
-concentration of the chromatic number\nby Annika Heckel (LMU Munich)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
nThere are many impressive results asserting that the chromatic number of
a random graph is sharply concentrated. In 1987\, Shamir and Spencer showe
d that for any function p=p(n)\, the chromatic number of G(n\,p) takes one
of at most about $n^{1/2}$ consecutive values whp. For sparse random grap
hs\, much sharper concentration is known to hold: Alon and Krivelevich pro
ved two point concentration whenever $p < n^{-1/2-\\varepsilon}$.\n\nHowev
er\, until recently no non-trivial lower bounds for the concentration were
known for any p\, even though the question was raised prominently by Erd
ős in 1992 and by Bollobás in 2004.\n\nIn this talk\, we show that the c
hromatic number of G(n\, 1/2) is not whp contained in any sequence of inte
rvals of length $n^{1/2-o(1)}$\, almost matching Shamir and Spencer's uppe
r bound.\n\nJoint work with Oliver Riordan.\n
LOCATION:https://researchseminars.org/talk/EPC/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anton Bernshteyn (Carnegie Mellon University)
DTSTART:20200629T130000Z
DTEND:20200629T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/12
DESCRIPTION:Title: A f
ast distributed algorithm for $(\\Delta + 1)$-edge-coloring\nby Anton
Bernshteyn (Carnegie Mellon University) as part of Extremal and probabilis
tic combinatorics webinar\n\n\nAbstract\nA celebrated theorem of Vizing sa
ys that every graph $G$ of maximum degree $\\Delta$ is $(\\Delta+1)$-edge-
colorable. In this talk I will describe a deterministic distributed algori
thm in the LOCAL model that finds a $(\\Delta+1)$-edge-coloring in the num
ber of rounds that is polynomial in $\\Delta$ and $\\log n$\, where $n = |
V(G)|$. This is the first distributed algorithm for $(\\Delta + 1)$-edge-c
oloring with running time better than $O(\\mathrm{diameter}(G))$.\n
LOCATION:https://researchseminars.org/talk/EPC/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Józef Balogh (University of Illinois)
DTSTART:20200706T130000Z
DTEND:20200706T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/13
DESCRIPTION:Title: Ext
ensions of Mantel's Theorem\nby Józef Balogh (University of Illinois)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract
\nMantel's theorem is a basic classical theorem of extremal graph theory.
There are many different extensions and generalizations investigated and
many open questions remained.
\nI will talk about three recent results\, including "stabilit
y" and "supersaturation" properties.
\nThe results are partly joined with Clemen\, Kat
ona\, Lidicky\, Linz\, Pfender and Tuza.\n
LOCATION:https://researchseminars.org/talk/EPC/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (Stanford University)
DTSTART:20200713T130000Z
DTEND:20200713T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/14
DESCRIPTION:Title: Ext
ension complexity of low-dimensional polytopes\nby Matthew Kwan (Stanf
ord University) as part of Extremal and probabilistic combinatorics webina
r\n\n\nAbstract\nSometimes\, it is possible to represent a complicated pol
ytope as a projection of a much simpler polytope. To quantify this phenome
non\, the extension complexity of a polytope P is defined to be the minimu
m number of facets in a (possibly higher-dimensional) polytope from which
P can be obtained as a linear projection. In this talk we discuss some ext
remal and probabilistic questions about this notion. This is a joint work
with Lisa Sauermann and Yufei Zhao.\n
LOCATION:https://researchseminars.org/talk/EPC/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shoham Letzter (University College London)
DTSTART:20200720T130000Z
DTEND:20200720T140000Z
DTSTAMP:20260422T225703Z
UID:EPC/15
DESCRIPTION:Title: Mon
ochromatic triangle packings in 2-coloured complete graphs\nby Shoham
Letzter (University College London) as part of Extremal and probabilistic
combinatorics webinar\n\n\nAbstract\nAbstract: We show that every 2-colour
ed complete graph on n vertices contains $n^2/12 + o(n^2)$ pairwise edge-d
isjoint monochromatic triangles. This confirms a conjecture of Erdős\, an
d is asymptotically tight. This is joint work with Vytautas Gruslys.\n
LOCATION:https://researchseminars.org/talk/EPC/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oleg Pikhurko (University of Warwick)
DTSTART:20200727T140000Z
DTEND:20200727T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/16
DESCRIPTION:Title: Com
binatorics of circle squaring\nby Oleg Pikhurko (University of Warwick
) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstrac
t\nTwo sets in a metric space are called equidecomposable if one set can b
e partitioned into finitely many pieces that can be rearranged by isometri
es to form a partition of the other set. I will discuss how combinatorial
ideas and methods helped in various results on "constructive" equidecompos
itions. In particular\, I will present our joint result with Andras Mathe
and Jonathan Noel that a disk and a
\nsquare in the Eucli
dean plane are equidecomposable with Jordan measurable pieces.\n
LOCATION:https://researchseminars.org/talk/EPC/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Felix Joos (Heidelberg University)
DTSTART:20200810T140000Z
DTEND:20200810T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/18
DESCRIPTION:Title: Dec
ompositions of Hypergraphs\nby Felix Joos (Heidelberg University) as p
art of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nSev
eral results on approximate decompositions of hypergraphs are presented in
cluding decompositions into tight Hamilton cycles under very mild assumpti
ons on the host hypergraphs as well as further results on decompositions o
f quasirandom hypergraphs into bounded degree hypergraphs.\n
LOCATION:https://researchseminars.org/talk/EPC/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mehtaab Sawhney (MIT)
DTSTART:20200817T140000Z
DTEND:20200817T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/19
DESCRIPTION:Title: Loc
al limit theorems for subgraph counts\nby Mehtaab Sawhney (MIT) as par
t of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nWe in
troduce a general framework for studying anticoncentration and local limit
theorems for random variables\, including graph statistics. Our methods i
nvolve an interplay between Fourier analysis\, decoupling\, hypercontracti
vity of Boolean functions\, and transference between "fixed-size" and "ind
ependent" models. We also adapt a notion of "graph factors" due to Janson.
\n\nAs a consequence\, we derive a local central limit theorem for connect
ed subgraph counts in the Erdős-Rényi random graph G(n\,p)\, building on
work of Gilmer and Kopparty and of Berkowitz. These results improve an an
ticoncentration result of Fox\, Kwan\, and Sauermann and partially answers
a question of Fox\, Kwan\, and Sauermann. We also derive a local limit ce
ntral limit theorem for induced subgraph counts\, as long as p is bounded
away from a set of "problematic" densities\, partially answering a questio
n of Fox\, Kwan\, and Sauermann. We then prove these restrictions are nece
ssary by exhibiting a disconnected graph for which anticoncentration for s
ubgraph counts at the optimal scale fails for all constant p\, and finding
a graph H for which anticoncentration for induced subgraph counts fails i
n G(n\,1/2). These counterexamples resolve anticoncentration conjectures o
f Fox\, Kwan\, and Sauermann in the negative.\n\nFinally\, we also examine
the behavior of counts of k-term arithmetic progressions in subsets of Z/
nZ and deduce a local limit theorem wherein the behavior is Gaussian at a
global scale but has nontrivial local oscillations (according to a Ramanuj
an theta function). These results improve on results of and answer questio
ns of the authors and Berkowitz\, and answer a question of Fox\, Kwan\, an
d Sauermann.\n
LOCATION:https://researchseminars.org/talk/EPC/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Boris Bukh (Carnegie Mellon University)
DTSTART:20200803T140000Z
DTEND:20200803T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/20
DESCRIPTION:Title: Con
vex holes in high-dimensional point sets\nby Boris Bukh (Carnegie Mell
on University) as part of Extremal and probabilistic combinatorics webinar
\n\n\nAbstract\nIt is well-known that every large enough set P in an Eucli
dean space contains k points in convex position. Such k points are called
"hole" if their convex hull contains no other point of P. We present a new
construction of k-hole-free sets in high-dimensional spaces. Surprisingly
\, the construction is based on non-trivial low-discrepancy sequences used
for numerical integration.
\nJoint work with Ting-Wei Chao and Ron H
olzman.\n
LOCATION:https://researchseminars.org/talk/EPC/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tao Jiang (Miami University)
DTSTART:20200831T140000Z
DTEND:20200831T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/21
DESCRIPTION:Title: On
Turán exponents of graphs\nby Tao Jiang (Miami University) as part of
Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nGiven a f
amily of graphs ${\\mathcal F}$\, the Turán number $ex(n\,{\\mathcal F})$
of ${\\mathcal F}$ is the maximum number of edges in an $n$-vertex graph
$G$ that does not contain any member of ${\\mathcal F}$ as a subgraph. In
a relatively recent breakthrough\, Bukh and Conlon verified a long-standin
g conjecture in extremal graph theory that was credited to Erdős and Simo
novits and re-iterated by other authors by showing that for every rational
number $r$ between $1$ and $2$ there exists a family ${\\mathcal F}$ of g
raphs such that $ex(n\,{\\mathcal F})=\\Theta(n^r)$.
\n\nThere is a stronge
r conjecture that states that for every rational $r$ between $1$ and $2$ t
here exists a single bipartite graph $F$ such that $ex(n\,F)=\\Theta(n^r)$
. This conjecture is still open. In this talk\, we survey recent progress
on this stronger conjecture.\n
LOCATION:https://researchseminars.org/talk/EPC/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guillem Perarnau (Universitat Politècnica de Catalunya)
DTSTART:20200907T140000Z
DTEND:20200907T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/22
DESCRIPTION:Title: Ext
remal stationary values for directed random graphs\nby Guillem Perarna
u (Universitat Politècnica de Catalunya) as part of Extremal and probabil
istic combinatorics webinar\n\n\nAbstract\n: In this talk\, we will discus
s the minimum positive value of the stationary distribution of a random wa
lk on a directed random graph with given (bounded) degrees. While for undi
rected graphs the stationary distribution is simply determined by the degr
ees\, the graph geometry plays a major role in the directed case. Understa
nding typical stationary values is key to determining the mixing time of t
he walk\, as shown by Bordenave\, Caputo\, and Salez. However\, typical re
sults provide no information on the minimum value\, which is important for
many applications. Recently\, Caputo and Quattropani showed that the stat
ionary distribution exhibits logarithmic fluctuations provided that the mi
nimum degree is at least 2. In this talk\, we show that dropping the minim
um degree condition may yield polynomially smaller stationary values of th
e form $n^{-(1+C+o(1))}$\, for a constant C determined by the degree distr
ibution. In particular\, C is the combination of two factors: (1) the cont
ribution of atypically thin in-neighborhoods\, controlled by subcritical b
ranching processes\; and (2) the contribution of atypically "light" direct
ed paths\, controlled by large deviation rate functions. As a by-product o
f our proof\, we also determine the mean hitting time in random digraphs.
This is joint work with Xing Shi Cai.\n
LOCATION:https://researchseminars.org/talk/EPC/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Postle (University of Waterloo)
DTSTART:20200914T140000Z
DTEND:20200914T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/23
DESCRIPTION:Title: Fur
ther progress towards Hadwiger's conjecture\nby Luke Postle (Universit
y of Waterloo) as part of Extremal and probabilistic combinatorics webinar
\n\n\nAbstract\nIn 1943\, Hadwiger conjectured that every graph with no $K
_t$ minor is $(t-1)$-colorable for every $t\\ge 1$. In the 1980s\, Kostoch
ka and Thomason independently proved that every graph with no $K_t$ minor
has average degree $O(t\\sqrt{\\log t})$ and hence is $O(t\\sqrt{\\log t})
$-colorable. Recently\, Norin\, Song and I showed that every graph with n
o $K_t$ minor is $O(t(\\log t)^{\\beta})$-colorable for every $\\beta > 1/
4$\, making the first improvement on the order of magnitude of the $O(t\\s
qrt{\\log t})$ bound. Here we show that every graph with no $K_t$ minor is
$O(t (\\log t)^{\\beta})$-colorable for every $\\beta > 0$\; more specifi
cally\, they are $O(t (\\log \\log t)^{6})$-colorable.\n
LOCATION:https://researchseminars.org/talk/EPC/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peter Allen (LSE)
DTSTART:20200921T140000Z
DTEND:20200921T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/24
DESCRIPTION:Title: Wea
k expansion and strong regularity\nby Peter Allen (LSE) as part of Ext
remal and probabilistic combinatorics webinar\n\n\nAbstract\nIn previous w
ork\, embedding large graphs into subgraphs of random graphs is generally
done vertex by vertex\, using the Sparse Regularity Lemma\, looking only o
ne step ahead\, and maintaining regularity properties throughout using a t
echnical tool called inheritance of regularity. This approach cannot work
for very sparse random graphs\, even though it is believed that the embedd
ing statements do remain true. We develop an alternative approach\, showin
g that given a partial embedding and looking several steps ahead\, the set
of extensions has a weak expansion property\; leveraging this one can per
form vertex by vertex embedding without the need for inheritance of regula
rity\, and as a result the approach works in sparser random graphs. In ord
er to make this approach work\, we need to use a strengthened version of t
he Sparse Regularity Lemma.\n\nI will outline the new approach briefly\, a
nd explain how to use it to prove two new results.\n\n(i) For any $\\gamm
a>0$ and integers $r$\, $D$ and $\\Delta$\, there is $c>0$ such that if $p
\\ge n^{-1/D+\\gamma}$ then $\\Gamma=G(n\,p)$ with high probability has th
e following property. However $\\Gamma$ is $r$-coloured\, there is a colou
r class which contains all $cn$-vertex graphs with degeneracy at most $D$
and maximum degree at most $\\Delta$.\n\n(ii) If $p\\ge n^{-1+o(1)}$\, the
n the random $k$-uniform hypergraph $\\Gamma=G^{(k)}(n\,p)$ with high prob
ability has the following property. Every subgraph $G$ of $\\Gamma$ with m
inimum codegree at least $(\\frac12+o(1))pn$ contains a tight Hamilton cyc
le.\n\nBoth these results are asymptotically optimal. This is joint work w
ith Julia Böttcher and with Olaf Parczyk and Vincent Pfenninger.\n
LOCATION:https://researchseminars.org/talk/EPC/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lisa Sauermann (Stanford University)
DTSTART:20201019T140000Z
DTEND:20201019T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/25
DESCRIPTION:Title: On
polynomials that vanish to high order on most of the hypercube\nby Lis
a Sauermann (Stanford University) as part of Extremal and probabilistic co
mbinatorics webinar\n\n\nAbstract\nMotivated by higher vanishing multiplic
ity generalizations of Alon's Combinatorial Nullstellensatz and its applic
ations\, we study the following problem: for fixed k and n large with resp
ect to k\, what is the minimum possible degree of a polynomial P in R[x_1\
,...\,x_n] such that P(0\,…\,0) is non-zero and such that P has zeroes o
f multiplicity at least k at all points in ${0\,1}^n$ except the origin? F
or k=1\, a classical theorem of Alon and Füredi states that the minimum p
ossible degree of such a polynomial equals n. We solve the problem for all
k>1\, proving that the answer is n+2k−3. Joint work with Yuval Wigderso
n.\n
LOCATION:https://researchseminars.org/talk/EPC/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Ellis (University of Bristol)
DTSTART:20201109T140000Z
DTEND:20201109T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/26
DESCRIPTION:Title: A r
emark on the transitive case of the union-closed conjecture\nby David
Ellis (University of Bristol) as part of Extremal and probabilistic combin
atorics webinar\n\n\nAbstract\nWe give a short proof that the union-closed
conjecture holds in the special case where the union-closed family in que
stion is generated by all translates of a fixed subset of an Abelian group
. Joint work with James Aaronson (Oxford) and Imre Leader (Cambridge).\n
LOCATION:https://researchseminars.org/talk/EPC/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Moumanti Podder (NYU Shanghai)
DTSTART:20201116T140000Z
DTEND:20201116T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/27
DESCRIPTION:Title: Som
e combinatorial games on rooted multi-type Galton-Watson trees\nby Mou
manti Podder (NYU Shanghai) as part of Extremal and probabilistic combinat
orics webinar\n\n\nAbstract\nIn a rooted multi-type Galton-Watson branchin
g process\, the root is assigned a colour from a finite set $\\Sigma$ of c
olours according to some probability distribution P\, and a vertex of the
tree\, conditioned on its colour $\\sigma \\in \\Sigma$\, gives birth to o
ffspring according to some probability distribution $\\chi_{\\sigma}$ on $
\\mathbb{N}_{0}^{\\Sigma}$. In particular\, one may consider $\\Sigma = \\
{{\\rm red}\, {\\rm blue}\\}$ and the resulting random tree\, denoted T\,
can be viewed as a directed random graph if each edge is attributed a dire
ction from parent to child. I consider the normal\, misere and escape game
s on T\, each played between P1 and P2\, with P1 being allowed to move the
token only along monochromatic directed edges and P2 being allowed to mov
e the token only along non-monochromatic directed edges. I then investigat
e the probabilities of win\, loss and (where pertinent) draw of each playe
r as fixed points of distributional recursions\, establish inequalities be
tween win / loss / draw probabilities of the players across different game
s\, seek possible phase transitions in win / loss / draw probabilities as
the parameters involved in the offspring distributions are made to vary\,
study expected durations of the games etc.\n
LOCATION:https://researchseminars.org/talk/EPC/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hao Huang (Emory University)
DTSTART:20201026T140000Z
DTEND:20201026T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/28
DESCRIPTION:Title: On
local Turán problems\nby Hao Huang (Emory University) as part of Extr
emal and probabilistic combinatorics webinar\n\n\nAbstract\nSince its form
ulation\, Turán's hypergraph problems have been among the most challengin
g open problems in extremal combinatorics. One of them is the following: g
iven a 3-uniform hypergraph F on n vertices in which any five vertices spa
n at least one edge\, prove that $|F|\\ge(1/4 -o(1))\\binom{n}{3}$. The co
nstruction showing that this bound would be best possible is simply ${X \\
choose 3} \\cup {Y \\choose 3}$ where X and Y evenly partition the vertex
set. This construction satisfies the following more general (2p+1\, p+1)-
property: any set of 2p+1 vertices spans a complete sub-hypergraph on p+1
vertices.\n\nIn this talk\, we will show that\, quite surprisingly\, for a
ll p>2 the (2p+1\,p+1)-property implies the conjectured lower bound. Furth
ermore\, we will prove that for integers r\, a >= 2\, the minimum edge den
sity of an r-uniform hypergraph satisfying the (ap+1\, p+1)-property tends
to $1/a^{r-1}$ when p tends to infinity.\n\nJoint work with Peter Frankl
and Vojtěch Rödl.\n
LOCATION:https://researchseminars.org/talk/EPC/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ferenc Benc (Rényi Institute)
DTSTART:20201012T140000Z
DTEND:20201012T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/29
DESCRIPTION:Title: Ato
ms of the matching measure\nby Ferenc Benc (Rényi Institute) as part
of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nWe prov
e that the matching measure of an infinite vertex-transitive connected gra
ph has no atoms. Generalizing the results of Salez\, we show that for an e
rgodic non-amenable unimodular random rooted graph with uniformly bounded
degrees\, the matching measure has only finitely many atoms. Ku and Chen p
roved the analogue of the Gallai-Edmonds structure theorem for non-zero ro
ots of the matching polynomial for finite graphs. We extend their results
for infinite graphs. We also show that the corresponding Gallai-Edmonds de
composition is compatible with the zero temperature monomer-dimer model. J
oint work with András Mészáros.\n
LOCATION:https://researchseminars.org/talk/EPC/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jonathan Noel (University of Victoria)
DTSTART:20200928T140000Z
DTEND:20200928T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/30
DESCRIPTION:Title: Non
-bipartite k-common graphs\nby Jonathan Noel (University of Victoria)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
nHow many monochromatic copies of H must appear in a k-edge colouring of a
large complete graph? The graph H is said to be "k-common" if the number
of monochromatic H is asymptotically minimized by a random colouring. Rece
nt progress on Sidorenko's Conjecture has provided many new examples of bi
partite k-common graphs\; however\, it is not known if such graphs can hav
e high chromatic number. We construct the first examples of non-bipartite
k-common graphs for $k \\ge 3$\, addressing a problem raised by Jagger\,
Šťovíček and Thomason in 1996. This talk is based on joint work with D
aniel Kráľ\, Sergey Norin\, Jan Volec and Fan Wei.\n
LOCATION:https://researchseminars.org/talk/EPC/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Richard Montgomery (University of Birmingham)
DTSTART:20201005T140000Z
DTEND:20201005T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/31
DESCRIPTION:Title: A s
olution to Erdős and Hajnal's odd cycle problem\nby Richard Montgomer
y (University of Birmingham) as part of Extremal and probabilistic combina
torics webinar\n\n\nAbstract\nI will discuss how to construct cycles of ma
ny different lengths in graphs\, in particular answering the following two
problems on odd and even cycles. In 1966\, Erdős and Hajnal asked whethe
r the sum of the reciprocals of the odd cycle lengths in a graph diverges
as the chromatic number increases. Later\, Erdős asked whether there 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\nThis is joint work with Hong Liu.
\n
LOCATION:https://researchseminars.org/talk/EPC/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:ZOOM-ISSUE
DTSTART:20200824T140000Z
DTEND:20200824T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/32
DESCRIPTION:Title: Jan
Grebik's talk rescheduled to Nov 23\nby ZOOM-ISSUE as part of Extrema
l and probabilistic combinatorics webinar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/EPC/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrey Kupavskii (Moscow Institute of Physics and Technology)
DTSTART:20201102T140000Z
DTEND:20201102T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/33
DESCRIPTION:Title: The
extremal number of surfaces\nby Andrey Kupavskii (Moscow Institute of
Physics and Technology) as part of Extremal and probabilistic combinatori
cs webinar\n\n\nAbstract\nIn 1973\, Brown\, Erdős and Sós proved that if
H is a 3-uniform hypergraph on n vertices which contains no triangulation
of the sphere\, then H has at most $O(n^{5/2})$ edges\, and this bound is
the best possible up to a constant factor. Resolving a conjecture of Lini
al\, also reiterated by Keevash\, Long\, Narayanan\, and Scott\, we show t
hat the same result holds for triangulations of the torus. Furthermore\, w
e extend our result to every closed orientable surface S. Joint work with
Alexandr Polyanskii\, István Tomon and Dmitriy Zakharov\n
LOCATION:https://researchseminars.org/talk/EPC/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Grebík (University of Warwick)
DTSTART:20201123T140000Z
DTEND:20201123T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/34
DESCRIPTION:Title: Lar
ge deviation principle for graphons\nby Jan Grebík (University of War
wick) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbs
tract\nIn this talk we discuss the large deviation principle (LDP) for a s
equence of measures on the graphon space which is obtained by sampling fro
m a fixed graphon W.\n\nThe large deviation theory for the Erdős–Rényi
random graph (sampling from a constant graphon) and its applications were
developed by Chatterjee and Varadhan.\n\nParticularly\, the Erdős–Rén
yi random graph satisfies LDP with the speed $2/n^2$.\n\nWe show that when
sampling from a general graphon one can get LDPs with two interesting spe
eds\, namely\, $1/n$ and $2/n^2$. We completely characterize the situation
for the speed $1/n$. In the case $2/n^2$\, we describe the LDP when sampl
ing from a step graphon.\n\nTime permitting\, we compare our work with a r
ecent result by Borgs\, Chayes\, Gaudio\, Petti and Sen on LDP for block m
odels.\n\nThis is a joint work with O.Pikhurko.\n
LOCATION:https://researchseminars.org/talk/EPC/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Conlon (California Institute of Technology)
DTSTART:20201214T140000Z
DTEND:20201214T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/35
DESCRIPTION:Title: Exp
onential improvements in Ramsey theory\nby David Conlon (California In
stitute of Technology) as part of Extremal and probabilistic combinatorics
webinar\n\n\nAbstract\nThe Ramsey number r(t) is the smallest natural num
ber n such that every two-colouring of the edges of $K_n$ contains a monoc
hromatic copy of $K_t$. It has been known for over seventy years that the
Ramsey number lies between $\\left(\\sqrt{2}\\right)^t$ and $4^t$\, but im
proving either bound by an exponential factor remains a difficult open pro
blem. In this lecture\, we discuss several related problems where such an
exponential improvement has been achieved.\n\nThis talk reflects joint wor
k with many co-authors\, including Asaf Ferber\, Jacob Fox\, Andrey Grinsh
pun\, Xiaoyu He and Yuval Wigderson.\n
LOCATION:https://researchseminars.org/talk/EPC/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benny Sudakov (ETH Zürich)
DTSTART:20201130T140000Z
DTEND:20201130T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/36
DESCRIPTION:Title: Thr
ee problems on 3-chromatic intersecting hypergraphs\nby Benny Sudakov
(ETH Zürich) as part of Extremal and probabilistic combinatorics webinar\
n\n\nAbstract\nThe study of non-2-colorable hypergraphs has a long history
going back almost 60 years to the famous problem of Erdos and Hajnal\, wh
o asked for the minimum number of edges in such a k-uniform hypergraph. In
1973 Erdos and Lovasz further asked what happens if in addition to non-2-
colorability one requires the hypergraph to be intersecting. Their seminal
paper\, which introduced the local lemma\, contains three intriguing prob
lems on the properties of 3-chromatic intersecting hypergraphs. Despite th
ese problems being reiterated several times over the years by Erdos and ot
her researchers\, remarkably they withstood any progress up until now. In
this talk\, we prove that in any 3-chromatic intersecting k-uniform hyperg
raph there are at least $k^{1/2-o(1)}$ different intersection sizes among
pairs of edges. This proves a conjecture of Erdos and Lovasz in a strong f
orm and substantially improves their previously best bound of at least 3 d
ifferent intersection sizes.\n\nJoint work with M. Bucic and S. Glock\n
LOCATION:https://researchseminars.org/talk/EPC/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Petér Pál Pach (Budapest University of Technology and Economics)
DTSTART:20201207T140000Z
DTEND:20201207T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/37
DESCRIPTION:Title: Avo
iding arithmetic progressions or right angles\nby Petér Pál Pach (Bu
dapest University of Technology and Economics) as part of Extremal and pro
babilistic combinatorics webinar\n\n\nAbstract\nIn this talk we discuss so
me bounds about sets avoiding certain arithmetic or geometric configuratio
ns in $F_p^n$ (or more generally\, in $Z_m^n$). In particular\, we will co
nsider the case of 6-term arithmetic progressions in $Z_6^n$\, and sets av
oiding right angles in $F_p^n$. Our methods can also be used to bound the
maximum possible size of a binary code where no two codewords have Hamming
distance divisible by a fixed prime p. \n\nJoint work with Palincza and
with Bursics\, Matolcsi and Schrettner.\n
LOCATION:https://researchseminars.org/talk/EPC/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nati Linial (Hebrew University of Jerusalem)
DTSTART:20201221T140000Z
DTEND:20201221T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/38
DESCRIPTION:Title: Geo
desic geometry on graphs\nby Nati Linial (Hebrew University of Jerusal
em) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstr
act\nWe investigate a graph theoretic analog of geodesic geometry. In a gr
aph G=(V\,E) we consider a system of paths $P=\\{Pu\,v | u\,v \\in V\\}$ w
here $Pu\,v$ connects vertices u and v. This system is consistent in that
if vertices y\,z are in $Pu\,v$\, then the sub-path of $Pu\,v$ between the
m coincides with $Py\,z$. A map $w:E \\to (0\,\\infty)$ is said to induce
P if for every $u\,v \\in V$ the path $Pu\,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 are very rare\, whereas there exist infinit
ely many 2-connected metrizable graphs.\n\n\nJoint work with my student Da
niel Cizma\n
LOCATION:https://researchseminars.org/talk/EPC/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noga Alon (Princeton University)
DTSTART:20210104T140000Z
DTEND:20210104T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/39
DESCRIPTION:Title: Spl
itting necklaces\nby Noga Alon (Princeton University) as part of Extre
mal and probabilistic combinatorics webinar\n\n\nAbstract\nIt is known tha
t one can cut any opened necklace with beads of $n$ types in at most $(k-1
)n$ points and partition the resulting intervals into k collections\, each
containing the same number of beads of each type (up to 1). This number o
f cuts is optimal. I will discuss some recent advances in the study of thi
s problem focusing on its algorithmic aspects and on the case of random ne
cklaces. \n\nBased on joint work with Anrdei Graur and on joint work in pr
ogress with Janos Pach and Gabor Tardos.\n
LOCATION:https://researchseminars.org/talk/EPC/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vishesh Jain (Stanford University)
DTSTART:20210301T140000Z
DTEND:20210301T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/40
DESCRIPTION:Title: Tow
ards the sampling Lovász local lemma\nby Vishesh Jain (Stanford Unive
rsity) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nFor a constraint satisfaction problem which satisfies the conditio
n of the Lovász local lemma (LLL)\, the celebrated algorithm of Moser and
Tardos allows one to efficiently find a satisfying assignment. In the pas
t few years\, much work has gone into understanding whether one can effici
ently sample from approximately the uniform distribution on satisfying ass
ignments\, or approximately count the number of satisfying assignments\, u
nder LLL-like conditions.\n\nI will discuss recent algorithmic progress on
this problem\, joint with Huy Tuan Pham (Stanford) and Thuy Duong Vuong (
Stanford).\n
LOCATION:https://researchseminars.org/talk/EPC/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peter Winkler (Dartmouth College)
DTSTART:20210308T140000Z
DTEND:20210308T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/41
DESCRIPTION:Title: On
the Shape of Large Permutations\nby Peter Winkler (Dartmouth College)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
nWhat do large permutations look like? We can in some cases answer this q
uestion with the help of limit structures called "permutons\," and a varia
tional principle. Examples show nice apparent behavior and a contrast to t
he case of graphs and graphons.\n\nJoint work with Rick Kenyon\, Dan Krá
ľ and Charles Radin\; later\, with Chris Coscia\, Sayan Das\, Sumit Mukhe
rjee and Martin Tassy.\n
LOCATION:https://researchseminars.org/talk/EPC/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Hladky (Czech Academy of Sciences)
DTSTART:20210111T140000Z
DTEND:20210111T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/42
DESCRIPTION:Title: Fli
p processes on finite graphs and dynamical systems they induce on graphons
\nby Jan Hladky (Czech Academy of Sciences) as part of Extremal and pr
obabilistic combinatorics webinar\n\n\nAbstract\nWe introduce a class of r
andom graph processes\, which we call \\emph{flip processes}. Each such pr
ocess is given by a \\emph{rule} which is just a function $\\mathcal{R}:\\
mathcal{H}_k\\rightarrow \\mathcal{H}_k$ from all labelled $k$-vertex grap
hs into itself ($k$ is fixed). Now\, the process starts with a given $n$-v
ertex graph $G_0$. In each step\, the graph $G_i$ is obtained by sampling
$k$ random vertices $v_1\,\\ldots\,v_k$ of $G_{i-1}$ and replacing the ind
uced graph $G_{i-1}[v_1\,\\ldots\,v_k]$ by $\\mathcal{R}(G_{i-1}[v_1\,\\ld
ots\,v_k])$. This class contains several previously studied processes incl
uding the Erdos-Renyi random graph process and the random triangle removal
.\n\nGiven a flip processes with a rule $\\mathcal{R}$ we construct time-i
ndexed trajectories $\\Phi:\\mathcal{W}\\times [0\,\\infty)\\rightarrow\\m
athcal{W}$ in the space of graphons. We prove that with high probability\,
starting with a large finite graph $G_0$ which is close to a graphon $W_0
$ in the cut norm distance\, the flip process will stay in a thin sausage
around the trajectory $(\\Phi(W_0\,t))_{t=0}^\\infty$ (after rescaling the
time by the square of the order of the graph).\n\nThese graphon trajector
ies are then studied from the perspective of dynamical systems. We prove t
hat two trajectories cannot form a confluence\, give an example of a proce
ss with an oscilatory trajectory\, and address the question of existence a
nd stability of fixed points and periodic trajectories.\n
LOCATION:https://researchseminars.org/talk/EPC/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Corrine Yap (Rutgers University)
DTSTART:20210118T140000Z
DTEND:20210118T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/43
DESCRIPTION:Title: A T
opological Turán Problem\nby Corrine Yap (Rutgers University) as part
of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nThe cl
assical Turán problem asks: given a graph H\, how many edges can an n-ver
tex graph have while containing no isomorphic copy of H? By viewing (k+1)-
uniform hypergraphs as k-dimensional simplicial complexes\, we can ask a t
opological version of this (first posed by Nati Linial): given a k-dimensi
onal 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 give an answer fo
r general k\, by way of dependent random choice and the combinatorial noti
on of a trace-bounded hypergraph. Joint work with Jason Long and Bhargav N
arayanan.\n
LOCATION:https://researchseminars.org/talk/EPC/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marcus Michelen (University of Illinois at Chicago)
DTSTART:20210125T140000Z
DTEND:20210125T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/44
DESCRIPTION:Title: Roo
ts of random polynomials near the unit circle\nby Marcus Michelen (Uni
versity of Illinois at Chicago) as part of Extremal and probabilistic comb
inatorics webinar\n\n\nAbstract\nIt is a well-known (but perhaps surprisin
g) fact that a polynomial with independent random coefficients has most of
its roots very close to the unit circle. Using a probabilistic perspectiv
e\, we understand the behavior of roots of random polynomials exceptionall
y close to the unit circle and prove several limit theorems\; these result
s resolve several conjectures of Shepp and Vanderbei. We will also discuss
how our techniques provide a heuristic\, probabilistic explanation for wh
y random polynomials tend to have most roots near the unit circle. Based o
n joint work with Julian Sahasrabudhe.\n
LOCATION:https://researchseminars.org/talk/EPC/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lior Gishboliner (Tel-Aviv University)
DTSTART:20210201T140000Z
DTEND:20210201T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/45
DESCRIPTION:Title: Dis
crepancy of spanning trees\nby Lior Gishboliner (Tel-Aviv University)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
nRecently there has been some interest in discrepancy-type problems on gra
phs. Here we study the discrepancy of spanning trees. For a connected grap
h $G$ and a number of colors $r$\, what is the maximum $d = d_r(G)$ such t
hat in any $r$-coloring of the edges of $G$\, there is a spanning tree wit
h at least $(n-1)/r + d$ edges of the same color? $d_r(G)$ is called the $
r$-color spanning-tree discrepancy of $G$\, and has been recently studied
by Balogh\, Csaba\, Jing and Pluhar. As our main result\, we show that und
er very mild conditions (for example\, if $G$ is 3-connected)\, $d_r(G)$ i
s equal\, up to a constant factor\, to the minimal integer s such that G c
an be separated into r equal parts $V_1\,...\,V_r$ by deleting at most $s$
vertices. This strong and perhaps surprising relation between these two p
arameters allows us to estimate $d_r(G)$ for many graphs of interest. In p
articular\, we reprove and generalize results of Balogh et al.\, as well a
s obtain new ones. Some tight asymptotic results for particular graph clas
ses are also obtained. \n\nJoint work with Michael Krivelevich and Peleg M
ichaeli.\n
LOCATION:https://researchseminars.org/talk/EPC/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hong Liu (University of Warwick)
DTSTART:20210208T140000Z
DTEND:20210208T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/46
DESCRIPTION:Title: Opt
imal high dimension geometric construction for Ramsey-Turan theory\nby
Hong Liu (University of Warwick) as part of Extremal and probabilistic co
mbinatorics webinar\n\n\nAbstract\nCombining two classical notions in extr
emal graph theory\, the study of Ramsey-Turan theory seeks to determine\,
for integers $m\\le n$ and $p \\leq q$\, the number $RT_p(n\,K_q\,m)$\, wh
ich is the maximum size of an $n$-vertex $K_q$-free graph in which every s
et of at least $m$ vertices contains a $K_p$.\n\nTwo major open problems i
n this area from the 80s ask:\n(1) whether the asymptotic extremal structu
re for the general case exhibits certain periodic behaviour\, resembling t
hat of the special case when $p=2$ \;\n(2) to construct analogues of the B
ollobas-Erdos graph with densities other than powers of $1/2$.\n\nWe refut
e the first conjecture by witnessing asymptotic extremal structures that a
re drastically different from the $p=2$ case\; and address the second prob
lem by constructing Bollobas-Erdos-type graphs with any rational density u
p to $\\frac{1}{2}$ using high dimension complex sphere.\n\nJoint work wit
h Christian Reiher\, Maryam Sharifzadeh and Katherine Staden.\n
LOCATION:https://researchseminars.org/talk/EPC/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Suk (UC San Diego)
DTSTART:20210329T140000Z
DTEND:20210329T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/48
DESCRIPTION:Title: Cli
ques and sunflowers under bounded VC-dimension\nby Andrew Suk (UC San
Diego) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nThe VC-dimension of a set system is one of the most useful combina
torial parameters that measures its complexity\, and\, apart from its geom
etric applications\, it has proved to be relevant in many other areas such
as statistics\, logic\, and learning theory. In this talk\, I will discu
ss two well-known combinatorial problems under bounded VC-dimension: estim
ating multicolor Ramsey numbers and the sunflower problem. This talk is b
ased on joint works with Jacob Fox and Janos Pach.\n
LOCATION:https://researchseminars.org/talk/EPC/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jonathan Tidor (MIT)
DTSTART:20210215T140000Z
DTEND:20210215T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/49
DESCRIPTION:Title: Equ
iangular lines with a fixed angle\nby Jonathan Tidor (MIT) as part of
Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nA configur
ation of N lines through the origin in d-dimensional Euclidean space is ca
lled equiangular if the lines are pairwise separated by the same angle. A
natural and long-standing problem in discrete geometry is to determine the
maximum size of a configuration of equiangular lines in a given dimension
.\n\nWe determine\, for each fixed angle and in all sufficiently large dim
ensions\, the maximum number of equiangular lines separated by this given
angle. Surprisingly\, this maximum depends on spectral graph theoretic pro
perties of the fixed angle.\n\nOur proof involves the following novel resu
lt that seems to be of independent interest: A bounded degree connected gr
aph has sublinear second eigenvalue multiplicity (that is\, the multiplici
ty of the second-largest eigenvalue of the adjacency matrix of the graph i
s sublinear in the number of vertices).\n\nJoint work with Zilin Jiang\, Y
uan Yao\, Shengtong Zhang\, and Yufei Zhao.\n
LOCATION:https://researchseminars.org/talk/EPC/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Glock (ETH Zurich)
DTSTART:20210412T140000Z
DTEND:20210412T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/50
DESCRIPTION:Title: Lon
g induced paths in sparse random graphs (rescheduled from Feb 22)\nby
Stefan Glock (ETH Zurich) as part of Extremal and probabilistic combinator
ics webinar\n\n\nAbstract\nThe study of induced trees in random graphs was
initiated by Erdős and Palka in the 80s. Many interesting questions rema
in unanswered\, especially in the sparse case when the average degree is c
onstant. For instance: what is the length of a longest induced path?\n\nNa
tural algorithms produce an induced path of length roughly half the conjec
tured optimal value\, which has not been improved in the last 30 years.\n\
nWe show that one can do better than that\, which answers a question of Fe
rnandez de la Vega. Unfortunately\, we only get halfway towards the upper
bound. We will explain the main ideas and explore possible ways to close t
he remaining gap.\n
LOCATION:https://researchseminars.org/talk/EPC/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ashwin Sah (MIT)
DTSTART:20210315T140000Z
DTEND:20210315T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/51
DESCRIPTION:Title: Pop
ular differences for matrix patterns\nby Ashwin Sah (MIT) as part of E
xtremal and probabilistic combinatorics webinar\n\n\nAbstract\nWe study ma
trix patterns including those of the form $x\,x+M_1d\,x+M_2d\,x+(M_1+M_2)d
$ in abelian groups $G^k$ for integer matrices $M_1\,M_2$. If $A\\subseteq
G^k$ has density $\\alpha$\, one might expect based on recent conjectures
of Ackelsberg\, Bergelson\, and Best that there is $d\\neq 0$ such that \
\[\\#\\{x \\in G^k: x\, x+M_1d\, x+M_2d\, x+(M_1+M_2)d \\in A\\} \\ge (\\a
lpha^4-o(1))|G|^k\\] as long as $M_1\,M_2\,M_1\\pm M_2$ define automorphis
ms of $G^k$. We show this conjecture holds in $G = \\mathbb{F}_p^n$ for od
d $p$ given an additional spectral condition\, but is false without this c
ondition. Explicitly\, we show the rotated squares pattern is false
over $\\mathbb{F}_5^n$. This is in surprising contrast to the theory of p
opular differences of one-dimensional patterns.\n
LOCATION:https://researchseminars.org/talk/EPC/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Abhishek Methuku (University of Birmingham)
DTSTART:20210322T140000Z
DTEND:20210322T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/52
DESCRIPTION:Title: A p
roof of the Erdős–Faber–Lovász conjecture\nby Abhishek Methuku (
University of Birmingham) as part of Extremal and probabilistic combinator
ics webinar\n\n\nAbstract\nThe celebrated Erdős–F
aber–Lovász conjecture (posed in 1972) states that the chromatic in
dex of any linear hypergraph on n vertices is at most n. In this talk\, I
will sketch a proof
\nof this conjecture for ever
y large n.\n\nHistory of the problem: Erdős problems\, UC
SD.\n\nJoint work with D. Kang\, T. Kelly\, D.Kuhn and D. Osthus.\n
LOCATION:https://researchseminars.org/talk/EPC/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Sidorenko (Rényi Institute of Mathematics)
DTSTART:20210405T140000Z
DTEND:20210405T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/53
DESCRIPTION:Title: On
the asymptotic behavior of the classical Turán numbers\nby Alexander
Sidorenko (Rényi Institute of Mathematics) as part of Extremal and probab
ilistic combinatorics webinar\n\n\nAbstract\nA subset of vertices in a hyp
ergraph H is called independent if it does not contain an edge of $H$. The
independence number $\\alpha(H)$ is the size of the largest independent s
et. The classical Turán number $T(n\,\\alpha+1\,r)$ is the minimum number
of edges in an $n$-vertex $r$-uniform hypergraph $H$ with $\\alpha(H) \\l
e \\alpha$. In other words\, $\\binom{n}{r} - T(n\,k\,r)$ is the largest n
umber of edges in an $n$-vertex $r$-uniform hypergraph that does not conta
in a complete k-vertex subgraph.\n\nThe limit of $T(n\,k\,r) / \\binom{n}{
r}$ with $n\\to\\infty$ is known as Turán density $t(k\,r)$. Pál Turán
in 1941 proved that $t(\\alpha+1\,2) = 1/\\alpha$. It is widely believed t
hat $t(\\alpha+1\,3) = 4/\\alpha^2$. I will discuss the asymptotic behavio
r of $t(k\,r)$ in respect to $k$ and $r$. I will also cover similar topics
for the codegree Turán problem.\n
LOCATION:https://researchseminars.org/talk/EPC/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Torsten Mütze (University of Warwick)
DTSTART:20210426T140000Z
DTEND:20210426T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/54
DESCRIPTION:Title: Com
binatorial generation via permutation languages\nby Torsten Mütze (Un
iversity of Warwick) as part of Extremal and probabilistic combinatorics w
ebinar\n\n\nAbstract\nIn this talk I present a general and versatile algor
ithmic framework for exhaustively generating a large variety of different
combinatorial objects\, based on encoding them as permutations\, which pro
vides a unified view on many known results and allows us to prove many new
ones. This talk gives an overview over three main applications of our fra
mework: (1) the generation of pattern-avoiding permutations\; (2) the gene
ration of various classes of rectangulations\; (3) the generation of latti
ce congruences of the weak order on the symmetric group and of graph assoc
iahedra.\n\nThis talk is based on joint work with Liz Hartung\, Hung P. Ho
ang\, and Aaron Williams (SODA 2020)\, and with Arturo Merino (SoCG 2021)
and Jean Cardinal.\n
LOCATION:https://researchseminars.org/talk/EPC/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Glock (ETH Zurich)
DTSTART:20210222T140000Z
DTEND:20210222T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/55
DESCRIPTION:Title: res
cheduled to to Apr 12 due to technical problems\nby Stefan Glock (ETH
Zurich) as part of Extremal and probabilistic combinatorics webinar\n\nAbs
tract: TBA\n
LOCATION:https://researchseminars.org/talk/EPC/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annie Raymond (University of Massachusetts)
DTSTART:20210419T140000Z
DTEND:20210419T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/56
DESCRIPTION:Title: Gra
ph Density Inequalities\, Sums of Squares and Tropicalization\nby Anni
e Raymond (University of Massachusetts) as part of Extremal and probabilis
tic combinatorics webinar\n\n\nAbstract\nEstablishing inequalities among g
raph densities is a central pursuit in extremal graph theory. One way to c
ertify the nonnegativity of a graph density expression is to write it as a
sum of squares or as a rational sum of squares. In this talk\, we will ex
plore how one does so and we will then identify simple conditions under wh
ich a graph density expression cannot be a sum of squares or a rational su
m of squares. Tropicalization will play a key role for the latter\, and wi
ll turn out to be an interesting object in itself. This is joint work with
Greg Blekherman\, Mohit Singh\, and Rekha Thomas.\n
LOCATION:https://researchseminars.org/talk/EPC/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Istvan Tomon (ETH Zurich)
DTSTART:20210503T140000Z
DTEND:20210503T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/57
DESCRIPTION:Title: Ram
sey properties of string graphs\nby Istvan Tomon (ETH Zurich) as part
of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nIn this
talk\, I will give an outline of the proof of the following conjecture of
Alon\, Pach\, Pinchasi\, Radoicic and Sharir. There exists an absolute co
nstant $c>0$ such that any collection of $n$ curves (or in general arcwise
-connected sets) in the plane contains a subset of size $n^c$ in which any
two elements intersect\, or any two are disjoint. This generalizes many e
arlier results about the Ramsey properties of intersection graphs of geome
tric objects. The heart of our proof is a purely graph theoretic lemma\, w
hich turned out to be quite useful in other Erdos-Hajnal type results as w
ell\, see e.g. the recent proof of the Erdos-Hajnal conjecture for the cyc
le of length 5 by Chudnovsky\, Scott\, Seymour and Spirkl. For this talk\,
no knowledge of geometry is required.\n
LOCATION:https://researchseminars.org/talk/EPC/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Raphael Yuster (University of Haifa)
DTSTART:20210621T140000Z
DTEND:20210621T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/58
DESCRIPTION:Title: Ham
ilton cycles above expectation in r-graphs and quasi-random r-graphs\n
by Raphael Yuster (University of Haifa) as part of Extremal and probabilis
tic combinatorics webinar\n\n\nAbstract\nLet $H_r(n\,p)$ denote the maximu
m number of (tight) Hamilton cycles in an n-vertex r-graph with density $p
\\in (0\,1)$. The expected number of Hamilton cycles in the random r-grap
h $G_r(n\,p)$ is clearly $E(n\,p)=p^n(n-1)!/2$ and in the random r-graph $
G_r(n\,m)$ with $m=p\\binom{n}{r}$ it is\, in fact\, easily shown to be sl
ightly smaller than $E(n\,p)$.\n\nFor graphs\, $H_2(n\,p)$ it is proved to
be only larger than $E(n\,p)$ by a polynomial factor and it is an open pr
oblem whether a quasi-random graph with density p can be larger than $E(n\
,p)$ by a polynomial factor.\n\nFor hypergraphs the situation is drastical
ly different. For all $r \\ge 3$ it is proved that $H_r(n\,p)$ is larger
than $E(n\,p)$ by an exponential factor and\, moreover\, there are quasi-r
andom r-graphs with density p whose number of Hamilton cycles is larger th
an $E(n\,p)$ by an exponential factor.\n
LOCATION:https://researchseminars.org/talk/EPC/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrzej Grzesik (Jagiellonian University)
DTSTART:20210510T140000Z
DTEND:20210510T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/59
DESCRIPTION:Title: Gen
eralized Turán problem for cycles\nby Andrzej Grzesik (Jagiellonian U
niversity) as part of Extremal and probabilistic combinatorics webinar\n\n
Abstract: TBA\n
LOCATION:https://researchseminars.org/talk/EPC/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xizhi Liu (University of Illinois at Chicago)
DTSTART:20210517T140000Z
DTEND:20210517T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/70
DESCRIPTION:Title: A u
nified approach to hypergraph stability\nby Xizhi Liu (University of I
llinois at Chicago) as part of Extremal and probabilistic combinatorics we
binar\n\n\nAbstract\nWe present a method which provides a unified framewor
k for many stability theorems that have been proved in graph and hypergrap
h theory. Our main result reduces stability for a large class of hypergrap
h problems to the simpler question of checking that a hypergraph $\\math
cal H$ with large minimum degree that omits the forbidden structures is v
ertex-extendable. This means that if $v$ is a vertex of $\\mathcal H$ and
${\\mathcal H} -v$ is a subgraph of the extremal configuration(s)\, then $
\\mathcal H$ is also a subgraph of the extremal configuration(s). In many
cases vertex-extendability is quite easy to verify.\n\nOur method always y
ields an Andrásfai-Erdős-Sós type result\, which says if $\\mathcal H$
has large minimum degree\, then it must be a subgraph of one of the extrem
al configurations.\n\nThis is joint work with Dhruv Mubayi and Christian R
eiher.\n
LOCATION:https://researchseminars.org/talk/EPC/70/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aditya Potukuchi (University of Illinois at Chicago)
DTSTART:20210524T140000Z
DTEND:20210524T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/71
DESCRIPTION:Title: Enu
merating independent sets in Abelian Cayley graphs\nby Aditya Potukuch
i (University of Illinois at Chicago) as part of Extremal and probabilisti
c combinatorics webinar\n\n\nAbstract\nWe show that any Cayley graph on an
Abelian group of order 2n and degree $\\tilde{\\Omega}(\\log n)$ has at m
ost $2^{n+1}(1 + o(1))$ independent sets. This bound is tight up to the $o
(1)$ term whenever the graph is bipartite. The proof is based on the conta
iner method and the Pl\\"{u}nnecke-Rusza-Petridis inequality from additive
combinatorics.\n\nJoint work with Liana Yepremyan.\n
LOCATION:https://researchseminars.org/talk/EPC/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jozsef Solymosi (University of British Columbia)
DTSTART:20210531T140000Z
DTEND:20210531T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/72
DESCRIPTION:Title: On
Erdős' Unit Distances Problem\nby Jozsef Solymosi (University of Brit
ish Columbia) as part of Extremal and probabilistic combinatorics webinar\
n\n\nAbstract\nIn 1946\, Paul Erdős published a paper in the American Mat
hematical Monthly "On sets of distances of n points". He proposed two prob
lems in discrete geometry. What is the minimum number of distinct distance
s among n points in the plane\, and among n points in the plane how many p
airs of points could be at unit distance from each other? The first questi
on was answered almost completely by Larry Guth and Netz Katz in 2010\, bu
t the second\, on unit distances\, resisted all attacks so far. I will tal
k about the unit distances problems\, and related questions.\n
LOCATION:https://researchseminars.org/talk/EPC/72/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicolás Sanhueza-Matamala (Czech Academy of Sciences)
DTSTART:20210614T140000Z
DTEND:20210614T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/73
DESCRIPTION:Title: Deg
ree conditions for spanning structures in dense graphs\nby Nicolás Sa
nhueza-Matamala (Czech Academy of Sciences) as part of Extremal and probab
ilistic combinatorics webinar\n\n\nAbstract\nA classic theorem of Dirac (1
952) states that a graph in which every vertex is connected to at least ha
lf of the other vertices contains a Hamilton cycle. Over the years\, this
result has been generalised in several ways. Some generalisations weaken t
he assumptions (by not requiring every vertex to have large minimum degree
)\, and other generalisations strengthen the outcome (by considering spann
ing structures which are not cycles). We investigate the combination of th
ese two directions\, and find cycles and other spanning structures under v
arious degree conditions. Along the way\, we recover known results and obt
ain many new ones. Joint work with Richard Lang.\n
LOCATION:https://researchseminars.org/talk/EPC/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Correia (ETH Zurich)
DTSTART:20210628T140000Z
DTEND:20210628T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/74
DESCRIPTION:Title: Tig
ht bounds for powers of Hamilton cycles in tournaments\nby David Corre
ia (ETH Zurich) as part of Extremal and probabilistic combinatorics webina
r\n\n\nAbstract\nA basic result in graph theory says that any n-vertex tou
rnament with in- and out-degrees at least n/4 contains a Hamilton cycle\,
and this is essentially tight. In 1990\, Bollobás and Häggkvist signific
antly extended this by showing that for any fixed k and ε >0\, and suffic
iently large n\, all tournaments with degrees at least n/4+εn contain the
k-th power of a Hamilton cycle. Given this\, it is natural to ask for a m
ore accurate error term in the degree condition. We show that if the degre
es are at least $n/4+cn^{1−1/⌈k/2⌉}$ for some constant c=c(k)\, then
the tournament contains the k-th power of a Hamilton cycle. In particular
\, in order to guarantee the square of a Hamilton cycle\, one only require
s a constant additive term. We also present a construction which\, modulo
a well-known conjecture on Turán numbers for complete bipartite graphs\,
shows that the error term must be of order at least $n^{1−1/⌈(k−1)/2
⌉}$\, which matches our upper bound for all even k. For odd k\, we belie
ve that the lower bound can be improved and we show that for k=3\, there e
xist tournaments with degrees $n/4+Ω(n^{1/5})$ and no cube of a Hamilton
cycle. Additionally we also show that the Bollobás-Häggkvist theorem alr
eady holds for $n=ε^{−Θ(k)}$\, which is best possible. This is joint w
ork with Nemanja Draganic and Benny Sudakov.\n
LOCATION:https://researchseminars.org/talk/EPC/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natasha Morrison (University of Victoria)
DTSTART:20211101T140000Z
DTEND:20211101T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/75
DESCRIPTION:Title: Unc
ommon systems of equations\nby Natasha Morrison (University of Victori
a) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstra
ct\nA system of linear equations $L$ over $\\mathbb{F}_q$ is common if the
number of monochromatic solutions to $L$ in any two-colouring of $\\mathb
b{F}_q^n$ is asymptotically at least the expected number of monochromatic
solutions in a random two-colouring of $\\mathbb{F}_q^n$. Motivated by exi
sting results for specific systems (such as Schur triples and arithmetic p
rogressions)\, as well as extensive research on common and Sidorenko graph
s\, the systematic study of common systems of linear equations was recentl
y initiated by Saad and Wolf. Building on earlier work of Cameron\, Ciller
uelo and Serra\, as well as Saad and Wolf\, common linear equations have b
een fully characterised by Fox\, Pham and Zhao.\n\nIn this talk I will dis
cuss some recent progress towards a characterisation of common systems of
two or more equations. In particular we prove that any system containing a
n arithmetic progression of length four is uncommon\, confirming a conject
ure of Saad and Wolf. This follows from a more general result which allows
us to deduce the uncommonness of a general system from certain properties
of one- or two-equation subsystems.\n
LOCATION:https://researchseminars.org/talk/EPC/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ander Lamaison (Masaryk University)
DTSTART:20211108T140000Z
DTEND:20211108T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/76
DESCRIPTION:Title: Hyp
ergraphs with minimum positive uniform Turán density\nby Ander Lamais
on (Masaryk University) as part of Extremal and probabilistic combinatoric
s webinar\n\n\nAbstract\nReiher\, Rödl and Schacht showed that the unifor
m Turán density of every 3-uniform hypergraph is either 0 or at least 1/2
7\, and asked whether there exist 3-uniform hypergraphs with uniform Turá
n density equal or arbitrarily close to 1/27. We construct 3-uniform hyper
graphs with uniform Turán density equal to 1/27. This is based on joint w
ork with Frederik Garbe and Daniel Kráľ.\n
LOCATION:https://researchseminars.org/talk/EPC/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rajko Nenadov (Google)
DTSTART:20211115T140000Z
DTEND:20211115T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/77
DESCRIPTION:Title: A n
ew proof of the KŁR conjecture\nby Rajko Nenadov (Google) as part of
Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nWe give a
new\, short and intuitive proof of the celebrated KŁR conjecture. Slight
ly rephrased\, the conjecture states that if we condition on uniform edge
distribution\, the archetypal property of random graphs\, the probability
that the Erdős–Rényi random graph G(n\,m) does not contain a copy of a
fixed graph H becomes superexponentially small in m\, for sufficiently la
rge m > m(n\, H). As its most prominent application\, this conjecture impl
ies that with high probability all subgraphs of the binomial random graph
with appropriate parameters satisfy an embedding lemma which complements t
he sparse regularity lemma. The proof proceeds by induction and\, in some
way\, can be considered a `deterministic' analogue of the multiple-exposur
e technique from random graph theory.\n
LOCATION:https://researchseminars.org/talk/EPC/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julia Böttcher (LSE)
DTSTART:20211122T140000Z
DTEND:20211122T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/78
DESCRIPTION:by Julia Böttcher (LSE) as part of Extremal and probabilistic
combinatorics webinar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/EPC/78/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bernard Lidický (Iowa State University)
DTSTART:20211129T140000Z
DTEND:20211129T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/79
DESCRIPTION:Title: Max
imum number of almost similar triangles in the plane\nby Bernard Lidic
ký (Iowa State University) as part of Extremal and probabilistic combinat
orics webinar\n\n\nAbstract\nA triangle $T'$ is $\\varepsilon$-similar to
another triangle $T$ if their angles pairwise differ by at most $\\varepsi
lon$. Given a triangle $T$\, $\\varepsilon >0$ and $n \\in \\mathbb{N}$\,
Bárány and Füredi asked to determine the maximum number of triangles $h
(n\,T\,\\varepsilon)$ being $\\varepsilon$-similar to $T$ in a planar poin
t set of size $n$. We show that for almost all triangles $T$ there exists
$\\varepsilon=\\varepsilon(T)>0$ such that $h(n\,T\,\\varepsilon)=(1+o(1))
n^3/24$. Exploring connections to hypergraph Turán problems\, we use flag
algebras and stability techniques for the proof. This is joint work with
József Balogh and Felix Christian Clemen.\n
LOCATION:https://researchseminars.org/talk/EPC/79/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Kráľ (Masaryk University)
DTSTART:20211220T140000Z
DTEND:20211220T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/80
DESCRIPTION:Title: Qua
sirandom graphs\, permutations and Latin squares\nby Dan Kráľ (Masar
yk University) as part of Extremal and probabilistic combinatorics webinar
\n\n\nAbstract\nA combinatorial structure is said to be quasirandom if it
resembles a random structure in a certain robust sense. The notion of quas
irandom graphs\, developed in the work of Rödl\, Thomason\, Chung\, Graha
m and Wilson in 1980s\, is particularly robust as several different proper
ties of truly random graphs\, e.g.\, subgraph density\, edge distribution
and spectral properties\, are satisfied by a large graph if and only if on
e of them is. A closely related notion is the notion of common graphs\, wh
ich are graphs whose number of monochromatic copies is minimized by the (q
uasi)random coloring of a host complete graph.\n\n
\nWe will disc
uss quasirandom properties of permutations and Latin squares\, and present
several recent results obtained using analytic tools of the theory of com
binatorial limits. We will also present some recent results on common and
locally common graphs\, in particular\, we show that there exists common c
onnected graphs with arbitrary large chromatic number\, whose existence wa
s an open problem for more than 20 years.\n\n\nThe talk is based on result
s obtained with different groups of collaborators\, including Timothy F. N
. Chan\, Jacob W. Cooper\, Robert Hancock\, Matjaž Krnc\, Ander Lamaison\
, Samuel Mohr\, Jonathan A. Noel\, Sergey Norin\, Yanitsa Pehova\, Oleg Pi
khurko\, Maryam Sharifzadeh\, Jan Volec and Fan
\nWei.\n
LOCATION:https://researchseminars.org/talk/EPC/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benedikt Stufler (TU Wien)
DTSTART:20211206T140000Z
DTEND:20211206T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/81
DESCRIPTION:Title: Loc
al convergence of random planar graphs\nby Benedikt Stufler (TU Wien)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
nThe study of random combinatorial structures and their limits is a growin
g field at the interface of combinatorics\, probability theory\, and mathe
matical physics. Planar graphs are a prominent example of such structures\
, yet important problems concerning their asymptotic shape remain open. Th
is talk highlights open conjectures and reviews recent results\, in partic
ular the discovery of a Uniform Infinite Planar Graph (UIPG) as their quen
ched local limit.\n
LOCATION:https://researchseminars.org/talk/EPC/81/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Candida Bowtell (University of Oxford)
DTSTART:20211213T140000Z
DTEND:20211213T150000Z
DTSTAMP:20260422T225703Z
UID:EPC/82
DESCRIPTION:Title: The
n-queens problem\nby Candida Bowtell (University of Oxford) as part o
f Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nHow many
ways are there to place n queens on an n by n chessboard so that no two c
an attack one another? What if the chessboard is embedded on the torus? Le
t Q(n) be the number of ways on the standard chessboard and T(n) the numbe
r on the toroidal board. The toroidal problem was first studied in 1918 by
Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3
. Much more recently Luria showed that T(n) is at most $\\left((1+o(1))ne^
{-3}\\right)^n$ and conjectured equality when n is not divisible by 2 or 3
. We prove this conjecture\, prior to which no non-trivial lower bounds we
re known to hold for all (sufficiently large) n not divisible by 2 or 3. W
e also show that Q(n) is at least $\\left((1+o(1))ne^{-3}\\right)^n$ for a
ll natural numbers n which was independently proved by Luria and Simkin an
d\, combined with our toroidal result\, completely settles a conjecture of
Rivin\, Vardi and Zimmerman regarding both Q(n) and T(n).\n\nIn this talk
we'll discuss our methods used to prove these results. A crucial element
of this is translating the problem to one of counting matchings in a 4-par
tite 4-uniform hypergraph. Our strategy combines a random greedy algorithm
to count `almost' configurations with a complex absorbing strategy that u
ses ideas from the methods of randomised algebraic construction and iterat
ive absorption.\n\nThis is joint work with Peter Keevash.\n
LOCATION:https://researchseminars.org/talk/EPC/82/
END:VEVENT
END:VCALENDAR