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:20260404T110827Z
UID:EPC/1
DESCRIPTION:Title: Overlap gap property: a provable barrier to fast optimization in probab
ilistic combinatorial structures\nby David Gamarnik (MIT) as part of E
xtremal and probabilistic combinatorics webinar\n\n\nAbstract\nMany combin
atorial optimization problems defined on random instances\, such as random
graphs\, exhibit an apparent gap between the optimal values\, which can b
e computed by non-constructive means\, and the best values achievable by f
ast (polynomial time) algorithms. Through a combined effort of mathematici
ans\, computer scientists and statistical physicists\, it became apparent
that a potential\, and in some cases\, a provable barrier for designing fa
st algorithms bridging this gap is an intricate topology of nearly optimal
solutions\, in particular the presence of a certain Overlap Gap Property
(OGP)\, which we will introduce in this talk. We will demonstrate how for
many such problems the onset of the OGP phase transition indeed nearly coi
ncides with algorithmically hard regimes and provides a provable barrier t
o a broad class of polynomial time algorithms. Our examples will include t
he problem of finding a largest independent set of a random graph\, findin
g a largest cut in a random hypergraph\, the problem of finding a ground s
tate of a p-spin model\, and also many models in high-dimensional statisti
cs and machine learning fields. The classes of algorithms ruled out by the
OGP include local algorithms\, Markov Chain Monte Carlo\, Approximate Mes
sage Passing and low-degree polynomial based algorithms.\n\nJoint work wit
h Madhu Sudan\, Wei-Cuo Chen\, Dmitry Panchenko\, Mustazee Rahman\, Aukosh
Jagannath and Alex Wein.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ehud Friedgut (Weizmann Institute of Science)
DTSTART:20200420T130000Z
DTEND:20200420T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/2
DESCRIPTION:Title: Five and a half proofs of one theorem\nby Ehud Friedgut (Weizmann I
nstitute of Science) as part of Extremal and probabilistic combinatorics w
ebinar\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 th
e variants of this theorem\, in the setting of the product measure on the
discrete cube\, and present (time permitting) several different proofs of
it\, using a surprisingly eclectic set of tools.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matija Bucić (ETH Zurich)
DTSTART:20200504T130000Z
DTEND:20200504T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/3
DESCRIPTION:Title: Tournament quasirandomness from local counting\nby Matija Bucić (E
TH Zurich) as part of Extremal and probabilistic combinatorics webinar\n\n
\nAbstract\nA well-known theorem of Chung and Graham states that if h>3 th
en a tournament T is quasirandom if and only if T contains each h-vertex t
ournament the "correct number" of times as a subtournament. In this talk w
e investigate the relationship between quasirandomness of T and the count
of a single h-vertex tournament H in T. We consider two types of counts\,
the global one and the local one.\n\nWe first observe that if T has the co
rrect global count of H and h>6 then quasirandomness of T is only forced i
f H is transitive. The next natural question when studying quasirandom obj
ects asks whether possessing the correct local counts of H is enough to fo
rce quasirandomness 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 s
tudied before in both the graph and hypergraph settings. Perhaps the close
st analogue of our problem was considered by Simonovits and Sós who looke
d at whether having "correct counts" of a fixed graph H as an induced subg
raph of G implies G must be quasirandom\, in an appropriate sense. They pr
oved that this is indeed the case when H is regular and conjectured that i
t holds for all H (except the path on 3 vertices).\n\nContrary to the Simo
novits-Sós conjecture\, in the tournament setting we prove that a constan
t proportion of all tournaments are not locally forcing. In fact\, any loc
ally forcing tournament must itself be strongly quasirandom. On the other
hand\, unlike the global forcing case\, we construct infinite families of
non-transitive locally forcing tournaments.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jinyoung Park (Rutgers University)
DTSTART:20200511T130000Z
DTEND:20200511T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/4
DESCRIPTION:Title: The number of maximal independent sets in the Hamming cube\nby Jiny
oung Park (Rutgers University) as part of Extremal and probabilistic combi
natorics webinar\n\n\nAbstract\nLet $Q_n$ be the $n$-dimensional Hamming c
ube (hypercube) and $N = 2^n$. We prove that the number of maximal indepen
dent sets in $Q_n$ is asymptotically $2n2^{N/4}$\, as was conjectured by I
linca and Kahn in connection with a question of Duffus\, Frankl and Rödl.
The value is a natural lower bound derived from a connection between maxi
mal independent sets and induced matchings. The proof of the upper bound d
raws on various tools\, among them “stability” results for maximal ind
ependent set counts and old and new results on isoperimetric behavior in $
Q_n$. This is joint with Jeff Kahn.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Institute of Technology)
DTSTART:20200518T130000Z
DTEND:20200518T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/5
DESCRIPTION:Title: Counting extensions in random graphs\nby Lutz Warnke (Georgia Insti
tute of Technology) as part of Extremal and probabilistic combinatorics we
binar\n\n\nAbstract\nWe consider rooted subgraphs in random graphs\, i.e.\
, extension 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 event that\, whip\, all roots of the binomial random graph G(n\,p) hav
e the same asymptotic number of extensions\, i.e.\, (1 \\pm \\epsilon) tim
es their expected number. \n\nFor the important strictly balanced case\, S
pencer also raised the fundamental question whether these conditions are n
ecessary. \n\nWe answer this question by a careful second moment argument\
, and discuss some intriguing problems that remain open.\n\nJoint work wit
h Matas Sileikis\, see arXiv:1911.03012\n\nPassword: the first 6 prime num
bers (8 digits in total)\n
LOCATION:https://stable.researchseminars.org/talk/EPC/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexey Pokrovskiy (Birkbeck College)
DTSTART:20200427T130000Z
DTEND:20200427T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/6
DESCRIPTION:Title: Proof of Ringel's conjecture\nby Alexey Pokrovskiy (Birkbeck Colleg
e) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstra
ct\nRingel conjectured that the edges of the complete graph on 2n+1 vertic
es 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://stable.researchseminars.org/talk/EPC/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gábor Tardos (Alfréd Rényi Institute)
DTSTART:20200525T130000Z
DTEND:20200525T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/7
DESCRIPTION:Title: Planar point sets determine many pairwise crossing segments\nby Gá
bor Tardos (Alfréd Rényi Institute) as part of Extremal and probabilisti
c combinatorics webinar\n\n\nAbstract\nWhat is the largest number $f(n)$ s
uch that $n$ points in the plane (no three on a line) always determine $f(
n)$ pairwise crossing segments. This natural question was asked by Aronov\
, Erdős\, Goddard\, Kleitman\, Klugerman\, Pach\, and Schulman in 1991 a
nd they proved $f(n)=\\Omega(\\sqrt{n})$. The prevailing conjecture was th
at this bound is far from optimal and $f(n)$ is probably linear in $n$. Ne
vertheless\, this lower bound was not improved till last year\, when we p
roved with János Pach and Natan Rubin an almost (but not quite) linear lo
wer bound. Our result gives $f(n)>n/\\exp(O(\\sqrt{\\log n}))$. Determinin
g whether $f(n)$ is truly linear is an intriguing open problem.\n\nPasswor
d: the first 6 prime numbers (8 digits in total)\n
LOCATION:https://stable.researchseminars.org/talk/EPC/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joonkyung Lee (Universität Hamburg)
DTSTART:20200601T130000Z
DTEND:20200601T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/8
DESCRIPTION:Title: On tripartite common graphs\nby Joonkyung Lee (Universität Hamburg
) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstrac
t\nA graph $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 c
olouring. Burr and Rosta\, extending a famous conjecture by Erdős\, conje
ctured that every graph is common\, which was disproved by Thomason and by
Sidorenko in late 1980s. Collecting new examples for common graphs had no
t seen much progress since then\, although very recently\, a few more grap
hs are verified to be common by the flag algebra method or the recent prog
ress on Sidorenko's conjecture.\n\nOur contribution here is to give a new
class of tripartite common graphs. The first example class is so-called tr
iangle trees\, which generalises two theorems by Sidorenko and hence answe
rs a question by Jagger\, Šťovíček\, and Thomason from 1996. We also
prove that\, somewhat surprisingly\, given any tree T\, there exists a tri
angle tree 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 th
at every complete tripartite graph is common.\n\nJoint work with Andrzej G
rzesik\, Bernard Lidický\, and Jan Volec.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Jenssen (University of Birmingham)
DTSTART:20200608T130000Z
DTEND:20200608T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/9
DESCRIPTION:Title: A proof of the Upper Matching Conjecture for large graphs\nby Matth
ew Jenssen (University of Birmingham) as part of Extremal and probabilisti
c combinatorics webinar\n\n\nAbstract\nWe show that the `Upper Matching Co
njecture' of Friedland\, Krop\, and Markström and the analogous conjectur
e of Kahn 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 lar
ge enough $n$ divisible by $2d$\, a union of $n \\over 2d$ copies of the c
omplete $d$-regular bipartite graph maximises the number of independent se
ts and matchings of any given size over all $d$-regular graphs on $n$ vert
ices. For the proof\, we'll discuss two different approaches to these prob
lems\, both inspired by statistical physics. This is joint work with Ewan
Davies and Will Perkins.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Asaf Ferber (UC Irvine)
DTSTART:20200615T130000Z
DTEND:20200615T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/10
DESCRIPTION:Title: Induced subgraphs with prescribed degrees mod q\nby Asaf Ferber (U
C Irvine) as part of Extremal and probabilistic combinatorics webinar\n\n\
nAbstract\nA classical result of Galai asserts that the vertex-set of ever
y graph can be partitioned into two sets such that each induces a graph wi
th all degrees even. Scott studied the (harder) problem of
\ndetermining for which graphs can we find a partition into arbitrary ma
ny parts\, each of which induces a graph with all odd degrees.\n\nIn this
talk we discuss various extensions of this problem to arbitrary residues m
od $q\\geq 3$. Among other results\, we show that for every $q$\, a typica
l 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 s
equence.\n
\nSwitc
hing to a completely unrelated problem: based on idea of the main key lemm
a of the above results\, we give non-trivial bound (but weaker than known
results) on the singularity probability of a random symmetric Bernoulli ma
trix. The new argument avoids both decoupling and distance from random hyp
erplanes and it turns this problem into a simple and elegant exercise.\n
\nThe first part of
the talk is based on a joint work with Liam Hardiman (UCI) and Michael Kr
ivelevich (Tel Aviv University).\n
LOCATION:https://stable.researchseminars.org/talk/EPC/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annika Heckel (LMU Munich)
DTSTART:20200622T130000Z
DTEND:20200622T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/11
DESCRIPTION:Title: Non-concentration of the chromatic number\nby Annika Heckel (LMU M
unich) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nThere are many impressive results asserting that the chromatic num
ber of a random graph is sharply concentrated. In 1987\, Shamir and Spence
r showed that for any function p=p(n)\, the chromatic number of G(n\,p) ta
kes one of at most about $n^{1/2}$ consecutive values whp. For sparse rand
om graphs\, much sharper concentration is known to hold: Alon and Krivelev
ich proved two point concentration whenever $p < n^{-1/2-\\varepsilon}$.\n
\nHowever\, until recently no non-trivial lower bounds for the concentrati
on 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 chromatic number of G(n\, 1/2) is not whp contained in any sequence o
f intervals of length $n^{1/2-o(1)}$\, almost matching Shamir and Spencer'
s upper bound.\n\nJoint work with Oliver Riordan.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anton Bernshteyn (Carnegie Mellon University)
DTSTART:20200629T130000Z
DTEND:20200629T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/12
DESCRIPTION:Title: A fast distributed algorithm for $(\\Delta + 1)$-edge-coloring\nby
Anton Bernshteyn (Carnegie Mellon University) as part of Extremal and pro
babilistic combinatorics webinar\n\n\nAbstract\nA celebrated theorem of Vi
zing says that every graph $G$ of maximum degree $\\Delta$ is $(\\Delta+1)
$-edge-colorable. In this talk I will describe a deterministic distributed
algorithm in the LOCAL model that finds a $(\\Delta+1)$-edge-coloring in
the number of rounds that is polynomial in $\\Delta$ and $\\log n$\, where
$n = |V(G)|$. This is the first distributed algorithm for $(\\Delta + 1)$
-edge-coloring with running time better than $O(\\mathrm{diameter}(G))$.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Józef Balogh (University of Illinois)
DTSTART:20200706T130000Z
DTEND:20200706T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/13
DESCRIPTION:Title: Extensions of Mantel's Theorem\nby Józef Balogh (University of Il
linois) as part of Extremal and probabilistic combinatorics webinar\n\n\nA
bstract\nMantel's theorem is a basic classical theorem of extremal graph t
heory. There are many different extensions and generalizations investiga
ted and many open questions remained.
\nI will talk about three recent results\, including "s
tability" and "supersaturation" properties.
\nThe results are partly joined with Cleme
n\, Katona\, Lidicky\, Linz\, Pfender and Tuza.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Matthew Kwan (Stanford University)
DTSTART:20200713T130000Z
DTEND:20200713T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/14
DESCRIPTION:Title: Extension complexity of low-dimensional polytopes\nby Matthew Kwan
(Stanford University) as part of Extremal and probabilistic combinatorics
webinar\n\n\nAbstract\nSometimes\, it is possible to represent a complica
ted polytope as a projection of a much simpler polytope. To quantify this
phenomenon\, the extension complexity of a polytope P is defined to be the
minimum number of facets in a (possibly higher-dimensional) polytope from
which P can be obtained as a linear projection. In this talk we discuss s
ome extremal and probabilistic questions about this notion. This is a join
t work with Lisa Sauermann and Yufei Zhao.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Shoham Letzter (University College London)
DTSTART:20200720T130000Z
DTEND:20200720T140000Z
DTSTAMP:20260404T110827Z
UID:EPC/15
DESCRIPTION:Title: Monochromatic triangle packings in 2-coloured complete graphs\nby
Shoham Letzter (University College London) as part of Extremal and probabi
listic combinatorics webinar\n\n\nAbstract\nAbstract: We show that every 2
-coloured complete graph on n vertices contains $n^2/12 + o(n^2)$ pairwise
edge-disjoint monochromatic triangles. This confirms a conjecture of Erd
ős\, and is asymptotically tight. This is joint work with Vytautas Grusly
s.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oleg Pikhurko (University of Warwick)
DTSTART:20200727T140000Z
DTEND:20200727T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/16
DESCRIPTION:Title: Combinatorics of circle squaring\nby Oleg Pikhurko (University of
Warwick) as part of Extremal and probabilistic combinatorics webinar\n\n\n
Abstract\nTwo sets in a metric space are called equidecomposable if one se
t can be partitioned into finitely many pieces that can be rearranged by i
sometries to form a partition of the other set. I will discuss how combina
torial ideas and methods helped in various results on "constructive" equid
ecompositions. In particular\, I will present our joint result with Andras
Mathe and Jonathan Noel that a disk and a
\nsquare in th
e Euclidean plane are equidecomposable with Jordan measurable pieces.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Felix Joos (Heidelberg University)
DTSTART:20200810T140000Z
DTEND:20200810T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/18
DESCRIPTION:Title: Decompositions of Hypergraphs\nby Felix Joos (Heidelberg Universit
y) as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstra
ct\nSeveral results on approximate decompositions of hypergraphs are prese
nted including decompositions into tight Hamilton cycles under very mild a
ssumptions on the host hypergraphs as well as further results on decomposi
tions of quasirandom hypergraphs into bounded degree hypergraphs.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mehtaab Sawhney (MIT)
DTSTART:20200817T140000Z
DTEND:20200817T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/19
DESCRIPTION:Title: Local limit theorems for subgraph counts\nby Mehtaab Sawhney (MIT)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract
\nWe introduce a general framework for studying anticoncentration and loca
l limit theorems for random variables\, including graph statistics. Our me
thods involve an interplay between Fourier analysis\, decoupling\, hyperco
ntractivity of Boolean functions\, and transference between "fixed-size" a
nd "independent" models. We also adapt a notion of "graph factors" due to
Janson.\n\nAs a consequence\, we derive a local central limit theorem for
connected subgraph counts in the Erdős-Rényi random graph G(n\,p)\, buil
ding on work of Gilmer and Kopparty and of Berkowitz. These results improv
e an anticoncentration result of Fox\, Kwan\, and Sauermann and partially
answers a question of Fox\, Kwan\, and Sauermann. We also derive a local l
imit central limit theorem for induced subgraph counts\, as long as p is b
ounded away from a set of "problematic" densities\, partially answering a
question of Fox\, Kwan\, and Sauermann. We then prove these restrictions a
re necessary by exhibiting a disconnected graph for which anticoncentratio
n for subgraph counts at the optimal scale fails for all constant p\, and
finding a graph H for which anticoncentration for induced subgraph counts
fails in G(n\,1/2). These counterexamples resolve anticoncentration conjec
tures of Fox\, Kwan\, and Sauermann in the negative.\n\nFinally\, we also
examine the behavior of counts of k-term arithmetic progressions in subset
s of Z/nZ and deduce a local limit theorem wherein the behavior is Gaussia
n at a global scale but has nontrivial local oscillations (according to a
Ramanujan theta function). These results improve on results of and answer
questions of the authors and Berkowitz\, and answer a question of Fox\, Kw
an\, and Sauermann.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Boris Bukh (Carnegie Mellon University)
DTSTART:20200803T140000Z
DTEND:20200803T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/20
DESCRIPTION:Title: Convex holes in high-dimensional point sets\nby Boris Bukh (Carneg
ie Mellon University) as part of Extremal and probabilistic combinatorics
webinar\n\n\nAbstract\nIt is well-known that every large enough set P in a
n Euclidean space contains k points in convex position. Such k points are
called "hole" if their convex hull contains no other point of P. We presen
t a new construction of k-hole-free sets in high-dimensional spaces. Surpr
isingly\, the construction is based on non-trivial low-discrepancy sequenc
es used for numerical integration.
\nJoint work with Ting-Wei Chao an
d Ron Holzman.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tao Jiang (Miami University)
DTSTART:20200831T140000Z
DTEND:20200831T150000Z
DTSTAMP:20260404T110827Z
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\nGi
ven a family of graphs ${\\mathcal F}$\, the Turán number $ex(n\,{\\mathc
al 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 subgra
ph. In a relatively recent breakthrough\, Bukh and Conlon verified a long-
standing conjecture in extremal graph theory that was credited to Erdős a
nd Simonovits and re-iterated by other authors by showing that for every r
ational number $r$ between $1$ and $2$ there exists a family ${\\mathcal F
}$ of graphs such that $ex(n\,{\\mathcal F})=\\Theta(n^r)$.
\n\nThere is a
stronger conjecture that states that for every rational $r$ between $1$ an
d $2$ there exists a single bipartite graph $F$ such that $ex(n\,F)=\\Thet
a(n^r)$. This conjecture is still open. In this talk\, we survey recent pr
ogress on this stronger conjecture.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guillem Perarnau (Universitat Politècnica de Catalunya)
DTSTART:20200907T140000Z
DTEND:20200907T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/22
DESCRIPTION:Title: Extremal stationary values for directed random graphs\nby Guillem
Perarnau (Universitat Politècnica de Catalunya) as part of Extremal and p
robabilistic combinatorics webinar\n\n\nAbstract\n: In this talk\, we will
discuss the minimum positive value of the stationary distribution of a ra
ndom walk on a directed random graph with given (bounded) degrees. While f
or undirected graphs the stationary distribution is simply determined by t
he degrees\, the graph geometry plays a major role in the directed case. U
nderstanding typical stationary values is key to determining the mixing ti
me of the walk\, as shown by Bordenave\, Caputo\, and Salez. However\, typ
ical results provide no information on the minimum value\, which is import
ant for many applications. Recently\, Caputo and Quattropani showed that t
he stationary distribution exhibits logarithmic fluctuations provided that
the minimum degree is at least 2. In this talk\, we show that dropping th
e minimum degree condition may yield polynomially smaller stationary value
s of the form $n^{-(1+C+o(1))}$\, for a constant C determined by the degre
e distribution. In particular\, C is the combination of two factors: (1) t
he contribution of atypically thin in-neighborhoods\, controlled by subcri
tical branching processes\; and (2) the contribution of atypically "light"
directed paths\, controlled by large deviation rate functions. As a by-pr
oduct of our proof\, we also determine the mean hitting time in random dig
raphs. This is joint work with Xing Shi Cai.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Postle (University of Waterloo)
DTSTART:20200914T140000Z
DTEND:20200914T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/23
DESCRIPTION:Title: Further progress towards Hadwiger's conjecture\nby Luke Postle (Un
iversity of Waterloo) as part of Extremal and probabilistic combinatorics
webinar\n\n\nAbstract\nIn 1943\, Hadwiger conjectured that every graph wit
h no $K_t$ minor is $(t-1)$-colorable for every $t\\ge 1$. In the 1980s\,
Kostochka 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 no $K_t$ minor is $O(t(\\log t)^{\\beta})$-colorable for every $\\be
ta > 1/4$\, making the first improvement on the order of magnitude of the
$O(t\\sqrt{\\log t})$ bound. Here we show that every graph with no $K_t$ m
inor is $O(t (\\log t)^{\\beta})$-colorable for every $\\beta > 0$\; more
specifically\, they are $O(t (\\log \\log t)^{6})$-colorable.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peter Allen (LSE)
DTSTART:20200921T140000Z
DTEND:20200921T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/24
DESCRIPTION:Title: Weak expansion and strong regularity\nby Peter Allen (LSE) as part
of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nIn pre
vious work\, embedding large graphs into subgraphs of random graphs is gen
erally done vertex by vertex\, using the Sparse Regularity Lemma\, looking
only one step ahead\, and maintaining regularity properties throughout us
ing a technical tool called inheritance of regularity. This approach canno
t work for very sparse random graphs\, even though it is believed that the
embedding statements do remain true. We develop an alternative approach\,
showing that given a partial embedding and looking several steps ahead\,
the set of extensions has a weak expansion property\; leveraging this one
can perform vertex by vertex embedding without the need for inheritance of
regularity\, and as a result the approach works in sparser random graphs.
In order to make this approach work\, we need to use a strengthened versi
on of the Sparse Regularity Lemma.\n\nI will outline the new approach brie
fly\, and explain how to use it to prove two new results.\n\n(i) For any
$\\gamma>0$ and integers $r$\, $D$ and $\\Delta$\, there is $c>0$ such tha
t if $p\\ge n^{-1/D+\\gamma}$ then $\\Gamma=G(n\,p)$ with high probability
has the following property. However $\\Gamma$ is $r$-coloured\, there is
a colour class which contains all $cn$-vertex graphs with degeneracy at mo
st $D$ and maximum degree at most $\\Delta$.\n\n(ii) If $p\\ge n^{-1+o(1)}
$\, then the random $k$-uniform hypergraph $\\Gamma=G^{(k)}(n\,p)$ with hi
gh probability has the following property. Every subgraph $G$ of $\\Gamma$
with minimum codegree at least $(\\frac12+o(1))pn$ contains a tight Hamil
ton cycle.\n\nBoth these results are asymptotically optimal. This is joint
work with Julia Böttcher and with Olaf Parczyk and Vincent Pfenninger.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lisa Sauermann (Stanford University)
DTSTART:20201019T140000Z
DTEND:20201019T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/25
DESCRIPTION:Title: On polynomials that vanish to high order on most of the hypercube\
nby Lisa Sauermann (Stanford University) as part of Extremal and probabili
stic combinatorics webinar\n\n\nAbstract\nMotivated by higher vanishing mu
ltiplicity generalizations of Alon's Combinatorial Nullstellensatz and its
applications\, we study the following problem: for fixed k and n large wi
th respect 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 z
eroes of multiplicity at least k at all points in ${0\,1}^n$ except the or
igin? For k=1\, a classical theorem of Alon and Füredi states that the mi
nimum possible 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 W
igderson.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Ellis (University of Bristol)
DTSTART:20201109T140000Z
DTEND:20201109T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/26
DESCRIPTION:Title: A remark on the transitive case of the union-closed conjecture\nby
David Ellis (University of Bristol) as part of Extremal and probabilistic
combinatorics 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 question is generated by all translates of a fixed subset of an Abelia
n group. Joint work with James Aaronson (Oxford) and Imre Leader (Cambridg
e).\n
LOCATION:https://stable.researchseminars.org/talk/EPC/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Moumanti Podder (NYU Shanghai)
DTSTART:20201116T140000Z
DTEND:20201116T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/27
DESCRIPTION:Title: Some combinatorial games on rooted multi-type Galton-Watson trees\
nby Moumanti Podder (NYU Shanghai) as part of Extremal and probabilistic c
ombinatorics webinar\n\n\nAbstract\nIn a rooted multi-type Galton-Watson b
ranching process\, the root is assigned a colour from a finite set $\\Sigm
a$ of colours according to some probability distribution P\, and a vertex
of the tree\, conditioned on its colour $\\sigma \\in \\Sigma$\, gives bir
th to offspring according to some probability distribution $\\chi_{\\sigma
}$ on $\\mathbb{N}_{0}^{\\Sigma}$. In particular\, one may consider $\\Sig
ma = \\{{\\rm red}\, {\\rm blue}\\}$ and the resulting random tree\, denot
ed T\, can be viewed as a directed random graph if each edge is attributed
a direction from parent to child. I consider the normal\, misere and esca
pe games on T\, each played between P1 and P2\, with P1 being allowed to m
ove the token only along monochromatic directed edges and P2 being allowed
to move the token only along non-monochromatic directed edges. I then inv
estigate the probabilities of win\, loss and (where pertinent) draw of eac
h player as fixed points of distributional recursions\, establish inequali
ties between win / loss / draw probabilities of the players across differe
nt games\, seek possible phase transitions in win / loss / draw probabilit
ies as the parameters involved in the offspring distributions are made to
vary\, study expected durations of the games etc.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hao Huang (Emory University)
DTSTART:20201026T140000Z
DTEND:20201026T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/28
DESCRIPTION:Title: On local Turán problems\nby Hao Huang (Emory University) as part
of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nSince i
ts formulation\, Turán's hypergraph problems have been among the most cha
llenging open problems in extremal combinatorics. One of them is the follo
wing: given a 3-uniform hypergraph F on n vertices in which any five verti
ces span at least one edge\, prove that $|F|\\ge(1/4 -o(1))\\binom{n}{3}$.
The construction 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 all p>2 the (2p+1\,p+1)-property implies the conjectured lower bound
. Furthermore\, we will prove that for integers r\, a >= 2\, the minimum e
dge density of an r-uniform hypergraph satisfying the (ap+1\, p+1)-propert
y 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://stable.researchseminars.org/talk/EPC/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ferenc Benc (Rényi Institute)
DTSTART:20201012T140000Z
DTEND:20201012T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/29
DESCRIPTION:Title: Atoms of the matching measure\nby Ferenc Benc (Rényi Institute) a
s part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\n
We prove that the matching measure of an infinite vertex-transitive connec
ted graph has no atoms. Generalizing the results of Salez\, we show that f
or an ergodic non-amenable unimodular random rooted graph with uniformly b
ounded degrees\, the matching measure has only finitely many atoms. Ku and
Chen proved the analogue of the Gallai-Edmonds structure theorem for non-
zero roots of the matching polynomial for finite graphs. We extend their r
esults for infinite graphs. We also show that the corresponding Gallai-Edm
onds decomposition is compatible with the zero temperature monomer-dimer m
odel. Joint work with András Mészáros.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jonathan Noel (University of Victoria)
DTSTART:20200928T140000Z
DTEND:20200928T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/30
DESCRIPTION:Title: Non-bipartite k-common graphs\nby Jonathan Noel (University of Vic
toria) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nHow many monochromatic copies of H must appear in a k-edge colouri
ng 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 colourin
g. Recent progress on Sidorenko's Conjecture has provided many new example
s of bipartite k-common graphs\; however\, it is not known if such graphs
can have high chromatic number. We construct the first examples of non-bip
artite k-common graphs for $k \\ge 3$\, addressing a problem raised by Jag
ger\, Šťovíček and Thomason in 1996. This talk is based on joint work
with Daniel Kráľ\, Sergey Norin\, Jan Volec and Fan Wei.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Richard Montgomery (University of Birmingham)
DTSTART:20201005T140000Z
DTEND:20201005T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/31
DESCRIPTION:Title: A solution to Erdős and Hajnal's odd cycle problem\nby Richard Mo
ntgomery (University of Birmingham) as part of Extremal and probabilistic
combinatorics webinar\n\n\nAbstract\nI will discuss how to construct cycle
s of many different lengths in graphs\, in particular answering the follow
ing two problems on odd and even cycles. In 1966\, Erdős and Hajnal asked
whether the sum of the reciprocals of the odd cycle lengths in a graph di
verges as the chromatic number increases. Later\, Erdős asked whether the
re is a constant C such that every graph with average degree at least C co
ntains a cycle whose length is a power of 2.\n\nThis is joint work with Ho
ng Liu.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:ZOOM-ISSUE
DTSTART:20200824T140000Z
DTEND:20200824T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/32
DESCRIPTION:Title: Jan Grebik's talk rescheduled to Nov 23\nby ZOOM-ISSUE as part of
Extremal and probabilistic combinatorics webinar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/EPC/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrey Kupavskii (Moscow Institute of Physics and Technology)
DTSTART:20201102T140000Z
DTEND:20201102T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/33
DESCRIPTION:Title: The extremal number of surfaces\nby Andrey Kupavskii (Moscow Insti
tute of Physics and Technology) as part of Extremal and probabilistic comb
inatorics 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 triang
ulation of the sphere\, then H has at most $O(n^{5/2})$ edges\, and this b
ound is the best possible up to a constant factor. Resolving a conjecture
of Linial\, also reiterated by Keevash\, Long\, Narayanan\, and Scott\, we
show that the same result holds for triangulations of the torus. Furtherm
ore\, we extend our result to every closed orientable surface S. Joint wor
k with Alexandr Polyanskii\, István Tomon and Dmitriy Zakharov\n
LOCATION:https://stable.researchseminars.org/talk/EPC/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Grebík (University of Warwick)
DTSTART:20201123T140000Z
DTEND:20201123T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/34
DESCRIPTION:Title: Large deviation principle for graphons\nby Jan Grebík (University
of Warwick) as part of Extremal and probabilistic combinatorics webinar\n
\n\nAbstract\nIn this talk we discuss the large deviation principle (LDP)
for a sequence of measures on the graphon space which is obtained by sampl
ing from a fixed graphon W.\n\nThe large deviation theory for the Erdős
–Rényi random graph (sampling from a constant graphon) and its applicat
ions were developed by Chatterjee and Varadhan.\n\nParticularly\, the Erd
ős–Rényi 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 inter
esting speeds\, 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 sampling from a step graphon.\n\nTime permitting\, we compare our wor
k with a recent result by Borgs\, Chayes\, Gaudio\, Petti and Sen on LDP f
or block models.\n\nThis is a joint work with O.Pikhurko.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Conlon (California Institute of Technology)
DTSTART:20201214T140000Z
DTEND:20201214T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/35
DESCRIPTION:Title: Exponential improvements in Ramsey theory\nby David Conlon (Califo
rnia Institute of Technology) as part of Extremal and probabilistic combin
atorics webinar\n\n\nAbstract\nThe Ramsey number r(t) is the smallest natu
ral number n such that every two-colouring of the edges of $K_n$ contains
a monochromatic copy of $K_t$. It has been known for over seventy years th
at the Ramsey number lies between $\\left(\\sqrt{2}\\right)^t$ and $4^t$\,
but improving either bound by an exponential factor remains a difficult o
pen problem. In this lecture\, we discuss several related problems where s
uch an exponential improvement has been achieved.\n\nThis talk reflects jo
int work with many co-authors\, including Asaf Ferber\, Jacob Fox\, Andrey
Grinshpun\, Xiaoyu He and Yuval Wigderson.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benny Sudakov (ETH Zürich)
DTSTART:20201130T140000Z
DTEND:20201130T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/36
DESCRIPTION:Title: Three problems on 3-chromatic intersecting hypergraphs\nby Benny S
udakov (ETH Zürich) as part of Extremal and probabilistic combinatorics w
ebinar\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 Hajn
al\, who asked for the minimum number of edges in such a k-uniform hypergr
aph. 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 intrigui
ng problems on the properties of 3-chromatic intersecting hypergraphs. Des
pite these problems being reiterated several times over the years by Erdos
and other researchers\, remarkably they withstood any progress up until n
ow. In this talk\, we prove that in any 3-chromatic intersecting k-uniform
hypergraph 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 s
trong form and substantially improves their previously best bound of at le
ast 3 different intersection sizes.\n\nJoint work with M. Bucic and S. Glo
ck\n
LOCATION:https://stable.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:20260404T110827Z
UID:EPC/37
DESCRIPTION:Title: Avoiding arithmetic progressions or right angles\nby Petér Pál P
ach (Budapest University of Technology and Economics) as part of Extremal
and probabilistic combinatorics webinar\n\n\nAbstract\nIn this talk we dis
cuss some bounds about sets avoiding certain arithmetic or geometric confi
gurations in $F_p^n$ (or more generally\, in $Z_m^n$). In particular\, we
will consider the case of 6-term arithmetic progressions in $Z_6^n$\, and
sets avoiding right angles in $F_p^n$. Our methods can also be used to bou
nd 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 Palinc
za and with Bursics\, Matolcsi and Schrettner.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nati Linial (Hebrew University of Jerusalem)
DTSTART:20201221T140000Z
DTEND:20201221T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/38
DESCRIPTION:Title: Geodesic geometry on graphs\nby Nati Linial (Hebrew University of
Jerusalem) as part of Extremal and probabilistic combinatorics webinar\n\n
\nAbstract\nWe investigate a graph theoretic analog of geodesic geometry.
In a graph G=(V\,E) we consider a system of paths $P=\\{Pu\,v | u\,v \\in
V\\}$ where $Pu\,v$ connects vertices u and v. This system is consistent i
n that if vertices y\,z are in $Pu\,v$\, then the sub-path of $Pu\,v$ betw
een them 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 s
uch w. As we show\, metrizable graphs are very rare\, whereas there exist
infinitely many 2-connected metrizable graphs.\n\n\nJoint work with my stu
dent Daniel Cizma\n
LOCATION:https://stable.researchseminars.org/talk/EPC/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Noga Alon (Princeton University)
DTSTART:20210104T140000Z
DTEND:20210104T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/39
DESCRIPTION:Title: Splitting necklaces\nby Noga Alon (Princeton University) as part o
f Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nIt is kn
own that one can cut any opened necklace with beads of $n$ types in at mos
t $(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 n
umber of cuts is optimal. I will discuss some recent advances in the study
of this problem focusing on its algorithmic aspects and on the case of ra
ndom necklaces. \n\nBased on joint work with Anrdei Graur and on joint wor
k in progress with Janos Pach and Gabor Tardos.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vishesh Jain (Stanford University)
DTSTART:20210301T140000Z
DTEND:20210301T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/40
DESCRIPTION:Title: Towards the sampling Lovász local lemma\nby Vishesh Jain (Stanfor
d University) as part of Extremal and probabilistic combinatorics webinar\
n\n\nAbstract\nFor a constraint satisfaction problem which satisfies the c
ondition of the Lovász local lemma (LLL)\, the celebrated algorithm of Mo
ser and Tardos allows one to efficiently find a satisfying assignment. In
the past few years\, much work has gone into understanding whether one can
efficiently sample from approximately the uniform distribution on satisfy
ing assignments\, or approximately count the number of satisfying assignme
nts\, under LLL-like conditions.\n\nI will discuss recent algorithmic prog
ress on this problem\, joint with Huy Tuan Pham (Stanford) and Thuy Duong
Vuong (Stanford).\n
LOCATION:https://stable.researchseminars.org/talk/EPC/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Peter Winkler (Dartmouth College)
DTSTART:20210308T140000Z
DTEND:20210308T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/41
DESCRIPTION:Title: On the Shape of Large Permutations\nby Peter Winkler (Dartmouth Co
llege) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nWhat do large permutations look like? We can in some cases answer
this question with the help of limit structures called "permutons\," and
a variational principle. Examples show nice apparent behavior and a contra
st to the case of graphs and graphons.\n\nJoint work with Rick Kenyon\, Da
n Kráľ and Charles Radin\; later\, with Chris Coscia\, Sayan Das\, Sumit
Mukherjee and Martin Tassy.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Hladky (Czech Academy of Sciences)
DTSTART:20210111T140000Z
DTEND:20210111T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/42
DESCRIPTION:Title: Flip processes on finite graphs and dynamical systems they induce on g
raphons\nby Jan Hladky (Czech Academy of Sciences) as part of Extremal
and probabilistic combinatorics webinar\n\n\nAbstract\nWe introduce a cla
ss of random graph processes\, which we call \\emph{flip processes}. Each
such process is given by a \\emph{rule} which is just a function $\\mathca
l{R}:\\mathcal{H}_k\\rightarrow \\mathcal{H}_k$ from all labelled $k$-vert
ex graphs into itself ($k$ is fixed). Now\, the process starts with a give
n $n$-vertex graph $G_0$. In each step\, the graph $G_i$ is obtained by sa
mpling $k$ random vertices $v_1\,\\ldots\,v_k$ of $G_{i-1}$ and replacing
the induced graph $G_{i-1}[v_1\,\\ldots\,v_k]$ by $\\mathcal{R}(G_{i-1}[v_
1\,\\ldots\,v_k])$. This class contains several previously studied process
es including the Erdos-Renyi random graph process and the random triangle
removal.\n\nGiven a flip processes with a rule $\\mathcal{R}$ we construct
time-indexed trajectories $\\Phi:\\mathcal{W}\\times [0\,\\infty)\\righta
rrow\\mathcal{W}$ in the space of graphons. We prove that with high probab
ility\, starting with a large finite graph $G_0$ which is close to a graph
on $W_0$ in the cut norm distance\, the flip process will stay in a thin s
ausage around the trajectory $(\\Phi(W_0\,t))_{t=0}^\\infty$ (after rescal
ing the time by the square of the order of the graph).\n\nThese graphon tr
ajectories are then studied from the perspective of dynamical systems. We
prove that two trajectories cannot form a confluence\, give an example of
a process with an oscilatory trajectory\, and address the question of exis
tence and stability of fixed points and periodic trajectories.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Corrine Yap (Rutgers University)
DTSTART:20210118T140000Z
DTEND:20210118T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/43
DESCRIPTION:Title: A Topological Turán Problem\nby Corrine Yap (Rutgers University)
as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
nThe classical Turán problem asks: given a graph H\, how many edges can a
n n-vertex graph have while containing no isomorphic copy of H? By viewing
(k+1)-uniform hypergraphs as k-dimensional simplicial complexes\, we can
ask a topological version of this (first posed by Nati Linial): given a k-
dimensional simplicial complex S\, how many facets can an n-vertex k-dimen
sional simplicial complex have while containing no homeomorphic copy of S?
Until recently\, little was known for k > 2. In this talk\, we give an an
swer for general k\, by way of dependent random choice and the combinatori
al notion of a trace-bounded hypergraph. Joint work with Jason Long and Bh
argav Narayanan.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marcus Michelen (University of Illinois at Chicago)
DTSTART:20210125T140000Z
DTEND:20210125T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/44
DESCRIPTION:Title: Roots of random polynomials near the unit circle\nby Marcus Michel
en (University of Illinois at Chicago) as part of Extremal and probabilist
ic combinatorics webinar\n\n\nAbstract\nIt is a well-known (but perhaps su
rprising) fact that a polynomial with independent random coefficients has
most of its roots very close to the unit circle. Using a probabilistic per
spective\, we understand the behavior of roots of random polynomials excep
tionally close to the unit circle and prove several limit theorems\; these
results resolve several conjectures of Shepp and Vanderbei. We will also
discuss how our techniques provide a heuristic\, probabilistic explanation
for why random polynomials tend to have most roots near the unit circle.
Based on joint work with Julian Sahasrabudhe.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lior Gishboliner (Tel-Aviv University)
DTSTART:20210201T140000Z
DTEND:20210201T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/45
DESCRIPTION:Title: Discrepancy of spanning trees\nby Lior Gishboliner (Tel-Aviv Unive
rsity) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nRecently there has been some interest in discrepancy-type problems
on graphs. Here we study the discrepancy of spanning trees. For a connect
ed graph $G$ and a number of colors $r$\, what is the maximum $d = d_r(G)$
such that in any $r$-coloring of the edges of $G$\, there is a spanning t
ree with at least $(n-1)/r + d$ edges of the same color? $d_r(G)$ is calle
d the $r$-color spanning-tree discrepancy of $G$\, and has been recently s
tudied by Balogh\, Csaba\, Jing and Pluhar. As our main result\, we show t
hat under very mild conditions (for example\, if $G$ is 3-connected)\, $d_
r(G)$ is equal\, up to a constant factor\, to the minimal integer s such t
hat G can be separated into r equal parts $V_1\,...\,V_r$ by deleting at m
ost $s$ vertices. This strong and perhaps surprising relation between thes
e two parameters allows us to estimate $d_r(G)$ for many graphs of interes
t. In particular\, we reprove and generalize results of Balogh et al.\, as
well as obtain new ones. Some tight asymptotic results for particular gra
ph classes are also obtained. \n\nJoint work with Michael Krivelevich and
Peleg Michaeli.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hong Liu (University of Warwick)
DTSTART:20210208T140000Z
DTEND:20210208T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/46
DESCRIPTION:Title: Optimal high dimension geometric construction for Ramsey-Turan theory<
/a>\nby Hong Liu (University of Warwick) as part of Extremal and probabili
stic combinatorics webinar\n\n\nAbstract\nCombining two classical notions
in extremal graph theory\, the study of Ramsey-Turan theory seeks to deter
mine\, for integers $m\\le n$ and $p \\leq q$\, the number $RT_p(n\,K_q\,m
)$\, which is the maximum size of an $n$-vertex $K_q$-free graph in which
every set of at least $m$ vertices contains a $K_p$.\n\nTwo major open pro
blems in this area from the 80s ask:\n(1) whether the asymptotic extremal
structure for the general case exhibits certain periodic behaviour\, resem
bling that of the special case when $p=2$ \;\n(2) to construct analogues o
f the Bollobas-Erdos graph with densities other than powers of $1/2$.\n\nW
e refute the first conjecture by witnessing asymptotic extremal structures
that are drastically different from the $p=2$ case\; and address the seco
nd problem by constructing Bollobas-Erdos-type graphs with any rational de
nsity up to $\\frac{1}{2}$ using high dimension complex sphere.\n\nJoint w
ork with Christian Reiher\, Maryam Sharifzadeh and Katherine Staden.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrew Suk (UC San Diego)
DTSTART:20210329T140000Z
DTEND:20210329T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/48
DESCRIPTION:Title: Cliques and sunflowers under bounded VC-dimension\nby Andrew Suk (
UC San Diego) as part of Extremal and probabilistic combinatorics webinar\
n\n\nAbstract\nThe VC-dimension of a set system is one of the most useful
combinatorial parameters that measures its complexity\, and\, apart from i
ts geometric applications\, it has proved to be relevant in many other are
as such as statistics\, logic\, and learning theory. In this talk\, I wil
l discuss two well-known combinatorial problems under bounded VC-dimension
: estimating multicolor Ramsey numbers and the sunflower problem. This ta
lk is based on joint works with Jacob Fox and Janos Pach.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jonathan Tidor (MIT)
DTSTART:20210215T140000Z
DTEND:20210215T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/49
DESCRIPTION:Title: Equiangular lines with a fixed angle\nby Jonathan Tidor (MIT) as p
art of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nA c
onfiguration of N lines through the origin in d-dimensional Euclidean spac
e is called equiangular if the lines are pairwise separated by the same an
gle. A natural and long-standing problem in discrete geometry is to determ
ine the maximum size of a configuration of equiangular lines in a given di
mension.\n\nWe determine\, for each fixed angle and in all sufficiently la
rge dimensions\, the maximum number of equiangular lines separated by this
given angle. Surprisingly\, this maximum depends on spectral graph theore
tic properties of the fixed angle.\n\nOur proof involves the following nov
el result that seems to be of independent interest: A bounded degree conne
cted graph has sublinear second eigenvalue multiplicity (that is\, the mul
tiplicity of the second-largest eigenvalue of the adjacency matrix of the
graph is sublinear in the number of vertices).\n\nJoint work with Zilin Ji
ang\, Yuan Yao\, Shengtong Zhang\, and Yufei Zhao.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Glock (ETH Zurich)
DTSTART:20210412T140000Z
DTEND:20210412T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/50
DESCRIPTION:Title: Long induced paths in sparse random graphs (rescheduled from Feb 22)\nby Stefan Glock (ETH Zurich) as part of Extremal and probabilistic com
binatorics webinar\n\n\nAbstract\nThe study of induced trees in random gra
phs was initiated by Erdős and Palka in the 80s. Many interesting questio
ns remain unanswered\, especially in the sparse case when the average degr
ee is constant. For instance: what is the length of a longest induced path
?\n\nNatural algorithms produce an induced path of length roughly half the
conjectured optimal value\, which has not been improved in the last 30 ye
ars.\n\nWe show that one can do better than that\, which answers a questio
n of Fernandez de la Vega. Unfortunately\, we only get halfway towards the
upper bound. We will explain the main ideas and explore possible ways to
close the remaining gap.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ashwin Sah (MIT)
DTSTART:20210315T140000Z
DTEND:20210315T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/51
DESCRIPTION:Title: Popular differences for matrix patterns\nby Ashwin Sah (MIT) as pa
rt of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nWe s
tudy matrix 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\\s
ubseteq G^k$ has density $\\alpha$\, one might expect based on recent conj
ectures 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 (\\alpha^4-o(1))|G|^k\\] as long as $M_1\,M_2\,M_1\\pm M_2$ define auto
morphisms of $G^k$. We show this conjecture holds in $G = \\mathbb{F}_p^n$
for odd $p$ given an additional spectral condition\, but is false without
this condition. Explicitly\, we show the rotated squares pattern i
s false over $\\mathbb{F}_5^n$. This is in surprising contrast to the theo
ry of popular differences of one-dimensional patterns.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Abhishek Methuku (University of Birmingham)
DTSTART:20210322T140000Z
DTEND:20210322T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/52
DESCRIPTION:Title: A proof of the Erdős–Faber–Lovász conjecture\nby Abhishek Me
thuku (University of Birmingham) as part of Extremal and probabilistic com
binatorics webinar\n\n\nAbstract\nThe celebrated Erd
ős–Faber–Lovász conjecture (posed in 1972) states that the chrom
atic index of any linear hypergraph on n vertices is at most n. In this ta
lk\, I will sketch a proof
\nof this conjecture f
or every large n.\n\nHistory of the problem: Erdős proble
ms\, UCSD.\n\nJoint work with D. Kang\, T. Kelly\, D.Kuhn and D. Osthu
s.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Sidorenko (Rényi Institute of Mathematics)
DTSTART:20210405T140000Z
DTEND:20210405T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/53
DESCRIPTION:Title: On the asymptotic behavior of the classical Turán numbers\nby Ale
xander Sidorenko (Rényi Institute of Mathematics) as part of Extremal and
probabilistic combinatorics webinar\n\n\nAbstract\nA subset of vertices i
n a hypergraph H is called independent if it does not contain an edge of $
H$. The independence number $\\alpha(H)$ is the size of the largest indepe
ndent set. 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) \\le \\alpha$. In other words\, $\\binom{n}{r} - T(n\,k\,r)$ is the la
rgest number of edges in an $n$-vertex $r$-uniform hypergraph that does no
t contain a complete k-vertex subgraph.\n\nThe limit of $T(n\,k\,r) / \\bi
nom{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 bel
ieved that $t(\\alpha+1\,3) = 4/\\alpha^2$. I will discuss the asymptotic
behavior 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://stable.researchseminars.org/talk/EPC/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Torsten Mütze (University of Warwick)
DTSTART:20210426T140000Z
DTEND:20210426T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/54
DESCRIPTION:Title: Combinatorial generation via permutation languages\nby Torsten Mü
tze (University of Warwick) as part of Extremal and probabilistic combinat
orics webinar\n\n\nAbstract\nIn this talk I present a general and versatil
e algorithmic framework for exhaustively generating a large variety of dif
ferent combinatorial objects\, based on encoding them as permutations\, wh
ich provides a unified view on many known results and allows us to prove m
any new ones. This talk gives an overview over three main applications of
our framework: (1) the generation of pattern-avoiding permutations\; (2) t
he generation of various classes of rectangulations\; (3) the generation o
f lattice congruences of the weak order on the symmetric group and of grap
h associahedra.\n\nThis talk is based on joint work with Liz Hartung\, Hun
g P. Hoang\, and Aaron Williams (SODA 2020)\, and with Arturo Merino (SoCG
2021) and Jean Cardinal.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Glock (ETH Zurich)
DTSTART:20210222T140000Z
DTEND:20210222T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/55
DESCRIPTION:Title: rescheduled to to Apr 12 due to technical problems\nby Stefan Gloc
k (ETH Zurich) as part of Extremal and probabilistic combinatorics webinar
\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/EPC/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annie Raymond (University of Massachusetts)
DTSTART:20210419T140000Z
DTEND:20210419T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/56
DESCRIPTION:Title: Graph Density Inequalities\, Sums of Squares and Tropicalization\n
by Annie Raymond (University of Massachusetts) as part of Extremal and pro
babilistic combinatorics webinar\n\n\nAbstract\nEstablishing inequalities
among graph densities is a central pursuit in extremal graph theory. One w
ay to certify 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 explore how one does so and we will then identify simple conditions u
nder which a graph density expression cannot be a sum of squares or a rati
onal sum of squares. Tropicalization will play a key role for the latter\,
and will turn out to be an interesting object in itself. This is joint wo
rk with Greg Blekherman\, Mohit Singh\, and Rekha Thomas.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Istvan Tomon (ETH Zurich)
DTSTART:20210503T140000Z
DTEND:20210503T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/57
DESCRIPTION:Title: Ramsey properties of string graphs\nby Istvan Tomon (ETH Zurich) a
s part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\n
In this talk\, I will give an outline of the proof of the following conjec
ture of Alon\, Pach\, Pinchasi\, Radoicic and Sharir. There exists an abso
lute constant $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 wh
ich any two elements intersect\, or any two are disjoint. This generalizes
many earlier results about the Ramsey properties of intersection graphs o
f geometric objects. The heart of our proof is a purely graph theoretic le
mma\, which turned out to be quite useful in other Erdos-Hajnal type resul
ts as well\, see e.g. the recent proof of the Erdos-Hajnal conjecture for
the cycle of length 5 by Chudnovsky\, Scott\, Seymour and Spirkl. For this
talk\, no knowledge of geometry is required.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/57/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Raphael Yuster (University of Haifa)
DTSTART:20210621T140000Z
DTEND:20210621T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/58
DESCRIPTION:Title: Hamilton cycles above expectation in r-graphs and quasi-random r-graph
s\nby Raphael Yuster (University of Haifa) as part of Extremal and pro
babilistic combinatorics webinar\n\n\nAbstract\nLet $H_r(n\,p)$ denote the
maximum number of (tight) Hamilton cycles in an n-vertex r-graph with den
sity $p \\in (0\,1)$. The expected number of Hamilton cycles in the random
r-graph $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 t
o be slightly smaller than $E(n\,p)$.\n\nFor graphs\, $H_2(n\,p)$ it is pr
oved to be only larger than $E(n\,p)$ by a polynomial factor and it is an
open problem whether a quasi-random graph with density p can be larger tha
n $E(n\,p)$ by a polynomial factor.\n\nFor hypergraphs the situation is dr
astically 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-random r-graphs with density p whose number of Hamilton cycles is la
rger than $E(n\,p)$ by an exponential factor.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/58/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrzej Grzesik (Jagiellonian University)
DTSTART:20210510T140000Z
DTEND:20210510T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/59
DESCRIPTION:Title: Generalized Turán problem for cycles\nby Andrzej Grzesik (Jagiell
onian University) as part of Extremal and probabilistic combinatorics webi
nar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/EPC/59/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xizhi Liu (University of Illinois at Chicago)
DTSTART:20210517T140000Z
DTEND:20210517T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/70
DESCRIPTION:Title: A unified approach to hypergraph stability\nby Xizhi Liu (Universi
ty of Illinois at Chicago) as part of Extremal and probabilistic combinato
rics webinar\n\n\nAbstract\nWe present a method which provides a unified f
ramework for many stability theorems that have been proved in graph and hy
pergraph theory. Our main result reduces stability for a large class of hy
pergraph problems to the simpler question of checking that a hypergraph
$\\mathcal H$ with large minimum degree that omits the forbidden structur
es is vertex-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). I
n many cases vertex-extendability is quite easy to verify.\n\nOur method a
lways yields an Andrásfai-Erdős-Sós type result\, which says if $\\math
cal H$ has large minimum degree\, then it must be a subgraph of one of the
extremal configurations.\n\nThis is joint work with Dhruv Mubayi and Chri
stian Reiher.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/70/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aditya Potukuchi (University of Illinois at Chicago)
DTSTART:20210524T140000Z
DTEND:20210524T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/71
DESCRIPTION:Title: Enumerating independent sets in Abelian Cayley graphs\nby Aditya P
otukuchi (University of Illinois at Chicago) as part of Extremal and proba
bilistic combinatorics webinar\n\n\nAbstract\nWe show that any Cayley grap
h on an Abelian group of order 2n and degree $\\tilde{\\Omega}(\\log n)$ h
as at most $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 th
e container method and the Pl\\"{u}nnecke-Rusza-Petridis inequality from a
dditive combinatorics.\n\nJoint work with Liana Yepremyan.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/71/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jozsef Solymosi (University of British Columbia)
DTSTART:20210531T140000Z
DTEND:20210531T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/72
DESCRIPTION:Title: On Erdős' Unit Distances Problem\nby Jozsef Solymosi (University
of British Columbia) as part of Extremal and probabilistic combinatorics w
ebinar\n\n\nAbstract\nIn 1946\, Paul Erdős published a paper in the Ameri
can Mathematical Monthly "On sets of distances of n points". He proposed t
wo problems in discrete geometry. What is the minimum number of distinct d
istances among n points in the plane\, and among n points in the plane how
many pairs of points could be at unit distance from each other? The first
question was answered almost completely by Larry Guth and Netz Katz in 20
10\, but the second\, on unit distances\, resisted all attacks so far. I w
ill talk about the unit distances problems\, and related questions.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/72/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicolás Sanhueza-Matamala (Czech Academy of Sciences)
DTSTART:20210614T140000Z
DTEND:20210614T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/73
DESCRIPTION:Title: Degree conditions for spanning structures in dense graphs\nby Nico
lás Sanhueza-Matamala (Czech Academy of Sciences) as part of Extremal and
probabilistic combinatorics webinar\n\n\nAbstract\nA classic theorem of D
irac (1952) states that a graph in which every vertex is connected to at l
east half of the other vertices contains a Hamilton cycle. Over the years\
, this result has been generalised in several ways. Some generalisations w
eaken the assumptions (by not requiring every vertex to have large minimum
degree)\, and other generalisations strengthen the outcome (by considerin
g spanning structures which are not cycles). We investigate the combinatio
n of these two directions\, and find cycles and other spanning structures
under various degree conditions. Along the way\, we recover known results
and obtain many new ones. Joint work with Richard Lang.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/73/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Correia (ETH Zurich)
DTSTART:20210628T140000Z
DTEND:20210628T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/74
DESCRIPTION:Title: Tight bounds for powers of Hamilton cycles in tournaments\nby Davi
d Correia (ETH Zurich) as part of Extremal and probabilistic combinatorics
webinar\n\n\nAbstract\nA basic result in graph theory says that any n-ver
tex tournament with in- and out-degrees at least n/4 contains a Hamilton c
ycle\, and this is essentially tight. In 1990\, Bollobás and Häggkvist s
ignificantly extended this by showing that for any fixed k and ε >0\, and
sufficiently large n\, all tournaments with degrees at least n/4+εn cont
ain the k-th power of a Hamilton cycle. Given this\, it is natural to ask
for a more accurate error term in the degree condition. We show that if th
e degrees 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 par
ticular\, in order to guarantee the square of a Hamilton cycle\, one only
requires a constant additive term. We also present a construction which\,
modulo a well-known conjecture on Turán numbers for complete bipartite gr
aphs\, 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\, w
e believe that the lower bound can be improved and we show that for k=3\,
there exist tournaments with degrees $n/4+Ω(n^{1/5})$ and no cube of a Ha
milton cycle. Additionally we also show that the Bollobás-Häggkvist theo
rem already holds for $n=ε^{−Θ(k)}$\, which is best possible. This is
joint work with Nemanja Draganic and Benny Sudakov.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/74/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natasha Morrison (University of Victoria)
DTSTART:20211101T140000Z
DTEND:20211101T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/75
DESCRIPTION:Title: Uncommon systems of equations\nby Natasha Morrison (University of
Victoria) as part of Extremal and probabilistic combinatorics webinar\n\n\
nAbstract\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 $
\\mathbb{F}_q^n$ is asymptotically at least the expected number of monochr
omatic solutions in a random two-colouring of $\\mathbb{F}_q^n$. Motivated
by existing results for specific systems (such as Schur triples and arith
metic progressions)\, as well as extensive research on common and Sidorenk
o graphs\, the systematic study of common systems of linear equations was
recently initiated by Saad and Wolf. Building on earlier work of Cameron\,
Cilleruelo and Serra\, as well as Saad and Wolf\, common linear equations
have been fully characterised by Fox\, Pham and Zhao.\n\nIn this talk I w
ill discuss some recent progress towards a characterisation of common syst
ems of two or more equations. In particular we prove that any system conta
ining an arithmetic progression of length four is uncommon\, confirming a
conjecture of Saad and Wolf. This follows from a more general result which
allows us to deduce the uncommonness of a general system from certain pro
perties of one- or two-equation subsystems.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/75/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ander Lamaison (Masaryk University)
DTSTART:20211108T140000Z
DTEND:20211108T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/76
DESCRIPTION:Title: Hypergraphs with minimum positive uniform Turán density\nby Ander
Lamaison (Masaryk University) as part of Extremal and probabilistic combi
natorics webinar\n\n\nAbstract\nReiher\, Rödl and Schacht showed that the
uniform Turán density of every 3-uniform hypergraph is either 0 or at le
ast 1/27\, and asked whether there exist 3-uniform hypergraphs with unifor
m Turán density equal or arbitrarily close to 1/27. We construct 3-unifor
m hypergraphs with uniform Turán density equal to 1/27. This is based on
joint work with Frederik Garbe and Daniel Kráľ.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/76/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rajko Nenadov (Google)
DTSTART:20211115T140000Z
DTEND:20211115T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/77
DESCRIPTION:Title: A new proof of the KŁR conjecture\nby Rajko Nenadov (Google) as p
art of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nWe
give a new\, short and intuitive proof of the celebrated KŁR conjecture.
Slightly rephrased\, the conjecture states that if we condition on unifor
m edge distribution\, the archetypal property of random graphs\, the proba
bility that the Erdős–Rényi random graph G(n\,m) does not contain a co
py of a fixed graph H becomes superexponentially small in m\, for sufficie
ntly large m > m(n\, H). As its most prominent application\, this conjectu
re implies that with high probability all subgraphs of the binomial random
graph with appropriate parameters satisfy an embedding lemma which comple
ments the sparse regularity lemma. The proof proceeds by induction and\, i
n some way\, can be considered a `deterministic' analogue of the multiple-
exposure technique from random graph theory.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/77/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Julia Böttcher (LSE)
DTSTART:20211122T140000Z
DTEND:20211122T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/78
DESCRIPTION:by Julia Böttcher (LSE) as part of Extremal and probabilistic
combinatorics webinar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/EPC/78/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bernard Lidický (Iowa State University)
DTSTART:20211129T140000Z
DTEND:20211129T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/79
DESCRIPTION:Title: Maximum number of almost similar triangles in the plane\nby Bernar
d Lidický (Iowa State University) as part of Extremal and probabilistic c
ombinatorics webinar\n\n\nAbstract\nA triangle $T'$ is $\\varepsilon$-simi
lar to another triangle $T$ if their angles pairwise differ by at most $\\
varepsilon$. Given a triangle $T$\, $\\varepsilon >0$ and $n \\in \\mathbb
{N}$\, Bárány and Füredi asked to determine the maximum number of trian
gles $h(n\,T\,\\varepsilon)$ being $\\varepsilon$-similar to $T$ in a plan
ar point 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 u
se flag algebras and stability techniques for the proof. This is joint wor
k with József Balogh and Felix Christian Clemen.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/79/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Dan Kráľ (Masaryk University)
DTSTART:20211220T140000Z
DTEND:20211220T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/80
DESCRIPTION:Title: Quasirandom graphs\, permutations and Latin squares\nby Dan Kráľ
(Masaryk 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 quasirandom graphs\, developed in the work of Rödl\, Thomason\, Chung\
, Graham and Wilson in 1980s\, is particularly robust as several different
properties of truly random graphs\, e.g.\, subgraph density\, edge distri
bution and spectral properties\, are satisfied by a large graph if and onl
y if one of them is. A closely related notion is the notion of common grap
hs\, which are graphs whose number of monochromatic copies is minimized by
the (quasi)random coloring of a host complete graph.\n\n
\nWe wi
ll discuss quasirandom properties of permutations and Latin squares\, and
present several recent results obtained using analytic tools of the theory
of combinatorial limits. We will also present some recent results on comm
on and locally common graphs\, in particular\, we show that there exists c
ommon connected graphs with arbitrary large chromatic number\, whose exist
ence was an open problem for more than 20 years.\n\n\nThe talk is based on
results obtained with different groups of collaborators\, including Timot
hy F. N. Chan\, Jacob W. Cooper\, Robert Hancock\, Matjaž Krnc\, Ander La
maison\, Samuel Mohr\, Jonathan A. Noel\, Sergey Norin\, Yanitsa Pehova\,
Oleg Pikhurko\, Maryam Sharifzadeh\, Jan Volec and Fan
\nWei.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/80/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benedikt Stufler (TU Wien)
DTSTART:20211206T140000Z
DTEND:20211206T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/81
DESCRIPTION:Title: Local convergence of random planar graphs\nby Benedikt Stufler (TU
Wien) as part of Extremal and probabilistic combinatorics webinar\n\n\nAb
stract\nThe study of random combinatorial structures and their limits is a
growing field at the interface of combinatorics\, probability theory\, an
d mathematical physics. Planar graphs are a prominent example of such stru
ctures\, yet important problems concerning their asymptotic shape remain o
pen. This talk highlights open conjectures and reviews recent results\, in
particular the discovery of a Uniform Infinite Planar Graph (UIPG) as the
ir quenched local limit.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/81/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Candida Bowtell (University of Oxford)
DTSTART:20211213T140000Z
DTEND:20211213T150000Z
DTSTAMP:20260404T110827Z
UID:EPC/82
DESCRIPTION:Title: The n-queens problem\nby Candida Bowtell (University of Oxford) as
part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\nH
ow many ways are there to place n queens on an n by n chessboard so that n
o two can attack one another? What if the chessboard is embedded on the to
rus? Let Q(n) be the number of ways on the standard chessboard and T(n) th
e number 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 bo
unds were known to hold for all (sufficiently large) n not divisible by 2
or 3. We also show that Q(n) is at least $\\left((1+o(1))ne^{-3}\\right)^n
$ for all natural numbers n which was independently proved by Luria and Si
mkin and\, combined with our toroidal result\, completely settles a conjec
ture of Rivin\, Vardi and Zimmerman regarding both Q(n) and T(n).\n\nIn th
is talk we'll discuss our methods used to prove these results. A crucial e
lement of this is translating the problem to one of counting matchings in
a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy al
gorithm to count `almost' configurations with a complex absorbing strategy
that uses ideas from the methods of randomised algebraic construction and
iterative absorption.\n\nThis is joint work with Peter Keevash.\n
LOCATION:https://stable.researchseminars.org/talk/EPC/82/
END:VEVENT
END:VCALENDAR