BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Yifan Jing (UIUC)
DTSTART:20200603T130000Z
DTEND:20200603T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/1
DESCRIPTION:Title: Structures of sets with minimal measure growth\nby Yifan Jing (UIUC
) as part of Warwick Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/WCS/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yahav Alon (Tel Aviv)
DTSTART:20200610T130000Z
DTEND:20200610T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/2
DESCRIPTION:Title: Hitting time of disjoint Hamilton cycles in random subgraph processes\nby Yahav Alon (Tel Aviv) as part of Warwick Combinatorics Seminar\n\nA
bstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/WCS/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrzej Grzesik (Jagiellonian)
DTSTART:20200617T130000Z
DTEND:20200617T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/3
DESCRIPTION:Title: The Turán number of blow-ups of trees\nby Andrzej Grzesik (Jagiell
onian) as part of Warwick Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/WCS/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bjarne Schülke (Hamburg)
DTSTART:20200624T130000Z
DTEND:20200624T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/4
DESCRIPTION:Title: Extremal problems concerning the traces of sets\nby Bjarne Schülke
(Hamburg) as part of Warwick Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/WCS/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:László Lovász (Budapest)
DTSTART:20201009T130000Z
DTEND:20201009T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/5
DESCRIPTION:Title: Graph limits\, measures\, and flows\nby László Lovász (Budapest)
as part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe theory of gra
ph limits is only understood to a somewhat\nsatisfactory degree in the cas
es of dense graphs and of bounded degree\ngraphs. There is\, however\, a l
ot of interest in the intermediate cases.\nIt appears that the most import
ant constituents of graph limits in the\ngeneral case will be Markov space
s (Markov chains on measurable spaces\nwith a stationary distribution).\n\
nThis motivates our goal to extend some important theorems from finite\ngr
aphs to Markov spaces or\, more generally\, to measurable spaces. In\nthis
talk we show that much of flow theory\, one of the most important\nareas
in graph theory\, can be extended to measurable spaces. In\nparticular\, t
he Hoffman Circulation Theorem\, the Max-Flow-Min-Cut\nTheorem\, Multicomm
odity Flow Theorem\, and several other results have\nsimple and elegant ex
tensions to measures.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marthe Bonamy (Bordeaux)
DTSTART:20201016T130000Z
DTEND:20201016T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/6
DESCRIPTION:Title: Graph recolouring\nby Marthe Bonamy (Bordeaux) as part of Warwick C
ombinatorics Seminar\n\n\nAbstract\nGiven a solution to a problem\, we can
try and apply a series of elementary operations to it\, making sure to re
main in the solution space at every step. What kind of solutions can we re
ach this way? How fast? This is motivated by a variety of applications\, f
rom statistical physics to real-life scenarios\, including enumeration and
sampling. In this talk\, we will discuss various positive and negative re
sults\, in the special case of graph colouring.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gábor Tardos (Budapest)
DTSTART:20201023T130000Z
DTEND:20201023T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/7
DESCRIPTION:Title: Convergence and limits of finite trees\nby Gábor Tardos (Budapest)
as part of Warwick Combinatorics Seminar\n\n\nAbstract\nSeeing the succes
s of limit theory of dense finite graphs with graphons as their limit obje
cts we developed a similar (?) theory for finite trees. In order for the s
ampling limit to make sense we need to make the trees "dense" - we do this
by considering them as metric spaces with the normalized graph distance.
Using ultaproducts is a simple and elegant way to find unique limit object
s (we call them dendrons) and also to highlight similarities and major dif
ferences from the theory of dense graph limits. For the underlying quantit
ative approximation results\, one needs more "down to earth" techniques to
be developed.\nThis is joint work with Gábor Elek.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Maria Chudnovsky (Princeton)
DTSTART:20201030T140000Z
DTEND:20201030T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/8
DESCRIPTION:Title: Even-hole free graphs of bounded degree have bounded treewidth\nby
Maria Chudnovsky (Princeton) as part of Warwick Combinatorics Seminar\n\n\
nAbstract\nTree decompositions are a powerful tool in structural graph the
ory that is traditionally used in the context of forbidden graph minors.
Connecting tree decompositions and forbidden induced subgraphs has so far
largely remained out of reach. Traditionally to bound the treewidth of a g
raph\, one finds a way to decompose it by a so-called laminar collection o
f\ndecompositions. Recently\, in joint work with Tara Abrishami and Krist
ina \nVuskovic\, we proved that even-hole free graphs of bounded degree h
ave bounded tree-width. To do so we used "star cutset separations" that ar
ise naturally in the context of even-hole-free graphs. While the set of st
ar cutset separations is far from being non-crossing\, it turns out that o
ne can partition it into a bounded number of laminar collections\, and thi
s is sufficient for our purposes.\nIn this talk we will present an outline
of the proof.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Boris Bukh (Pittsburgh)
DTSTART:20201106T140000Z
DTEND:20201106T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/9
DESCRIPTION:Title: Empty axis-parallel boxes\nby Boris Bukh (Pittsburgh) as part of Wa
rwick Combinatorics Seminar\n\n\nAbstract\nHow to place n points inside th
e d-dimensional unit cube so every large axis-parallel box contains at lea
st one point? We discuss the motivation as well as a partial solution to t
his problem. This is a joint work with Ting-Wei Chao.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tibor Szabó (Berlin)
DTSTART:20201113T140000Z
DTEND:20201113T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/10
DESCRIPTION:Title: Mader-perfect digraphs\nby Tibor Szabó (Berlin) as part of Warwic
k Combinatorics Seminar\n\n\nAbstract\nWe investigate the relationship of
dichromatic number and subdivision containment in digraphs. We call a digr
aph Mader-perfect if for every (induced) subdigraph $F$\, any digraph of d
ichromatic number at least $v(F)$ contains an $F$-subdivision. We show tha
t\, among others\, arbitrary orientated cycles\, bioriented trees\, and to
urnaments on four vertices are Mader-perfect. The first result settles a c
onjecture of Aboulker\, Cohen\, Havet\, Lochet\, Moura\, and Thomasse\, wh
ile the last one extends Dirac's Theorem about $4$-chromatic graphs contai
ning a $K_4$-subdivision to directed graphs. The talk represents joint wor
k with Lior Gishboliner and Raphael Steiner.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benny Sudakov (Zurich)
DTSTART:20201120T140000Z
DTEND:20201120T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/11
DESCRIPTION:Title: Large independent sets from local considerations\nby Benny Sudakov
(Zurich) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nHow well
can global properties of a graph be inferred from observations that are p
urely local? This general question gives rise to numerous interesting prob
lems. One such very natural question was raised independently by Erdos-Haj
nal and Linial-Rabinovich in the early 90's. How large must the independen
ce number $\\alpha (G)$ of a graph $G$ be whose every $m$ vertices contain
an independent set of size $r$? In this talk we discuss new methods to at
tack this problem which improve many previous results.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anton Bernshteyn (Georgia Tech)
DTSTART:20201127T140000Z
DTEND:20201127T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/12
DESCRIPTION:Title: Measurable colorings\, the Lovász Local Lemma\, and distributed algor
ithms\nby Anton Bernshteyn (Georgia Tech) as part of Warwick Combinato
rics Seminar\n\n\nAbstract\nIn the past twenty or so years\, a rich theory
has emerged concerning the behavior of graph colorings\, matchings\, and
other combinatorial notions under additional regularity requirements\, for
instance measurability. It turns out that this area is closely related to
distributed computing\, i.e.\, the part of computer science concerned wit
h problems that can be solved efficiently by a decentralized network of pr
ocessors. A key role in this relationship is played by the Lovász Local L
emma and its analogs in the measurable setting. In this talk I will outlin
e this relationship and present a number of applications.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bhargav Narayanan (Rutgers)
DTSTART:20201204T140000Z
DTEND:20201204T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/13
DESCRIPTION:Title: Homeomorphs\nby Bhargav Narayanan (Rutgers) as part of Warwick Com
binatorics Seminar\n\n\nAbstract\nNati Linial asked the following basic pr
oblem in 2006: Given a $k$-dimensional simplicial complex $S$\, how many f
acets can a $k$-complex on $n$ vertices have if it contains no topological
copy of $S$? This is a beautiful and natural question\, but results in lo
w dimensions apart ($k\\le 2$)\, very little was previously known. In this
talk\, I’ll provide an answer in all dimensions and take the scenic rou
te to the answer\, surveying many natural problems about simplicial comple
xes along the way.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hong Liu (Warwick)
DTSTART:20201211T140000Z
DTEND:20201211T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/14
DESCRIPTION:Title: Extremal density for sparse minors and subdivisions\nby Hong Liu (
Warwick) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nHow dense
a graph has to be to necessarily contain (topological) minors of a given
graph $H$? When $H$ is a complete graph\, this question is well understood
by result of Kostochka/Thomason for clique minor\, and result of Bollobas
-Thomason/Komlos-Szemeredi for topological minor. The situation is a lot l
ess clear when $H$ is a sparse graph. We will present a general result on
optimal density condition forcing (topological) minors of a wide range of
sparse graphs. As corollaries\, we resolve several questions of Reed and W
ood on embedding sparse minors. Among others\,\n\n - $(1+o(1))t^2$ av
erage degree is sufficient to force the $t\\times t$ grid as a topological
minor\;\n\n - $(3/2+o(1))t$ average degree forces $every$ $t$-vertex
planar graph as a minor\, and the constant $3/2$ is optimal\, furthermore
\, surprisingly\, the value is the same for $t$-vertex graphs embeddable o
n any fixed surface\;\n\n - a universal bound of $(2+o(1))t$ on avera
ge degree forcing $every$ $t$-vertex graph in $any$ nontrivial minor-close
d family as a minor\, and the constant 2 is best possible by considering g
raphs with given treewidth.\n\nJoint work with John Haslegrave and Jaehoon
Kim.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pál Galicza (Budapest)
DTSTART:20210115T140000Z
DTEND:20210115T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/15
DESCRIPTION:Title: Sparse reconstruction for iid variables\nby Pál Galicza (Budapest
) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nFor a sequence o
f Boolean functions $f_n : \\{-1\,1\\}^{V_n} \\longrightarrow \\{-1\,1\\}$
\, defined on increasing configuration spaces of random inputs\, we say th
at there is sparse reconstruction if there is a sequence of subsets $U_n \
\subseteq V_n$ of the coordinates satisfying $|U_n| = o(|V_n|)$ such that
knowing the coordinates in $U_n$ gives us a non-vanishing amount of infor
mation about the value of $f_n$.\n\nWe first show that\, if the underlying
measure is a product measure\, then no sparse reconstruction is possible
for any sequence of transitive functions. We discuss the question in diffe
rent frameworks\, measuring information content in $L^2$ and with entropy.
We also highlight some interesting connections with cooperative game theo
ry.\n\nUsing our results for transitive sequences of functions\, we answe
r a question posed by Itai Benjamini and show that the left-right crossing
event for critical planar percolation on the square lattice does not admi
t sparse reconstruction either. Joint work with Gábor Pete.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Razborov (Chicago)
DTSTART:20210122T173000Z
DTEND:20210122T183000Z
DTSTAMP:20260404T094310Z
UID:WCS/16
DESCRIPTION:Title: Theons and quasirandomness\nby Alexander Razborov (Chicago) as par
t of Warwick Combinatorics Seminar\n\n\nAbstract\nThere are two known appr
oaches to the theory of limits of discrete combinatorial objects: geometri
c (graph limits) and algebraic (flag algebras). In the first part of the t
alk we present a general framework intending to combine useful features of
both theories and compare it with previous attempts of this kind. Our mai
n objects are $T$-ons\, for a\nuniversal relational first-order theory $T$
\; they generalize many previously considered partial cases\, some of them
(like permutons) in a non-trivial way.\n\nIn the second part we apply thi
s framework to offer a new perspective on quasi-randomness for combinatori
al objects more complicated than ordinary graphs. Our quasi-randomness pro
perties are natural in the sense that they do not use ad hoc densities and
they are preserved under the operation of defining combinatorial structur
es of one kind from structures of a different kind. One key concept in thi
s theory is that of unique coupleability roughly meaning that any alignmen
t of two objects on the same ground set should ``look like'' random.\n\nBa
sed on joint work with Leonardo Coregliano.\n\nNote the unusual time!\n
LOCATION:https://stable.researchseminars.org/talk/WCS/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lisa Sauermann (IAS)
DTSTART:20210129T140000Z
DTEND:20210129T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/17
DESCRIPTION:Title: On polynomials that vanish to high order on most of the hypercube\
nby Lisa Sauermann (IAS) as part of Warwick Combinatorics Seminar\n\n\nAbs
tract\nMotivated by higher vanishing multiplicity generalizations of Alon'
s Combinatorial Nullstellensatz and its applications\, we study the follow
ing problem: for fixed k and n large with respect to $k$\, what is the min
imum 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 of multiplicity at le
ast $k$ at all points in $\\{0\,1\\}^n$ except the origin? For $k=1$\, a c
lassical theorem of Alon and Füredi states that the minimum possible degr
ee of such a polynomial equals $n$. We solve the problem for all $k>1$\, p
roving that the answer is $n+2k−3$. Joint work with Yuval Wigderson.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gábor Pete (Budapest)
DTSTART:20210212T140000Z
DTEND:20210212T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/18
DESCRIPTION:Title: The Free Uniform Spanning Forest is disconnected in some virtually fre
e groups\, depending on the generating set\nby Gábor Pete (Budapest)
as part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe uniform random
spanning tree of a finite graph is a classical object in probability and
combinatorics. In an infinite graph\, one can take any exhaustion by finit
e subgraphs\, with some boundary conditions\, and take the limit measure.
The Free Uniform Spanning Forest (FUSF) is one of the natural limits\, but
it is less understood than the wired version\, the WUSF. Taking a finitel
y generated group\, several properties of WUSF and FUSF have been known to
be independent of the chosen Cayley graph of the group: the average degre
e in WUSF and in FUSF\; the number of ends in the components of the WUSF a
nd of the FUSF\; the number of trees in the WUSF. Lyons and Peres asked if
this latter should also be the case for the FUSF.\n\nIn joint work with
Ádám Timár\, we give two different Cayley graphs of the same group such
that the FUSF is connected in one of them but has infinitely many trees i
n the other. Since our example is a virtually free group\, this is also a
counterexample to the general expectation that such "tree-like" graphs wou
ld have connected FUSF. Many open questions are inspired by the results.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Kurkofka (Hamburg)
DTSTART:20210219T140000Z
DTEND:20210219T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/19
DESCRIPTION:Title: Every infinitely edge-connected graph contains the Farey graph or $T_{
\\aleph_0}*t$ as a minor\nby Jan Kurkofka (Hamburg) as part of Warwick
Combinatorics Seminar\n\n\nAbstract\nThe Farey graph plays a role in a nu
mber of mathematical fields ranging from group theory and number theory to
geometry and dynamics. Curiously\, graph theory is not among these. We sh
ow that the Farey graph plays a central role in graph theory too: it is on
e of two infinitely edge-connected graphs that must occur as a minor in ev
ery infinitely edge-connected graph. Previously it was not known that ther
e was any set of graphs determining infinite edge-connectivity by forming
a minor-minimal list in this way\, let alone a finite set.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Tech)
DTSTART:20210226T140000Z
DTEND:20210226T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/20
DESCRIPTION:Title: Prague dimension of random graphs\nby Lutz Warnke (Georgia Tech) a
s part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe Prague dimensio
n of graphs was introduced by Nesetril\, Pultr and Rodl in the 1970s: as a
combinatorial measure of complexity\, it is closely related to clique edg
es coverings and partitions. Proving a conjecture of Furedi and Kantor\, w
e show that the Prague dimension of the binomial random graph is typically
of order n/(log n) for constant edge-probabilities. \nThe main new proof
ingredient is a Pippenger-Spencer type edge-coloring result for random hyp
ergraphs with large uniformities\, i.e.\, edges of size O(log n). \n\nBase
d on joint work with He Guo and Kalen Patton\, see https://arxiv.org/abs/2
011.09459\n
LOCATION:https://stable.researchseminars.org/talk/WCS/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louis Esperet (Grenoble)
DTSTART:20210305T133000Z
DTEND:20210305T143000Z
DTSTAMP:20260404T094310Z
UID:WCS/21
DESCRIPTION:Title: Asymptotic dimension of graphs\nby Louis Esperet (Grenoble) as par
t of Warwick Combinatorics Seminar\n\n\nAbstract\nThe asymptotic dimension
of a metric space is a notion introduced by Gromov in the 90s\, in connec
tion with geometric group theory. In the special case of the shortest path
metric associated to a graph\, a related notion\, called "weak network de
composition" has been independently considered by theoretical computer sci
entists\, with a different motivation. I will also explain some links with
the classical notion of graph coloring\, and some variants that have been
studied since the end of the 90s.\n\nA class of graphs is minor-closed if
any graph obtained from a graph in the class by deleting vertices or edge
s\, or contracting edges\, is still in the class. A typical example is the
class of all graphs embeddable on a fixed surface. We prove that every pr
oper minor-closed family of graphs has asymptotic dimension at most 2\, wh
ich gives optimal answers to a question of Fujiwara and Papasoglu and to a
problem raised by Ostrovskii and Rosenthal on minor excluded groups.\n\nJ
oint work with M. Bonamy\, N. Bousquet\, C. Groenland\, C.-H. Liu\, F. Pir
ot\, and A. Scott.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annie Raymond (Massachusetts Amherst)
DTSTART:20210312T140000Z
DTEND:20210312T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/22
DESCRIPTION:Title: Graph Density Inequalities\, Sums of Squares and Tropicalization\n
by Annie Raymond (Massachusetts Amherst) as part of Warwick Combinatorics
Seminar\n\n\nAbstract\nEstablishing inequalities among graph densities is
a central pursuit in extremal graph theory. One way to certify the nonnega
tivity 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 under which a graph densit
y expression cannot be a sum of squares or a rational sum of squares. Trop
icalization will play a key role for the latter\, and will turn out to be
an interesting object in itself. This is joint work with Greg Blekherman\,
Mohit Singh\, and Rekha Thomas.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Spielman (Yale)
DTSTART:20210319T173000Z
DTEND:20210319T183000Z
DTSTAMP:20260404T094310Z
UID:WCS/23
DESCRIPTION:Title: Finite Free Probability and Ramanujan Graphs\nby Daniel Spielman (
Yale) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nWe introduce
a finite analog of Voiculescu's Free Probability that allows us to comput
e the expected characteristic polynomials of certain random matrices and t
o prove bounds on the locations of the roots of those polynomials. We sket
ch how this theory may be used to prove that there exist bipartite Ramanuj
an graphs of every degree and number of vertices.\n\nNo prior knowledge of
free probability or Ramanujan graphs will be assumed.\n\nThis is joint wo
rk with Adam Marcus and Nikhil Srivastava.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Agnes Backhausz (Budapest)
DTSTART:20210430T130000Z
DTEND:20210430T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/24
DESCRIPTION:Title: Typicality and entropy of processes on infinite trees\nby Agnes Ba
ckhausz (Budapest) as part of Warwick Combinatorics Seminar\n\n\nAbstract\
nWhen we study random $d$-regular graphs from the point of view of graph l
imit theory\, the notion of typical processes arise naturally. These are c
ertain invariant families of random variables indexed by the infinite regu
lar tree. Since this tree is the local limit of random $d$-regular graphs
when $d$ is fixed and the number of vertices tends to infinity\, we can co
nsider the processes that can be approximated with colorings (labelings) o
f random $d$-regular graphs. These are the so-called typical processes\, w
hose properties contain useful information about the structure of finite r
andom regular graphs. In earlier works\, various necessary conditions have
been given for a process to be typical\, by using correlation decay or en
tropy inequalities. In the work presented in the talk\, we go in the other
direction and provide sufficient entropy conditions in the special case o
f edge Markov processes. This condition can be extended to unimodular Galt
on--Watson random trees as well. Joint work with Charles Bordenave and Bal
ázs Szegedy (https://arxiv.org/abs/2102.02653).\n
LOCATION:https://stable.researchseminars.org/talk/WCS/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwen McKinley (San Diego)
DTSTART:20210507T163000Z
DTEND:20210507T173000Z
DTSTAMP:20260404T094310Z
UID:WCS/25
DESCRIPTION:Title: Counting integer partitions with the method of maximum entropy\nby
Gwen McKinley (San Diego) as part of Warwick Combinatorics Seminar\n\n\nA
bstract\nWe give an asymptotic formula for the number of partitions of an
integer $n$ where the sums of the $k$th powers of the parts are also fixed
\, for some collection of values $k$. To obtain this result\, we reframe t
he counting problem as an optimization problem\, and find the probability
distribution on the set of all integer partitions with maximum entropy amo
ng those that satisfy our restrictions in expectation (in essence\, this i
s an application of Jaynes' principle of maximum entropy). This approach l
eads to an approximate version of our formula as the solution to a relativ
ely straightforward optimization problem over real-valued functions. To es
tablish more precise asymptotics\, we prove a local central limit theorem
using an equidistribution result of Green and Tao.\n\nA large portion of t
he talk will be devoted to outlining how our method can be used to re-deri
ve a classical result of Hardy and Ramanujan\, with an emphasis on the int
uitions behind the method\, and limited technical detail. This is joint wo
rk with Marcus Michelen and Will Perkins.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Schweitzer (Darmstadt)
DTSTART:20210514T130000Z
DTEND:20210514T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/26
DESCRIPTION:Title: Automorphisms of graphs with a forbidden minor\nby Pascal Schweitz
er (Darmstadt) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nAcc
ording to Frucht’s classic theorem\, every finite group is the automorph
ism group of a finite graph (up to isomorphism). We say the class of all g
raphs is universal. Babai proved in 1974 that graph classes with a forbidd
en minor\, such as planar graphs\, graphs of bounded genus\, and graphs of
bounded tree width\, are not universal. He also made three conjectures re
garding automorphisms of such graphs. I will describe a structure theorem
of automorphism groups of such graphs\, affirming these conjectures.\n\nTh
is is joint work with Martin Grohe and Daniel Wiebking.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabor Elek (Lancaster)
DTSTART:20210521T130000Z
DTEND:20210521T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/27
DESCRIPTION:Title: Uniform amenability\nby Gabor Elek (Lancaster) as part of Warwick
Combinatorics Seminar\n\n\nAbstract\nAccording to the classical result of
Connes\, Feldman and Weiss\, measured hyperfiniteness of a group action is
equivalent to measured amenability. In the Borel category it is known th
at hyperfiniteness implies amenability and it is conjectured that the conv
erse is true. Based on the work of Anantharaman-Delaroche and Renault\, on
e can introduce the notion of uniform amenability\, a strengthening of mea
sured amenability (it is a sort of exactness in the category of measurable
actions\, so the famous Gromov-Osajda groups have no free uniformly amena
ble actions). One can also introduce the notion of uniform hyperfiniteness
in a rather natural way. We prove that the two notions are equivalent pro
vided that the measurable action satisfies a boundedness condition for the
Radon-Nikodym derivative (e.g. in the case of Poisson boundaries).\n
LOCATION:https://stable.researchseminars.org/talk/WCS/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabor Kun (Budapest)
DTSTART:20210604T130000Z
DTEND:20210604T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/28
DESCRIPTION:Title: Graphings without measurable perfect matchings\nby Gabor Kun (Buda
pest) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nMeasurable m
atchings of graphings (this is\, probability measure preserving Borel grap
hs) have attracted a great deal of attention in the last decades. The Bana
ch-Tarski paradox shows that the Hall condition does not guarantee the exi
stence of a measurable perfect matching in a bipartite graphing. Laczkovic
h gave an example when the measurable Hall condition is not sufficient eit
her. We discuss the few such counterexamples.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre-Loïc Méliot (Orsay)
DTSTART:20210528T130000Z
DTEND:20210528T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/29
DESCRIPTION:Title: Dependency graphs\, upper bounds on cumulants and singular graphons\nby Pierre-Loïc Méliot (Orsay) as part of Warwick Combinatorics Semina
r\n\n\nAbstract\nConsider a sum of random variables $S = \\sum_{v \\in V}
A_v$. If the variables $A_v$ are weakly dependent\, then it is well known
that under mild assumptions\, the distribution of $S$ is close to a normal
distribution. The theory of dependency graphs enables one to make this st
atement precise. In this framework\, we shall present new bounds on the cu
mulants of $S$\, which enable one to have a combinatorial approach of this
probabilistic results. One of the main application is the study of the fl
uctuations of the densities of subgraphs in a random graph chosen accordin
g to a graphon model. We shall see that two behavior are possible\, accord
ing to whether the graphon is generic or singular. In the latter case\, th
e limiting distributions that appear are non-Gaussian.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vishesh Jain (Stanford)
DTSTART:20210618T130000Z
DTEND:20210618T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/30
DESCRIPTION:Title: Towards the sampling Lovász Local Lemma\nby Vishesh Jain (Stanfor
d) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nFor a constrain
t satisfaction problem which satisfies the condition of the Lovász local
lemma (LLL)\, the celebrated algorithm of Moser and Tardos allows one to e
fficiently find a satisfying assignment. In the past few years\, much work
has gone into understanding whether one can efficiently sample from (appr
oximately) the uniform distribution on satisfying assignments under LLL-li
ke conditions. I will discuss recent progress on this problem\, joint with
Huy Tuan Pham (Stanford) and Thuy Duong Vuong (Stanford).\n
LOCATION:https://stable.researchseminars.org/talk/WCS/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tom Kelly (Birmingham)
DTSTART:20210625T130000Z
DTEND:20210625T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/31
DESCRIPTION:Title: A proof of the Erdős–Faber–Lovász conjecture\nby Tom Kelly (
Birmingham) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe Er
dős–Faber–Lovász conjecture (posed in 1972) states that the chromati
c index of any linear hypergraph on $n$ vertices is at most $n$. In joint
work with Dong Yeap Kang\, Daniela Kühn\, Abhishek Methuku\, and Deryk Os
thus\, we proved this conjecture for every sufficiently large $n$. In this
talk\, I will present the history of this conjecture and sketch our proof
in some special cases.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicholas Cook (Duke)
DTSTART:20210611T130000Z
DTEND:20210611T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/32
DESCRIPTION:Title: Regularity method and large deviation principles for the Erdős–Rén
yi hypergraph\nby Nicholas Cook (Duke) as part of Warwick Combinatoric
s Seminar\n\n\nAbstract\nIn recent years there has been intense activity o
n the problem of estimating the upper tail for counts of a fixed subgraph
in a sparse Erdős–Rényi graph\, combining tools and perspectives from
diverse areas such as extremal graph theory\, statistical physics\, stocha
stic analysis and spectral theory. I will discuss some recent extensions o
f these results to the hypergraph setting. Our approach rests on new decom
position theorems and counting lemmas for sparse Bernoulli tensors\, exten
ding classic results from the regularity method for dense graphs. These re
sults are formulated in terms of a new class of cut-type norms specially t
ailored for the sparse setting. Based on joint work with Amir Dembo and Hu
y Tuan Pham.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (Chicago)
DTSTART:20210702T130000Z
DTEND:20210702T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/33
DESCRIPTION:Title: Polymer models\, cluster expansion\, and local limit theorems: countin
g independent sets in the hypercube\nby Will Perkins (Chicago) as part
of Warwick Combinatorics Seminar\n\n\nAbstract\nI'll discuss how local ce
ntral limit theorems can be used in combination with two tools from statis
tical physics\, polymer models and the cluster expansion\, to asymptotical
ly enumerate independent sets of a given size in the hypercube. Joint work
with Matthew Jenssen and Aditya Potukuchi (arxiv:2106.09709)\n
LOCATION:https://stable.researchseminars.org/talk/WCS/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Allan Sly (Princeton)
DTSTART:20211006T130000Z
DTEND:20211006T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/34
DESCRIPTION:Title: Factor of IID for the Ising model on the tree\nby Allan Sly (Princ
eton) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIt's known t
hat there are factors of IID for the free Ising model on the $d$-regular t
ree when it has a unique Gibbs measure and not when reconstruction holds (
when it is not extremal). We construct a factor of IID for the free Ising
model on the $d$-regular tree in (part of) its intermediate regime\, wher
e there is non-uniqueness but still extremality. The construction is via t
he limit of a system of \nstochastic differential equations.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Henry Towsner (Pennsylvania)
DTSTART:20211020T130000Z
DTEND:20211020T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/35
DESCRIPTION:Title: Regularity Lemmas as Structured Decompositions\nby Henry Towsner (
Pennsylvania) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nOne
way of viewing Szemerédi's regularity lemma is that it gives a way of dec
omposing a graph (approximately) into a structured part (the "unary" data)
and a random part. Then hypergraph regularity\, the generalization to k-u
niform hypergraphs\, can be viewed as a decomposition into multiple "tiers
" of structure - a unary part as well as a binary part and so on\, and the
n finally a random part.\n\nWe'll discuss how an analytic approach can mak
e these decompositions exact instances of the conditional expectation in p
robability\, and how these analytic proofs relate to combinatorial proofs
with explicit bounds. Finally\, we'll discuss regularity lemmas for other
mathematical objects\, focusing on the example of ordered graphs and hyper
graphs\, and show how the "tiers of structures" perspective makes it possi
ble to see regularity lemmas for other mathematical objects as examples of
the regularity lemma for hypergraphs.\n\n(No prior knowledge of the regul
arity lemma and its variants is assumed.)\n
LOCATION:https://stable.researchseminars.org/talk/WCS/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rob Silversmith (Warwick)
DTSTART:20211027T130000Z
DTEND:20211027T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/36
DESCRIPTION:Title: Cross-ratios and perfect matchings\nby Rob Silversmith (Warwick) a
s part of Warwick Combinatorics Seminar\n\n\nAbstract\nI’ll describe a s
imple process from algebraic geometry that takes in a collection of $4$-el
ement subsets $S_1\,S_2\,…\,S_{n-3}$ of $[n]$\, and outputs a nonnegativ
e integer called a cross-ratio degree. I’ll discuss several interpretati
ons of cross-ratio degrees in algebra\, algebraic geometry\, and tropical
geometry\, and present a combinatorial algorithm for computing them\, due
to C. Goldner. I’ll then present a perhaps-surprising upper bound for cr
oss-ratio degrees in terms of matchings.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Łukasz Grabowski (Lancaster)
DTSTART:20211110T140000Z
DTEND:20211110T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/37
DESCRIPTION:Title: Directed analogues of expander graphs and random compact subsets of $\
\mathbb{R}^n$\nby Łukasz Grabowski (Lancaster) as part of Warwick Com
binatorics Seminar\n\n\nAbstract\nI will talk about two separate projects.
The first one is a joint work with Endre Csoka (published in "Combinatori
cs\, Probability and Computing")\, where we construct "extender" graphs -
sparse directed graphs with the property that it is impossible to remove a
small amount of edges and obtain a graph which does not have long directe
d paths (long is $|V|^\\delta$\, where $\\delta>0$ is an absolute constant
). Extenders are a directed analogue of expander graphs\, since the latter
ones are characterised by the property that it is impossible to remove a
small amount of edges and obtain graphs which have small connected compone
nts. I'll discuss some conjectures in circuit complexity which motivated u
s to introduce extenders.\n\nThe second project is a joint work with Tomas
z Ciesla (preprint available on arxiv). We construct compacts subsets of $
\\mathbb{R}^2$ which are not "domains of expansion"\, which answers a ques
tion about spectral properties of group actions\, raised by Adrian Ioana.\
n\nApart from the general theme of "expansion"\, both projects are related
by the method which is used to construct suitable examples - in both case
s the construction is probablistic\, and the required properties follow fr
om entropy estimates.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natasha Morrison (Victoria)
DTSTART:20211117T160000Z
DTEND:20211117T170000Z
DTSTAMP:20260404T094310Z
UID:WCS/38
DESCRIPTION:Title: Uncommon systems of equations\nby Natasha Morrison (Victoria) as p
art of Warwick Combinatorics Seminar\n\n\nAbstract\nA system of linear equ
ations $L$ over $\\mathbb{F}_q$ is common if the number of monochromatic s
olutions to $L$ in any two-colouring of $\\mathbb{F}_q^n$ is asymptoticall
y at least the expected number of monochromatic solutions in a random two-
colouring of $\\mathbb{F}_q^n$. Motivated by existing results for specific
systems (such as Schur triples and arithmetic progressions)\, as well as
extensive research on common and Sidorenko graphs\, the systematic study o
f common systems of linear equations was recently initiated by Saad and Wo
lf. Building on earlier work of of Cameron\, Cilleruelo and Serra\, as wel
l as Saad and Wolf\, common linear equations have been fully characterised
by Fox\, Pham and Zhao.\n\nIn this talk I will discuss some recent progre
ss towards a characterisation of common systems of two or more equations.
In particular we prove that any system containing an arithmetic progressio
n of length four is uncommon\, confirming a conjecture of Saad and Wolf. T
his follows from a more general result which allows us to deduce the uncom
monness of a general system from certain properties of one- or two-equatio
n subsystems.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martin Winter (Warwick)
DTSTART:20211201T140000Z
DTEND:20211201T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/39
DESCRIPTION:Title: Some modern open problems on polytopes with symmetries and regularitie
s\nby Martin Winter (Warwick) as part of Warwick Combinatorics Seminar
\n\n\nAbstract\nPolytope theory has itself established as a modern field o
f mathematics with deep connections to geometry\, combinatorics\, and alge
bra. Convex polytopes with many symmetries and regularities however have t
hereby played only a secondary role and are often considered as a fascinat
ing\, yet esoteric subject of the past. In this talk I want to rectify thi
s by presenting up to three modern open problems that connect the study of
such polytopes to representation theory\, hyperplane arrangements and Wey
l groupoids\, as well as spectral graph theory. More specifically\, the th
ree topics are the possible symmetries of orbit polytopes\, inscribed and
simple zonotopes\, and the reconstruction of polytopes from graphs via spe
ctral graph theory.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joseph Hyde (Warwick)
DTSTART:20211103T140000Z
DTEND:20211103T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/40
DESCRIPTION:Title: Progress on the Kohayakawa-Kreuter conjecture\nby Joseph Hyde (War
wick) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nLet $H_1\, .
..\, H_r$ be graphs. We write $G(n\,p) \\to (H_1\, ...\, H_r)$ to denote t
he property that whenever we colour the edges of $G(n\,p)$ with colours fr
om the set $[r] := \\{1\, ...\, r\\}$ there exists some $1 \\le i \\le r$
and a copy of $H_i$ in $G(n\,p)$ monochromatic in colour $i$.\n\nThere has
been much interest in determining the asymptotic threshold function for t
his property. Rödl and Ruciński (1995) determined the threshold function
for the general symmetric case\; that is\, when $H_1 = ... = H_r$. A conj
ecture of Kohayakawa and Kreuter (1997)\, if true\, would effectively reso
lve the asymmetric problem. Recently\, the $1$-statement of this conjectur
e was confirmed by Mousset\, Nenadov and Samotij (2021+). The $0$-statemen
t however has only been proved for pairs of cycles\, pairs of cliques and
pairs of a clique and a cycle.\n\nIn this talk we introduce a reduction of
the $0$-statement of Kohayakawa and Kreuter's conjecture to a certain det
erministic\, natural subproblem. To demonstrate the potential of this appr
oach\, we show this subproblem can be resolved for almost all pairs of reg
ular graphs (satisfying properties one can assume when proving the $0$-sta
tement).\n
LOCATION:https://stable.researchseminars.org/talk/WCS/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Carla Groenland (Utrecht)
DTSTART:20211124T140000Z
DTEND:20211124T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/41
DESCRIPTION:Title: Asymptotic dimension of graph classes\nby Carla Groenland (Utrecht
) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe notion of as
ymptotic dimension of graph classes is borrowed from an invariant of metri
c spaces introduced by Gromov in the context of geometric group theory. In
the talk\, I will try to give some intuition for the definition and our p
roof techniques. Our main result is that each minor-closed family of graph
s has asymptotic dimension at most $2$. I will also mention some corollari
es to clustered colouring and CS notions such as weak sparse partition sch
emes and weak diameter network decompositions. A special case of our main
result also implies that complete Riemannian surfaces have asymptotic dime
nsion (even Assouad-Nagata dimension) at most $2$ (which was previously un
known).\n\n \nThis is based on joint work with M. Bonamy\, N. Bousquet\, L
. Esperet\, C.-H. Liu\, F. Pirot and A. Scott.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:George Kontogeorgiou (Warwick)
DTSTART:20211208T140000Z
DTEND:20211208T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/42
DESCRIPTION:Title: Equivariant Cayley Complex Embeddings\nby George Kontogeorgiou (Wa
rwick) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIn recent y
ears\, a lot of progress has been made in high-dimensional combinatorics\,
i.e. extending concepts from graph theory to higher dimensional CW-comple
xes. Two such concepts of particular interest are (i) group actions and (i
i) embeddings. In this talk we will prove that every finite group which ad
mits a faithful topological action over $\\mathbb{S}^3$ has a generalised
Cayley complex which embeds equivariantly in $\\mathbb{S}^3$. In the proce
ss\, we will see some recent theorems and lemmas concerning $2$-complex em
beddings and group actions over $2$-complexes\, and we will derive a new c
ombinatorial characterization of finite groups acting faithfully and topol
ogically over $\\mathbb{S}^3$.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yinon Spinka (UBC)
DTSTART:20220112T160000Z
DTEND:20220112T170000Z
DTSTAMP:20260404T094310Z
UID:WCS/43
DESCRIPTION:Title: A tale of two balloons\nby Yinon Spinka (UBC) as part of Warwick C
ombinatorics Seminar\n\n\nAbstract\nFrom each point of a Poisson point pro
cess start growing a balloon at rate $1$. When two balloons touch\, they p
op and disappear. Will balloons reach the origin infinitely often or not?
We answer this question for various underlying spaces. En route we find a
new(ish) $0$-$1$ law\, and generalize bounds on independent sets that are
factors of IID on trees.\nJoint work with Omer Angel and Gourab Ray.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jane Gao (Waterloo)
DTSTART:20220119T140000Z
DTEND:20220119T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/44
DESCRIPTION:Title: Perfect matchings and sandwich conjectures of random regular graphs\nby Jane Gao (Waterloo) as part of Warwick Combinatorics Seminar\n\n\nAb
stract\nIn the first half of the talk I will survey results on the limitin
g distributions of small and large subgraphs of random regular graphs\, an
d present a recent result on the limiting distribution of the number of pe
rfect matchings. In the second half of the talk\, I will talk about the Ki
m-Vu sandwich conjecture of random regular graphs\, recent progress\, and
new results.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andy Zucker (San Diego)
DTSTART:20220126T160000Z
DTEND:20220126T170000Z
DTSTAMP:20260404T094310Z
UID:WCS/45
DESCRIPTION:Title: Big Ramsey degrees in binary free amalgamation classes\nby Andy Zu
cker (San Diego) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nI
n structural Ramsey theory\, one considers a "small" structure $A$\, a "me
dium" structure $B$\, a "large" structure $C$ and a number $r$\, then cons
iders the following combinatorial question: given a coloring of the copies
of $A$ inside $C$ in $r$ colors\, can we find a copy of $B$ inside $C$ al
l of whose copies of $A$ receive just one color? For example\, when $C$ is
the rational linear order and $A$ and $B$ are finite linear orders\, then
this follows from the finite version of the classical Ramsey theorem. Mor
e generally\, when $C$ is the Fraisse limit of a free amalgamation class i
n a finite relational language\, then for any finite $A$ and $B$ in the gi
ven class\, this can be done by a celebrated theorem of Nesetril and Rodl.
Things get much more interesting when both $B$ and $C$ are infinite. For
example\, when $B$ and $C$ are the rational linear order and $A$ is the tw
o-element linear order\, a pathological coloring due to Sierpinski shows t
hat this cannot be done. However\, if we weaken our demands and only ask f
or a copy of $B$ inside $C$ whose copies of $A$ receive "few" colors\, rat
her than just one color\, we can succeed. For the two-element linear order
\, we can get down to two colors. For the three-element order\, $16$ color
s. This number of colors is called the big Ramsey degree of a finite struc
ture in a Fraisse class. Recently\, building on groundbreaking work of Dob
rinen\, I proved a generalization of the Nesetril-Rodl theorem to binary f
ree amalgamation classes defined by a finite forbidden set of irreducible
structures (for instance\, the class of triangle-free graphs)\, showing th
at every structure in every such class has a finite big Ramsey degree. My
work only bounded the big Ramsey degrees\, and left open what the exact va
lues were. In recent joint work with Balko\, Chodounsky\, Dobrinen\, Hubic
ka\, Konecny\, and Vena\, we characterize the exact big Ramsey degree of e
very structure in every binary free amalgamation class defined by a finite
forbidden set.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michelle Delcourt (Ryerson)
DTSTART:20220202T140000Z
DTEND:20220202T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/46
DESCRIPTION:Title: Recent Progress on Hadwiger's Conjecture\nby Michelle Delcourt (Ry
erson) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIn 1943\, H
adwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colora
ble for every $t \\ge 1.$ In a recent breakthrough\, Norin\, Song\, and Po
stle proved that every graph with no $K_t$ minor is $O(t (\\log t)^c)$-col
orable for every $c > 0.25$\, Subsequently Postle showed that every graph
with no $K_t$ minor is $O(t (\\log \\log t)^6)$-colorable. We improve up
on this further showing that every graph with no $K_t$ minor is $O(t \\log
\\log t)$-colorable. Our main technical result yields this as well as a n
umber of other interesting corollaries. A natural weakening of Hadwiger's
Conjecture is the so-called Linear Hadwiger's Conjecture that every graph
with no $K_t$ minor is $O(t)$-colorable. We prove that Linear Hadwiger's
Conjecture reduces to small graphs as well as that Linear Hadwiger's Conje
cture holds for the class of $K_r$-free graphs (provided $t$ is sufficient
ly large). This is joint work with Luke Postle.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rachel Greenfeld (UCLA)
DTSTART:20220209T160000Z
DTEND:20220209T170000Z
DTSTAMP:20260404T094310Z
UID:WCS/47
DESCRIPTION:Title: Decidability and periodicity of translational tilings\nby Rachel G
reenfeld (UCLA) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nTr
anslational tiling is a covering of a space using translated copies of som
e building blocks\, called the “tiles”\, without any positive measure
overlaps. Which are the possible ways that a space can be tiled? In the
talk\, we will discuss the study of this question as well as its applicati
ons\, and report on recent progress\, joint with Terence Tao.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Victor Chepoi (Marseille)
DTSTART:20220316T160000Z
DTEND:20220316T170000Z
DTSTAMP:20260404T094310Z
UID:WCS/48
DESCRIPTION:Title: Labeled sample compression schemes for complexes of oriented matroids<
/a>\nby Victor Chepoi (Marseille) as part of Warwick Combinatorics Seminar
\n\n\nAbstract\nThe sample compression schemes were introduced by Littlest
one\nand Warmuth in 1986 and have been\nvastly studied in the literature d
ue to their importance in Machine\nLearning. Roughly speaking\, the goal\n
is to compress data as much as possible such that the original data can\nb
e reconstructed\nfrom the compressed data. The Vapnik-Chervonenkis dimens
ion is central\nin Machine Learning and is\nimportant in Combinatorics an
d Discrete Geometry. Floyd and Warmuth in\n1995 asked whether any set-fami
ly\nof VC-dimension $d$ has a sample compression scheme of size $O(d)$. Th
is\nremains one of the oldest open problems\nin Machine Learning.\n\nRecen
tly we showed that the topes of a complex of oriented matroids\n(abbreviat
ed COM) of VC-dimension $d$ admit a proper labeled\nsample compression sch
eme of size $d$. This considerably extends results\nof Moran and Warmuth a
nd the authors and is a step\ntowards the sample compression conjecture. O
n the one hand\, our approach\nexploits the rich combinatorial cell struct
ure of COMs\nvia oriented matroid theory. On the other hand viewing tope g
raphs of\nCOMs as partial cubes creates a fruitful link to metric graph th
eory.\n\nIn the talk\, we will expalain COMs and the labeled sample compre
ssion\nscheme for them.\n\nBased on the paper:\nV. Chepoi\, K. Knauer\, M.
Philibert\, Labeled sample compression schemes\nfor complexes of oriented
matroids\, arXiv:2110.15168\, 2021.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stijn Cambie (Warwick)
DTSTART:20220223T140000Z
DTEND:20220223T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/49
DESCRIPTION:Title: Packing list-colourings\nby Stijn Cambie (Warwick) as part of Warw
ick Combinatorics Seminar\n\n\nAbstract\nList colouring is an influential
and classic topic in graph theory\, which is related to e.g. frequency ass
ignment\, resource allocation and scheduling problems. Sometimes it is nat
ural to consider multiple of these and the best one can aim for is a packi
ng of disjoint solutions/ list colourings. We investigate this natural str
engthening\, the list packing problem.\nThis study was already suggested 2
5 years ago by Alon\, Fellows and Hare. In this talk\, we sketch the (conj
ectured) behaviour of this parameter and a related one under certain bound
ed degree conditions.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mikolaj Fraczyk (Chicago)
DTSTART:20220302T160000Z
DTEND:20220302T170000Z
DTSTAMP:20260404T094310Z
UID:WCS/50
DESCRIPTION:Title: Stationary random graphs and groups\nby Mikolaj Fraczyk (Chicago)
as part of Warwick Combinatorics Seminar\n\n\nAbstract\nA stationary rando
m graph is a random rooted graphs $(G\,o)$ such that replacing the root $o
$ by its random neighbor results in the same probability distribution. The
more well known unimodular random graphs are always stationary\, but the
unimodularity assumption is in fact much stronger. Invariant random subgro
ups and unimodular random graphs are now a household name in measured grou
p theory\, and they found several applications in geometry and topology. I
n my talk I want to advertise and describe some applications of the statio
nary random graphs and groups. I will explain how they can be used to find
non-expander sub-graphs inside any given graph and how to prove that any
higher rank locally symmetric space of infinite volume must have points of
arbitrary large injectivity radius. The talk is based on a joint work wit
h Wouter Van Limbeek and with Tsachik Gelander.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ján Špakula (Southampton)
DTSTART:20220309T140000Z
DTEND:20220309T150000Z
DTSTAMP:20260404T094310Z
UID:WCS/51
DESCRIPTION:Title: On measured expanders\nby Ján Špakula (Southampton) as part of W
arwick Combinatorics Seminar\n\n\nAbstract\nBy a "measured graph" we simpl
y mean a graph with weights\nassigned to its vertices. The classical isope
rimetric (a.k.a. Cheeger)\nconstant describing connectedness of a graph ge
neralises to this\nsetting\, leading to a notion of a "measured expander":
a sequence of\nfinite graphs with a uniform positive lower bound on this
isoperimetric\nconstant.\nThe talk will walk through a bit of coarse geome
try to a functional\nanalytic question that led us to consider this notion
. Our main result\nis a characterisation of measured expanders through a P
oincare\ninequality\, and thus that they do not coarsely embed into $L^p$-
space. I\nwill also present some examples.\nBased on joint work with K. Li
and J. Zhang.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xizhi Liu (Warwick)
DTSTART:20220427T130000Z
DTEND:20220427T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/52
DESCRIPTION:Title: The feasible region of induced graphs\nby Xizhi Liu (Warwick) as p
art of Warwick Combinatorics Seminar\n\n\nAbstract\nFix a graph $F$. A cla
ssical problem in extremal graph theory asks about how many induced copies
of $F$ can a graph with edge density $\\rho$ have? The only case in which
we know the asymptotic solution is when $F$ is a complete graph\, and it
was solved completely only recently by Reiher using the flag algebra machi
nery. We will consider the other cases and show some results when $F$ is a
complete bipartite graph or a complete graph minus one edge. Many interes
ting related open problems will also be introduced. Joint work with Dhruv
Mubayi and Christian Reiher.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alistair Benford (Birmingham)
DTSTART:20220504T130000Z
DTEND:20220504T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/53
DESCRIPTION:Title: Trees in tournaments\nby Alistair Benford (Birmingham) as part of
Warwick Combinatorics Seminar\n\n\nAbstract\nGiven an $n$-vertex oriented
tree $T$\, what is the smallest size a tournament $G$ must be\, in order t
o guarantee $G$ contains a copy of $T$? A strengthening of Sumner’s conj
ecture poses that it is enough for $G$ to have $(n+k-1)$ vertices\, where
$k$ is the number of leaves of $T$. In this talk we will look at recent pr
ogress towards this conjecture. We shall also consider how this problem ca
n be addressed by instead considering the maximum degree of the tree\, rat
her than the number of leaves\, and state some open problems in this maxim
um degree setting. This is joint work with Richard Montgomery.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Péter Pál Pach (Budapest)
DTSTART:20220511T130000Z
DTEND:20220511T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/54
DESCRIPTION:Title: The Alon-Jaeger-Tarsi conjecture via group ring identities\nby Pé
ter Pál Pach (Budapest) as part of Warwick Combinatorics Seminar\n\n\nAbs
tract\nThe Alon-Jaeger-Tarsi conjecture states that for any finite field $
F$ of size at least 4 and any nonsingular matrix $M$ over $F$ there exis
ts a vector $x$ such that neither $x$ nor $Mx$ has a 0 component. In joint
work with János Nagy we proved this conjecture when the size of the fiel
d is sufficiently large\, namely\, when $61<|F|\\ne 79$. In this talk we w
ill discuss this result.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Richard Montgomery (Warwick)
DTSTART:20220525T130000Z
DTEND:20220525T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/55
DESCRIPTION:Title: On the Ryser-Brualdi-Stein conjecture\nby Richard Montgomery (Warw
ick) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe Ryser-Bru
aldi-Stein conjecture states that every Latin square of order $n$ should h
ave a partial transversal with $n-1$ elements\, and a full transversal if
$n$ is odd. In 2020\, Keevash\, Pokrovskiy\, Sudakov and Yepremyan improve
d the long-standing best known bounds on this conjecture by showing that a
partial transversal with $n-O(\\log n/\\log\\log n)$ elements always exis
ts. I will discuss how to show\, for large $n$\, that a partial transversa
l with $n-1$ elements always exists.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gal Kronenberg (Oxford)
DTSTART:20220615T130000Z
DTEND:20220615T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/56
DESCRIPTION:Title: Independent sets in random subgraphs of the hypercube\nby Gal Kron
enberg (Oxford) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIn
dependent sets in bipartite regular graphs have been studied extensively i
n combinatorics\, probability\, computer science and more. The problem of
counting independent sets is particularly interesting in the $d$-dimension
al hypercube $\\{0\,1\\}^d$\, motivated by the lattice gas hardcore model
from statistical physics. Independent sets also turn out to be very intere
sting in the context of random graphs.\n\nThe number of independent sets i
n the hypercube $\\{0\,1\\}^d$ was estimated precisely by Korshunov and Sa
pozhenko in the 1980s and recently refined by Jenssen and Perkins.\n\nIn t
his talk we will discuss new results on the number of independent sets in
a random subgraph of the hypercube. The results extend to the hardcore mod
el and rely on an analysis of the antiferromagnetic Ising model on the hyp
ercube.\n\nThis talk is based on joint work with Yinon Spinka.\n
LOCATION:https://stable.researchseminars.org/talk/WCS/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miek Messerschmidt (Pretoria)
DTSTART:20220622T130000Z
DTEND:20220622T140000Z
DTSTAMP:20260404T094310Z
UID:WCS/57
DESCRIPTION:Title: Compact packings of the plane with discs\nby Miek Messerschmidt (P
retoria) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nAfter exp
laining what a compact packing of the plane by discs is\, I will discuss t
he following question: "For which $n$-tuples of distinct positive real num
bers is there a compact packing of the plane with discs\, so that\, firstl
y\, only the mentioned $n$ numbers are used as radii of discs in the packi
ng\, and secondly\, every one of the mentioned $n$ numbers occurs at least
once as a radius of a disc in the packing?"\n\nI will discuss some aspect
s of this question along with its history\, which is surprisingly recent (
e.g.\, the case $n=2$ was only solved in 2006).\n
LOCATION:https://stable.researchseminars.org/talk/WCS/57/
END:VEVENT
END:VCALENDAR