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:20260422T212557Z
UID:WCS/1
DESCRIPTION:Title: Stru
ctures of sets with minimal measure growth\nby Yifan Jing (UIUC) as pa
rt of Warwick Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/WCS/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yahav Alon (Tel Aviv)
DTSTART:20200610T130000Z
DTEND:20200610T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/2
DESCRIPTION:Title: Hitt
ing time of disjoint Hamilton cycles in random subgraph processes\nby
Yahav Alon (Tel Aviv) as part of Warwick Combinatorics Seminar\n\nAbstract
: TBA\n
LOCATION:https://researchseminars.org/talk/WCS/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andrzej Grzesik (Jagiellonian)
DTSTART:20200617T130000Z
DTEND:20200617T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/3
DESCRIPTION:Title: The
Turán number of blow-ups of trees\nby Andrzej Grzesik (Jagiellonian)
as part of Warwick Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/WCS/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bjarne Schülke (Hamburg)
DTSTART:20200624T130000Z
DTEND:20200624T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/4
DESCRIPTION:Title: Extr
emal problems concerning the traces of sets\nby Bjarne Schülke (Hambu
rg) as part of Warwick Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/WCS/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:László Lovász (Budapest)
DTSTART:20201009T130000Z
DTEND:20201009T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/5
DESCRIPTION:Title: Grap
h limits\, measures\, and flows\nby László Lovász (Budapest) as par
t of Warwick Combinatorics Seminar\n\n\nAbstract\nThe theory of graph limi
ts is only understood to a somewhat\nsatisfactory degree in the cases of d
ense graphs and of bounded degree\ngraphs. There is\, however\, a lot of i
nterest in the intermediate cases.\nIt appears that the most important con
stituents of graph limits in the\ngeneral case will be Markov spaces (Mark
ov chains on measurable spaces\nwith a stationary distribution).\n\nThis m
otivates our goal to extend some important theorems from finite\ngraphs to
Markov spaces or\, more generally\, to measurable spaces. In\nthis talk w
e show that much of flow theory\, one of the most important\nareas in grap
h theory\, can be extended to measurable spaces. In\nparticular\, the Hoff
man Circulation Theorem\, the Max-Flow-Min-Cut\nTheorem\, Multicommodity F
low Theorem\, and several other results have\nsimple and elegant extension
s to measures.\n
LOCATION:https://researchseminars.org/talk/WCS/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marthe Bonamy (Bordeaux)
DTSTART:20201016T130000Z
DTEND:20201016T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/6
DESCRIPTION:Title: Grap
h recolouring\nby Marthe Bonamy (Bordeaux) as part of Warwick Combinat
orics Seminar\n\n\nAbstract\nGiven a solution to a problem\, we can try an
d apply a series of elementary operations to it\, making sure to remain in
the solution space at every step. What kind of solutions can we reach thi
s way? How fast? This is motivated by a variety of applications\, from sta
tistical physics to real-life scenarios\, including enumeration and sampli
ng. In this talk\, we will discuss various positive and negative results\,
in the special case of graph colouring.\n
LOCATION:https://researchseminars.org/talk/WCS/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gábor Tardos (Budapest)
DTSTART:20201023T130000Z
DTEND:20201023T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/7
DESCRIPTION:Title: Conv
ergence and limits of finite trees\nby Gábor Tardos (Budapest) as par
t of Warwick Combinatorics Seminar\n\n\nAbstract\nSeeing the success of li
mit theory of dense finite graphs with graphons as their limit objects we
developed a similar (?) theory for finite trees. In order for the sampling
limit to make sense we need to make the trees "dense" - we do this by con
sidering them as metric spaces with the normalized graph distance. Using u
ltaproducts is a simple and elegant way to find unique limit objects (we c
all them dendrons) and also to highlight similarities and major difference
s from the theory of dense graph limits. For the underlying quantitative a
pproximation results\, one needs more "down to earth" techniques to be dev
eloped.\nThis is joint work with Gábor Elek.\n
LOCATION:https://researchseminars.org/talk/WCS/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Maria Chudnovsky (Princeton)
DTSTART:20201030T140000Z
DTEND:20201030T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/8
DESCRIPTION:Title: Even
-hole free graphs of bounded degree have bounded treewidth\nby Maria C
hudnovsky (Princeton) as part of Warwick Combinatorics Seminar\n\n\nAbstra
ct\nTree decompositions are a powerful tool in structural graph theory tha
t is traditionally used in the context of forbidden graph minors. Connect
ing tree decompositions and forbidden induced subgraphs has so far largely
remained out of reach. Traditionally to bound the treewidth of a graph\,
one finds a way to decompose it by a so-called laminar collection of\ndeco
mpositions. Recently\, in joint work with Tara Abrishami and Kristina \nV
uskovic\, we proved that even-hole free graphs of bounded degree have bou
nded tree-width. To do so we used "star cutset separations" that arise nat
urally in the context of even-hole-free graphs. While the set of star cuts
et separations is far from being non-crossing\, it turns out that one can
partition it into a bounded number of laminar collections\, and this is su
fficient for our purposes.\nIn this talk we will present an outline of the
proof.\n
LOCATION:https://researchseminars.org/talk/WCS/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Boris Bukh (Pittsburgh)
DTSTART:20201106T140000Z
DTEND:20201106T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/9
DESCRIPTION:Title: Empt
y axis-parallel boxes\nby Boris Bukh (Pittsburgh) as part of Warwick C
ombinatorics Seminar\n\n\nAbstract\nHow to place n points inside the d-dim
ensional unit cube so every large axis-parallel box contains at least one
point? We discuss the motivation as well as a partial solution to this pro
blem. This is a joint work with Ting-Wei Chao.\n
LOCATION:https://researchseminars.org/talk/WCS/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tibor Szabó (Berlin)
DTSTART:20201113T140000Z
DTEND:20201113T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/10
DESCRIPTION:Title: Mad
er-perfect digraphs\nby Tibor Szabó (Berlin) as part of Warwick Combi
natorics Seminar\n\n\nAbstract\nWe investigate the relationship of dichrom
atic number and subdivision containment in digraphs. We call a digraph Mad
er-perfect if for every (induced) subdigraph $F$\, any digraph of dichroma
tic number at least $v(F)$ contains an $F$-subdivision. We show that\, amo
ng others\, arbitrary orientated cycles\, bioriented trees\, and tournamen
ts on four vertices are Mader-perfect. The first result settles a conjectu
re of Aboulker\, Cohen\, Havet\, Lochet\, Moura\, and Thomasse\, while the
last one extends Dirac's Theorem about $4$-chromatic graphs containing a
$K_4$-subdivision to directed graphs. The talk represents joint work with
Lior Gishboliner and Raphael Steiner.\n
LOCATION:https://researchseminars.org/talk/WCS/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benny Sudakov (Zurich)
DTSTART:20201120T140000Z
DTEND:20201120T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/11
DESCRIPTION:Title: Lar
ge independent sets from local considerations\nby Benny Sudakov (Zuric
h) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nHow well can gl
obal properties of a graph be inferred from observations that are purely l
ocal? This general question gives rise to numerous interesting problems. O
ne such very natural question was raised independently by Erdos-Hajnal and
Linial-Rabinovich in the early 90's. How large must the independence numb
er $\\alpha (G)$ of a graph $G$ be whose every $m$ vertices contain an ind
ependent set of size $r$? In this talk we discuss new methods to attack th
is problem which improve many previous results.\n
LOCATION:https://researchseminars.org/talk/WCS/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Anton Bernshteyn (Georgia Tech)
DTSTART:20201127T140000Z
DTEND:20201127T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/12
DESCRIPTION:Title: Mea
surable colorings\, the Lovász Local Lemma\, and distributed algorithms\nby Anton Bernshteyn (Georgia Tech) as part of Warwick Combinatorics Se
minar\n\n\nAbstract\nIn the past twenty or so years\, a rich theory has em
erged concerning the behavior of graph colorings\, matchings\, and other c
ombinatorial notions under additional regularity requirements\, for instan
ce measurability. It turns out that this area is closely related to distri
buted computing\, i.e.\, the part of computer science concerned with probl
ems that can be solved efficiently by a decentralized network of processor
s. A key role in this relationship is played by the Lovász Local Lemma an
d its analogs in the measurable setting. In this talk I will outline this
relationship and present a number of applications.\n
LOCATION:https://researchseminars.org/talk/WCS/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bhargav Narayanan (Rutgers)
DTSTART:20201204T140000Z
DTEND:20201204T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/13
DESCRIPTION:Title: Hom
eomorphs\nby Bhargav Narayanan (Rutgers) as part of Warwick Combinator
ics Seminar\n\n\nAbstract\nNati Linial asked the following basic problem i
n 2006: Given a $k$-dimensional simplicial complex $S$\, how many facets c
an a $k$-complex on $n$ vertices have if it contains no topological copy o
f $S$? This is a beautiful and natural question\, but results in low dimen
sions apart ($k\\le 2$)\, very little was previously known. In this talk\,
I’ll provide an answer in all dimensions and take the scenic route to t
he answer\, surveying many natural problems about simplicial complexes alo
ng the way.\n
LOCATION:https://researchseminars.org/talk/WCS/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hong Liu (Warwick)
DTSTART:20201211T140000Z
DTEND:20201211T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/14
DESCRIPTION:Title: Ext
remal density for sparse minors and subdivisions\nby Hong Liu (Warwick
) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nHow dense a grap
h 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 res
ult of Kostochka/Thomason for clique minor\, and result of Bollobas-Thomas
on/Komlos-Szemeredi for topological minor. The situation is a lot less cle
ar 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 Wood on
embedding sparse minors. Among others\,\n\n - $(1+o(1))t^2$ average d
egree 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\, surp
risingly\, the value is the same for $t$-vertex graphs embeddable on any f
ixed surface\;\n\n - a universal bound of $(2+o(1))t$ on average degr
ee forcing $every$ $t$-vertex graph in $any$ nontrivial minor-closed famil
y as a minor\, and the constant 2 is best possible by considering graphs w
ith given treewidth.\n\nJoint work with John Haslegrave and Jaehoon Kim.\n
LOCATION:https://researchseminars.org/talk/WCS/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pál Galicza (Budapest)
DTSTART:20210115T140000Z
DTEND:20210115T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/15
DESCRIPTION:Title: Spa
rse reconstruction for iid variables\nby Pál Galicza (Budapest) as pa
rt of Warwick Combinatorics Seminar\n\n\nAbstract\nFor a sequence of Boole
an functions $f_n : \\{-1\,1\\}^{V_n} \\longrightarrow \\{-1\,1\\}$\, defi
ned on increasing configuration spaces of random inputs\, we say that ther
e is sparse reconstruction if there is a sequence of subsets $U_n \\subset
eq V_n$ of the coordinates satisfying $|U_n| = o(|V_n|)$ such that knowin
g the coordinates in $U_n$ gives us a non-vanishing amount of information
about the value of $f_n$.\n\nWe first show that\, if the underlying measur
e is a product measure\, then no sparse reconstruction is possible for any
sequence of transitive functions. We discuss the question in different fr
ameworks\, measuring information content in $L^2$ and with entropy. We als
o highlight some interesting connections with cooperative game theory.\n\n
Using our results for transitive sequences of functions\, we answer a que
stion posed by Itai Benjamini and show that the left-right crossing event
for critical planar percolation on the square lattice does not admit spars
e reconstruction either. Joint work with Gábor Pete.\n
LOCATION:https://researchseminars.org/talk/WCS/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alexander Razborov (Chicago)
DTSTART:20210122T173000Z
DTEND:20210122T183000Z
DTSTAMP:20260422T212557Z
UID:WCS/16
DESCRIPTION:Title: The
ons and quasirandomness\nby Alexander Razborov (Chicago) as part of Wa
rwick Combinatorics Seminar\n\n\nAbstract\nThere are two known approaches
to the theory of limits of discrete combinatorial objects: geometric (grap
h limits) and algebraic (flag algebras). In the first part of the talk we
present a general framework intending to combine useful features of both t
heories and compare it with previous attempts of this kind. Our main objec
ts 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 this frame
work to offer a new perspective on quasi-randomness for combinatorial obje
cts more complicated than ordinary graphs. Our quasi-randomness properties
are natural in the sense that they do not use ad hoc densities and they a
re preserved under the operation of defining combinatorial structures of o
ne kind from structures of a different kind. One key concept in this theor
y is that of unique coupleability roughly meaning that any alignment of tw
o objects on the same ground set should ``look like'' random.\n\nBased on
joint work with Leonardo Coregliano.\n\nNote the unusual time!\n
LOCATION:https://researchseminars.org/talk/WCS/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lisa Sauermann (IAS)
DTSTART:20210129T140000Z
DTEND:20210129T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/17
DESCRIPTION:Title: On
polynomials that vanish to high order on most of the hypercube\nby Lis
a Sauermann (IAS) as part of Warwick Combinatorics Seminar\n\n\nAbstract\n
Motivated by higher vanishing multiplicity generalizations of Alon's Combi
natorial Nullstellensatz and its applications\, we study the following pro
blem: for fixed k and n large with respect to $k$\, what is the minimum po
ssible 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 least $
k$ at all points in $\\{0\,1\\}^n$ except the origin? For $k=1$\, a classi
cal theorem of Alon and Füredi states that the minimum possible degree of
such a polynomial equals $n$. We solve the problem for all $k>1$\, provin
g that the answer is $n+2k−3$. Joint work with Yuval Wigderson.\n
LOCATION:https://researchseminars.org/talk/WCS/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gábor Pete (Budapest)
DTSTART:20210212T140000Z
DTEND:20210212T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/18
DESCRIPTION:Title: The
Free Uniform Spanning Forest is disconnected in some virtually free group
s\, depending on the generating set\nby Gábor Pete (Budapest) as part
of Warwick Combinatorics Seminar\n\n\nAbstract\nThe uniform random spanni
ng tree of a finite graph is a classical object in probability and combina
torics. In an infinite graph\, one can take any exhaustion by finite subgr
aphs\, with some boundary conditions\, and take the limit measure. The Fre
e Uniform Spanning Forest (FUSF) is one of the natural limits\, but it is
less understood than the wired version\, the WUSF. Taking a finitely gener
ated group\, several properties of WUSF and FUSF have been known to be ind
ependent of the chosen Cayley graph of the group: the average degree in WU
SF and in FUSF\; the number of ends in the components of the WUSF and of t
he FUSF\; the number of trees in the WUSF. Lyons and Peres asked if this l
atter should also be the case for the FUSF.\n\nIn joint work with Ádám T
imár\, we give two different Cayley graphs of the same group such that th
e FUSF is connected in one of them but has infinitely many trees in the ot
her. Since our example is a virtually free group\, this is also a countere
xample to the general expectation that such "tree-like" graphs would have
connected FUSF. Many open questions are inspired by the results.\n
LOCATION:https://researchseminars.org/talk/WCS/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Kurkofka (Hamburg)
DTSTART:20210219T140000Z
DTEND:20210219T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/19
DESCRIPTION:Title: Eve
ry infinitely edge-connected graph contains the Farey graph or $T_{\\aleph
_0}*t$ as a minor\nby Jan Kurkofka (Hamburg) as part of Warwick Combin
atorics Seminar\n\n\nAbstract\nThe Farey graph plays a role in a number of
mathematical fields ranging from group theory and number theory to geomet
ry and dynamics. Curiously\, graph theory is not among these. We show that
the Farey graph plays a central role in graph theory too: it is one of tw
o infinitely edge-connected graphs that must occur as a minor in every inf
initely edge-connected graph. Previously it was not known that there was a
ny set of graphs determining infinite edge-connectivity by forming a minor
-minimal list in this way\, let alone a finite set.\n
LOCATION:https://researchseminars.org/talk/WCS/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lutz Warnke (Georgia Tech)
DTSTART:20210226T140000Z
DTEND:20210226T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/20
DESCRIPTION:Title: Pra
gue dimension of random graphs\nby Lutz Warnke (Georgia Tech) as part
of Warwick Combinatorics Seminar\n\n\nAbstract\nThe Prague dimension of gr
aphs was introduced by Nesetril\, Pultr and Rodl in the 1970s: as a combin
atorial measure of complexity\, it is closely related to clique edges cove
rings and partitions. Proving a conjecture of Furedi and Kantor\, we show
that the Prague dimension of the binomial random graph is typically of ord
er n/(log n) for constant edge-probabilities. \nThe main new proof ingredi
ent is a Pippenger-Spencer type edge-coloring result for random hypergraph
s with large uniformities\, i.e.\, edges of size O(log n). \n\nBased on jo
int work with He Guo and Kalen Patton\, see https://arxiv.org/abs/2011.094
59\n
LOCATION:https://researchseminars.org/talk/WCS/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louis Esperet (Grenoble)
DTSTART:20210305T133000Z
DTEND:20210305T143000Z
DTSTAMP:20260422T212557Z
UID:WCS/21
DESCRIPTION:Title: Asy
mptotic dimension of graphs\nby Louis Esperet (Grenoble) as part of Wa
rwick Combinatorics Seminar\n\n\nAbstract\nThe asymptotic dimension of a m
etric space is a notion introduced by Gromov in the 90s\, in connection wi
th geometric group theory. In the special case of the shortest path metric
associated to a graph\, a related notion\, called "weak network decomposi
tion" has been independently considered by theoretical computer scientists
\, with a different motivation. I will also explain some links with the cl
assical notion of graph coloring\, and some variants that have been studie
d since the end of the 90s.\n\nA class of graphs is minor-closed if any gr
aph obtained from a graph in the class by deleting vertices or edges\, 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 proper mi
nor-closed family of graphs has asymptotic dimension at most 2\, which giv
es optimal answers to a question of Fujiwara and Papasoglu and to a proble
m raised by Ostrovskii and Rosenthal on minor excluded groups.\n\nJoint wo
rk with M. Bonamy\, N. Bousquet\, C. Groenland\, C.-H. Liu\, F. Pirot\, an
d A. Scott.\n
LOCATION:https://researchseminars.org/talk/WCS/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Annie Raymond (Massachusetts Amherst)
DTSTART:20210312T140000Z
DTEND:20210312T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/22
DESCRIPTION:Title: Gra
ph Density Inequalities\, Sums of Squares and Tropicalization\nby Anni
e Raymond (Massachusetts Amherst) as part of Warwick Combinatorics Seminar
\n\n\nAbstract\nEstablishing inequalities among graph densities is a centr
al pursuit in extremal graph theory. One way to certify the nonnegativity
of a graph density expression is to write it as a sum of squares or as a r
ational sum of squares. In this talk\, we will explore how one does so and
we will then identify simple conditions under which a graph density expre
ssion cannot be a sum of squares or a rational sum of squares. Tropicaliza
tion will play a key role for the latter\, and will turn out to be an inte
resting object in itself. This is joint work with Greg Blekherman\, Mohit
Singh\, and Rekha Thomas.\n
LOCATION:https://researchseminars.org/talk/WCS/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Spielman (Yale)
DTSTART:20210319T173000Z
DTEND:20210319T183000Z
DTSTAMP:20260422T212557Z
UID:WCS/23
DESCRIPTION:Title: Fin
ite Free Probability and Ramanujan Graphs\nby Daniel Spielman (Yale) a
s part of Warwick Combinatorics Seminar\n\n\nAbstract\nWe introduce a fini
te analog of Voiculescu's Free Probability that allows us to compute the e
xpected characteristic polynomials of certain random matrices and to prove
bounds on the locations of the roots of those polynomials. We sketch how
this theory may be used to prove that there exist bipartite Ramanujan grap
hs of every degree and number of vertices.\n\nNo prior knowledge of free p
robability or Ramanujan graphs will be assumed.\n\nThis is joint work with
Adam Marcus and Nikhil Srivastava.\n
LOCATION:https://researchseminars.org/talk/WCS/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Agnes Backhausz (Budapest)
DTSTART:20210430T130000Z
DTEND:20210430T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/24
DESCRIPTION:Title: Typ
icality and entropy of processes on infinite trees\nby Agnes Backhausz
(Budapest) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nWhen w
e study random $d$-regular graphs from the point of view of graph limit th
eory\, the notion of typical processes arise naturally. These are certain
invariant families of random variables indexed by the infinite regular tre
e. 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 consider
the processes that can be approximated with colorings (labelings) of rando
m $d$-regular graphs. These are the so-called typical processes\, whose pr
operties contain useful information about the structure of finite random r
egular graphs. In earlier works\, various necessary conditions have been g
iven for a process to be typical\, by using correlation decay or entropy i
nequalities. In the work presented in the talk\, we go in the other direct
ion and provide sufficient entropy conditions in the special case of edge
Markov processes. This condition can be extended to unimodular Galton--Wat
son random trees as well. Joint work with Charles Bordenave and Balázs Sz
egedy (https://arxiv.org/abs/2102.02653).\n
LOCATION:https://researchseminars.org/talk/WCS/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwen McKinley (San Diego)
DTSTART:20210507T163000Z
DTEND:20210507T173000Z
DTSTAMP:20260422T212557Z
UID:WCS/25
DESCRIPTION:Title: Cou
nting integer partitions with the method of maximum entropy\nby Gwen M
cKinley (San Diego) as part of Warwick Combinatorics Seminar\n\n\nAbstract
\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 the coun
ting problem as an optimization problem\, and find the probability distrib
ution on the set of all integer partitions with maximum entropy among thos
e that satisfy our restrictions in expectation (in essence\, this is an ap
plication of Jaynes' principle of maximum entropy). This approach leads to
an approximate version of our formula as the solution to a relatively str
aightforward optimization problem over real-valued functions. To establish
more precise asymptotics\, we prove a local central limit theorem using a
n equidistribution result of Green and Tao.\n\nA large portion of the talk
will be devoted to outlining how our method can be used to re-derive a cl
assical result of Hardy and Ramanujan\, with an emphasis on the intuitions
behind the method\, and limited technical detail. This is joint work with
Marcus Michelen and Will Perkins.\n
LOCATION:https://researchseminars.org/talk/WCS/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pascal Schweitzer (Darmstadt)
DTSTART:20210514T130000Z
DTEND:20210514T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/26
DESCRIPTION:Title: Aut
omorphisms of graphs with a forbidden minor\nby Pascal Schweitzer (Dar
mstadt) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nAccording
to Frucht’s classic theorem\, every finite group is the automorphism gro
up of a finite graph (up to isomorphism). We say the class of all graphs i
s universal. Babai proved in 1974 that graph classes with a forbidden mino
r\, such as planar graphs\, graphs of bounded genus\, and graphs of bounde
d tree width\, are not universal. He also made three conjectures regarding
automorphisms of such graphs. I will describe a structure theorem of auto
morphism groups of such graphs\, affirming these conjectures.\n\nThis is j
oint work with Martin Grohe and Daniel Wiebking.\n
LOCATION:https://researchseminars.org/talk/WCS/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabor Elek (Lancaster)
DTSTART:20210521T130000Z
DTEND:20210521T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/27
DESCRIPTION:Title: Uni
form amenability\nby Gabor Elek (Lancaster) as part of Warwick Combina
torics Seminar\n\n\nAbstract\nAccording to the classical result of Connes\
, Feldman and Weiss\, measured hyperfiniteness of a group action is equiva
lent to measured amenability. In the Borel category it is known that hype
rfiniteness implies amenability and it is conjectured that the converse is
true. Based on the work of Anantharaman-Delaroche and Renault\, one can i
ntroduce the notion of uniform amenability\, a strengthening of measured a
menability (it is a sort of exactness in the category of measurable action
s\, so the famous Gromov-Osajda groups have no free uniformly amenable act
ions). One can also introduce the notion of uniform hyperfiniteness in a r
ather natural way. We prove that the two notions are equivalent provided t
hat the measurable action satisfies a boundedness condition for the Radon-
Nikodym derivative (e.g. in the case of Poisson boundaries).\n
LOCATION:https://researchseminars.org/talk/WCS/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gabor Kun (Budapest)
DTSTART:20210604T130000Z
DTEND:20210604T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/28
DESCRIPTION:Title: Gra
phings without measurable perfect matchings\nby Gabor Kun (Budapest) a
s part of Warwick Combinatorics Seminar\n\n\nAbstract\nMeasurable matching
s of graphings (this is\, probability measure preserving Borel graphs) hav
e attracted a great deal of attention in the last decades. The Banach-Tars
ki paradox shows that the Hall condition does not guarantee the existence
of a measurable perfect matching in a bipartite graphing. Laczkovich gave
an example when the measurable Hall condition is not sufficient either. We
discuss the few such counterexamples.\n
LOCATION:https://researchseminars.org/talk/WCS/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pierre-Loïc Méliot (Orsay)
DTSTART:20210528T130000Z
DTEND:20210528T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/29
DESCRIPTION:Title: Dep
endency graphs\, upper bounds on cumulants and singular graphons\nby P
ierre-Loïc Méliot (Orsay) as part of Warwick Combinatorics Seminar\n\n\n
Abstract\nConsider a sum of random variables $S = \\sum_{v \\in V} A_v$. I
f the variables $A_v$ are weakly dependent\, then it is well known that un
der mild assumptions\, the distribution of $S$ is close to a normal distri
bution. The theory of dependency graphs enables one to make this statement
precise. In this framework\, we shall present new bounds on the cumulants
of $S$\, which enable one to have a combinatorial approach of this probab
ilistic results. One of the main application is the study of the fluctuati
ons of the densities of subgraphs in a random graph chosen according to a
graphon model. We shall see that two behavior are possible\, according to
whether the graphon is generic or singular. In the latter case\, the limit
ing distributions that appear are non-Gaussian.\n
LOCATION:https://researchseminars.org/talk/WCS/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vishesh Jain (Stanford)
DTSTART:20210618T130000Z
DTEND:20210618T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/30
DESCRIPTION:Title: Tow
ards the sampling Lovász Local Lemma\nby Vishesh Jain (Stanford) as p
art of Warwick Combinatorics Seminar\n\n\nAbstract\nFor a constraint satis
faction problem which satisfies the condition of the Lovász local lemma (
LLL)\, the celebrated algorithm of Moser and Tardos allows one to efficien
tly find a satisfying assignment. In the past few years\, much work has go
ne into understanding whether one can efficiently sample from (approximate
ly) the uniform distribution on satisfying assignments under LLL-like cond
itions. I will discuss recent progress on this problem\, joint with Huy Tu
an Pham (Stanford) and Thuy Duong Vuong (Stanford).\n
LOCATION:https://researchseminars.org/talk/WCS/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tom Kelly (Birmingham)
DTSTART:20210625T130000Z
DTEND:20210625T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/31
DESCRIPTION:Title: A p
roof of the Erdős–Faber–Lovász conjecture\nby Tom Kelly (Birming
ham) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe Erdős–
Faber–Lovász conjecture (posed in 1972) states that the chromatic index
of any linear hypergraph on $n$ vertices is at most $n$. In joint work wi
th Dong Yeap Kang\, Daniela Kühn\, Abhishek Methuku\, and Deryk Osthus\,
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 som
e special cases.\n
LOCATION:https://researchseminars.org/talk/WCS/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nicholas Cook (Duke)
DTSTART:20210611T130000Z
DTEND:20210611T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/32
DESCRIPTION:Title: Reg
ularity method and large deviation principles for the Erdős–Rényi hype
rgraph\nby Nicholas Cook (Duke) as part of Warwick Combinatorics Semin
ar\n\n\nAbstract\nIn recent years there has been intense activity on the p
roblem of estimating the upper tail for counts of a fixed subgraph in a sp
arse Erdős–Rényi graph\, combining tools and perspectives from diverse
areas such as extremal graph theory\, statistical physics\, stochastic an
alysis and spectral theory. I will discuss some recent extensions of these
results to the hypergraph setting. Our approach rests on new decompositio
n theorems and counting lemmas for sparse Bernoulli tensors\, extending cl
assic results from the regularity method for dense graphs. These results a
re formulated in terms of a new class of cut-type norms specially tailored
for the sparse setting. Based on joint work with Amir Dembo and Huy Tuan
Pham.\n
LOCATION:https://researchseminars.org/talk/WCS/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Will Perkins (Chicago)
DTSTART:20210702T130000Z
DTEND:20210702T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/33
DESCRIPTION:Title: Pol
ymer models\, cluster expansion\, and local limit theorems: counting indep
endent sets in the hypercube\nby Will Perkins (Chicago) as part of War
wick Combinatorics Seminar\n\n\nAbstract\nI'll discuss how local central l
imit theorems can be used in combination with two tools from statistical p
hysics\, polymer models and the cluster expansion\, to asymptotically enum
erate independent sets of a given size in the hypercube. Joint work with M
atthew Jenssen and Aditya Potukuchi (arxiv:2106.09709)\n
LOCATION:https://researchseminars.org/talk/WCS/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Allan Sly (Princeton)
DTSTART:20211006T130000Z
DTEND:20211006T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/34
DESCRIPTION:Title: Fac
tor of IID for the Ising model on the tree\nby Allan Sly (Princeton) a
s part of Warwick Combinatorics Seminar\n\n\nAbstract\nIt's known that the
re are factors of IID for the free Ising model on the $d$-regular tree whe
n 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\, where there
is non-uniqueness but still extremality. The construction is via the limi
t of a system of \nstochastic differential equations.\n
LOCATION:https://researchseminars.org/talk/WCS/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Henry Towsner (Pennsylvania)
DTSTART:20211020T130000Z
DTEND:20211020T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/35
DESCRIPTION:Title: Reg
ularity Lemmas as Structured Decompositions\nby Henry Towsner (Pennsyl
vania) 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 decomposin
g a graph (approximately) into a structured part (the "unary" data) and a
random part. Then hypergraph regularity\, the generalization to k-uniform
hypergraphs\, can be viewed as a decomposition into multiple "tiers" of st
ructure - a unary part as well as a binary part and so on\, and then final
ly a random part.\n\nWe'll discuss how an analytic approach can make these
decompositions exact instances of the conditional expectation in probabil
ity\, and how these analytic proofs relate to combinatorial proofs with ex
plicit bounds. Finally\, we'll discuss regularity lemmas for other mathema
tical objects\, focusing on the example of ordered graphs and hypergraphs\
, and show how the "tiers of structures" perspective makes it possible to
see regularity lemmas for other mathematical objects as examples of the re
gularity lemma for hypergraphs.\n\n(No prior knowledge of the regularity l
emma and its variants is assumed.)\n
LOCATION:https://researchseminars.org/talk/WCS/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rob Silversmith (Warwick)
DTSTART:20211027T130000Z
DTEND:20211027T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/36
DESCRIPTION:Title: Cro
ss-ratios and perfect matchings\nby Rob Silversmith (Warwick) as part
of Warwick Combinatorics Seminar\n\n\nAbstract\nI’ll describe a simple p
rocess from algebraic geometry that takes in a collection of $4$-element s
ubsets $S_1\,S_2\,…\,S_{n-3}$ of $[n]$\, and outputs a nonnegative integ
er called a cross-ratio degree. I’ll discuss several interpretations of
cross-ratio degrees in algebra\, algebraic geometry\, and tropical geometr
y\, and present a combinatorial algorithm for computing them\, due to C. G
oldner. I’ll then present a perhaps-surprising upper bound for cross-rat
io degrees in terms of matchings.\n
LOCATION:https://researchseminars.org/talk/WCS/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Łukasz Grabowski (Lancaster)
DTSTART:20211110T140000Z
DTEND:20211110T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/37
DESCRIPTION:Title: Dir
ected analogues of expander graphs and random compact subsets of $\\mathbb
{R}^n$\nby Łukasz Grabowski (Lancaster) as part of Warwick Combinator
ics Seminar\n\n\nAbstract\nI will talk about two separate projects. The fi
rst one is a joint work with Endre Csoka (published in "Combinatorics\, Pr
obability 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 directed paths
(long is $|V|^\\delta$\, where $\\delta>0$ is an absolute constant). Exte
nders are a directed analogue of expander graphs\, since the latter ones a
re characterised by the property that it is impossible to remove a small a
mount of edges and obtain graphs which have small connected components. I'
ll discuss some conjectures in circuit complexity which motivated us to in
troduce extenders.\n\nThe second project is a joint work with Tomasz Ciesl
a (preprint available on arxiv). We construct compacts subsets of $\\mathb
b{R}^2$ which are not "domains of expansion"\, which answers a question ab
out spectral properties of group actions\, raised by Adrian Ioana.\n\nApar
t from the general theme of "expansion"\, both projects are related by the
method which is used to construct suitable examples - in both cases the c
onstruction is probablistic\, and the required properties follow from entr
opy estimates.\n
LOCATION:https://researchseminars.org/talk/WCS/37/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Natasha Morrison (Victoria)
DTSTART:20211117T160000Z
DTEND:20211117T170000Z
DTSTAMP:20260422T212557Z
UID:WCS/38
DESCRIPTION:Title: Unc
ommon systems of equations\nby Natasha Morrison (Victoria) as part of
Warwick Combinatorics Seminar\n\n\nAbstract\nA system of linear equations
$L$ over $\\mathbb{F}_q$ is common if the number of monochromatic solution
s to $L$ in any two-colouring of $\\mathbb{F}_q^n$ is asymptotically at le
ast the expected number of monochromatic solutions in a random two-colouri
ng of $\\mathbb{F}_q^n$. Motivated by existing results for specific system
s (such as Schur triples and arithmetic progressions)\, as well as extensi
ve research on common and Sidorenko graphs\, the systematic study of commo
n systems of linear equations was recently initiated by Saad and Wolf. Bui
lding on earlier work of of Cameron\, Cilleruelo and Serra\, as well as Sa
ad and Wolf\, common linear equations have been fully characterised by Fox
\, Pham and Zhao.\n\nIn this talk I will discuss some recent progress towa
rds a characterisation of common systems of two or more equations. In part
icular we prove that any system containing an arithmetic progression of le
ngth four is uncommon\, confirming a conjecture of Saad and Wolf. This fol
lows from a more general result which allows us to deduce the uncommonness
of a general system from certain properties of one- or two-equation subsy
stems.\n
LOCATION:https://researchseminars.org/talk/WCS/38/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martin Winter (Warwick)
DTSTART:20211201T140000Z
DTEND:20211201T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/39
DESCRIPTION:Title: Som
e modern open problems on polytopes with symmetries and regularities\n
by Martin Winter (Warwick) as part of Warwick Combinatorics Seminar\n\n\nA
bstract\nPolytope theory has itself established as a modern field of mathe
matics with deep connections to geometry\, combinatorics\, and algebra. Co
nvex polytopes with many symmetries and regularities however have thereby
played only a secondary role and are often considered as a fascinating\, y
et esoteric subject of the past. In this talk I want to rectify this by pr
esenting up to three modern open problems that connect the study of such p
olytopes to representation theory\, hyperplane arrangements and Weyl group
oids\, as well as spectral graph theory. More specifically\, the three top
ics are the possible symmetries of orbit polytopes\, inscribed and simple
zonotopes\, and the reconstruction of polytopes from graphs via spectral g
raph theory.\n
LOCATION:https://researchseminars.org/talk/WCS/39/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joseph Hyde (Warwick)
DTSTART:20211103T140000Z
DTEND:20211103T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/40
DESCRIPTION:Title: Pro
gress on the Kohayakawa-Kreuter conjecture\nby Joseph Hyde (Warwick) a
s 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 the prop
erty that whenever we colour the edges of $G(n\,p)$ with colours from the
set $[r] := \\{1\, ...\, r\\}$ there exists some $1 \\le i \\le r$ and a c
opy of $H_i$ in $G(n\,p)$ monochromatic in colour $i$.\n\nThere has been m
uch interest in determining the asymptotic threshold function for this pro
perty. Rödl and Ruciński (1995) determined the threshold function for th
e general symmetric case\; that is\, when $H_1 = ... = H_r$. A conjecture
of Kohayakawa and Kreuter (1997)\, if true\, would effectively resolve the
asymmetric problem. Recently\, the $1$-statement of this conjecture was c
onfirmed by Mousset\, Nenadov and Samotij (2021+). The $0$-statement howev
er has only been proved for pairs of cycles\, pairs of cliques and pairs o
f 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 determinis
tic\, natural subproblem. To demonstrate the potential of this approach\,
we show this subproblem can be resolved for almost all pairs of regular gr
aphs (satisfying properties one can assume when proving the $0$-statement)
.\n
LOCATION:https://researchseminars.org/talk/WCS/40/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Carla Groenland (Utrecht)
DTSTART:20211124T140000Z
DTEND:20211124T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/41
DESCRIPTION:Title: Asy
mptotic dimension of graph classes\nby Carla Groenland (Utrecht) as pa
rt of Warwick Combinatorics Seminar\n\n\nAbstract\nThe notion of asymptoti
c dimension of graph classes is borrowed from an invariant of metric space
s introduced by Gromov in the context of geometric group theory. In the ta
lk\, I will try to give some intuition for the definition and our proof te
chniques. Our main result is that each minor-closed family of graphs has a
symptotic dimension at most $2$. I will also mention some corollaries to c
lustered colouring and CS notions such as weak sparse partition schemes an
d weak diameter network decompositions. A special case of our main result
also implies that complete Riemannian surfaces have asymptotic dimension (
even Assouad-Nagata dimension) at most $2$ (which was previously unknown).
\n\n \nThis is based on joint work with M. Bonamy\, N. Bousquet\, L. Esper
et\, C.-H. Liu\, F. Pirot and A. Scott.\n
LOCATION:https://researchseminars.org/talk/WCS/41/
END:VEVENT
BEGIN:VEVENT
SUMMARY:George Kontogeorgiou (Warwick)
DTSTART:20211208T140000Z
DTEND:20211208T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/42
DESCRIPTION:Title: Equ
ivariant Cayley Complex Embeddings\nby George Kontogeorgiou (Warwick)
as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIn recent years\,
a lot of progress has been made in high-dimensional combinatorics\, i.e. e
xtending concepts from graph theory to higher dimensional CW-complexes. Tw
o such concepts of particular interest are (i) group actions and (ii) embe
ddings. In this talk we will prove that every finite group which admits a
faithful topological action over $\\mathbb{S}^3$ has a generalised Cayley
complex which embeds equivariantly in $\\mathbb{S}^3$. In the process\, we
will see some recent theorems and lemmas concerning $2$-complex embedding
s and group actions over $2$-complexes\, and we will derive a new combinat
orial characterization of finite groups acting faithfully and topologicall
y over $\\mathbb{S}^3$.\n
LOCATION:https://researchseminars.org/talk/WCS/42/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yinon Spinka (UBC)
DTSTART:20220112T160000Z
DTEND:20220112T170000Z
DTSTAMP:20260422T212557Z
UID:WCS/43
DESCRIPTION:Title: A t
ale of two balloons\nby Yinon Spinka (UBC) as part of Warwick Combinat
orics Seminar\n\n\nAbstract\nFrom each point of a Poisson point process st
art growing a balloon at rate $1$. When two balloons touch\, they pop and
disappear. Will balloons reach the origin infinitely often or not? We answ
er 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://researchseminars.org/talk/WCS/43/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jane Gao (Waterloo)
DTSTART:20220119T140000Z
DTEND:20220119T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/44
DESCRIPTION:Title: Per
fect matchings and sandwich conjectures of random regular graphs\nby J
ane Gao (Waterloo) as part of Warwick Combinatorics Seminar\n\n\nAbstract\
nIn the first half of the talk I will survey results on the limiting distr
ibutions of small and large subgraphs of random regular graphs\, and prese
nt a recent result on the limiting distribution of the number of perfect m
atchings. In the second half of the talk\, I will talk about the Kim-Vu sa
ndwich conjecture of random regular graphs\, recent progress\, and new res
ults.\n
LOCATION:https://researchseminars.org/talk/WCS/44/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andy Zucker (San Diego)
DTSTART:20220126T160000Z
DTEND:20220126T170000Z
DTSTAMP:20260422T212557Z
UID:WCS/45
DESCRIPTION:Title: Big
Ramsey degrees in binary free amalgamation classes\nby Andy Zucker (S
an Diego) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIn struc
tural Ramsey theory\, one considers a "small" structure $A$\, a "medium" s
tructure $B$\, a "large" structure $C$ and a number $r$\, then considers t
he 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$ all of wh
ose copies of $A$ receive just one color? For example\, when $C$ is the ra
tional linear order and $A$ and $B$ are finite linear orders\, then this f
ollows from the finite version of the classical Ramsey theorem. More gener
ally\, when $C$ is the Fraisse limit of a free amalgamation class in a fin
ite relational language\, then for any finite $A$ and $B$ in the given cla
ss\, 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 two-eleme
nt linear order\, a pathological coloring due to Sierpinski shows that thi
s cannot be done. However\, if we weaken our demands and only ask for a co
py of $B$ inside $C$ whose copies of $A$ receive "few" colors\, rather tha
n just one color\, we can succeed. For the two-element linear order\, we c
an get down to two colors. For the three-element order\, $16$ colors. This
number of colors is called the big Ramsey degree of a finite structure in
a Fraisse class. Recently\, building on groundbreaking work of Dobrinen\,
I proved a generalization of the Nesetril-Rodl theorem to binary free ama
lgamation classes defined by a finite forbidden set of irreducible structu
res (for instance\, the class of triangle-free graphs)\, showing that ever
y structure in every such class has a finite big Ramsey degree. My work on
ly bounded the big Ramsey degrees\, and left open what the exact values we
re. In recent joint work with Balko\, Chodounsky\, Dobrinen\, Hubicka\, Ko
necny\, and Vena\, we characterize the exact big Ramsey degree of every st
ructure in every binary free amalgamation class defined by a finite forbid
den set.\n
LOCATION:https://researchseminars.org/talk/WCS/45/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michelle Delcourt (Ryerson)
DTSTART:20220202T140000Z
DTEND:20220202T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/46
DESCRIPTION:Title: Rec
ent Progress on Hadwiger's Conjecture\nby Michelle Delcourt (Ryerson)
as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIn 1943\, Hadwiger
conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for
every $t \\ge 1.$ In a recent breakthrough\, Norin\, Song\, and Postle pr
oved that every graph with no $K_t$ minor is $O(t (\\log t)^c)$-colorable
for every $c > 0.25$\, Subsequently Postle showed that every graph with n
o $K_t$ minor is $O(t (\\log \\log t)^6)$-colorable. We improve upon 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 number o
f other interesting corollaries. A natural weakening of Hadwiger's Conject
ure 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 Conject
ure reduces to small graphs as well as that Linear Hadwiger's Conjecture h
olds for the class of $K_r$-free graphs (provided $t$ is sufficiently larg
e). This is joint work with Luke Postle.\n
LOCATION:https://researchseminars.org/talk/WCS/46/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rachel Greenfeld (UCLA)
DTSTART:20220209T160000Z
DTEND:20220209T170000Z
DTSTAMP:20260422T212557Z
UID:WCS/47
DESCRIPTION:Title: Dec
idability and periodicity of translational tilings\nby Rachel Greenfel
d (UCLA) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nTranslati
onal tiling is a covering of a space using translated copies of some build
ing blocks\, called the “tiles”\, without any positive measure overlap
s. 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 applications\, a
nd report on recent progress\, joint with Terence Tao.\n
LOCATION:https://researchseminars.org/talk/WCS/47/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Victor Chepoi (Marseille)
DTSTART:20220316T160000Z
DTEND:20220316T170000Z
DTSTAMP:20260422T212557Z
UID:WCS/48
DESCRIPTION:Title: Lab
eled sample compression schemes for complexes of oriented matroids\nby
Victor Chepoi (Marseille) as part of Warwick Combinatorics Seminar\n\n\nA
bstract\nThe sample compression schemes were introduced by Littlestone\nan
d Warmuth in 1986 and have been\nvastly studied in the literature due to t
heir importance in Machine\nLearning. Roughly speaking\, the goal\nis to c
ompress data as much as possible such that the original data can\nbe recon
structed\nfrom the compressed data. The Vapnik-Chervonenkis dimension is
central\nin Machine Learning and is\nimportant in Combinatorics and Discr
ete Geometry. Floyd and Warmuth in\n1995 asked whether any set-family\nof
VC-dimension $d$ has a sample compression scheme of size $O(d)$. This\nrem
ains one of the oldest open problems\nin Machine Learning.\n\nRecently we
showed that the topes of a complex of oriented matroids\n(abbreviated COM)
of VC-dimension $d$ admit a proper labeled\nsample compression scheme of
size $d$. This considerably extends results\nof Moran and Warmuth and the
authors and is a step\ntowards the sample compression conjecture. On the o
ne hand\, our approach\nexploits the rich combinatorial cell structure of
COMs\nvia oriented matroid theory. On the other hand viewing tope graphs o
f\nCOMs as partial cubes creates a fruitful link to metric graph theory.\n
\nIn the talk\, we will expalain COMs and the labeled sample compression\n
scheme for them.\n\nBased on the paper:\nV. Chepoi\, K. Knauer\, M. Philib
ert\, Labeled sample compression schemes\nfor complexes of oriented matroi
ds\, arXiv:2110.15168\, 2021.\n
LOCATION:https://researchseminars.org/talk/WCS/48/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stijn Cambie (Warwick)
DTSTART:20220223T140000Z
DTEND:20220223T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/49
DESCRIPTION:Title: Pac
king list-colourings\nby Stijn Cambie (Warwick) as part of Warwick Com
binatorics Seminar\n\n\nAbstract\nList colouring is an influential and cla
ssic topic in graph theory\, which is related to e.g. frequency assignment
\, resource allocation and scheduling problems. Sometimes it is natural to
consider multiple of these and the best one can aim for is a packing of d
isjoint solutions/ list colourings. We investigate this natural strengthen
ing\, the list packing problem.\nThis study was already suggested 25 years
ago by Alon\, Fellows and Hare. In this talk\, we sketch the (conjectured
) behaviour of this parameter and a related one under certain bounded degr
ee conditions.\n
LOCATION:https://researchseminars.org/talk/WCS/49/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Mikolaj Fraczyk (Chicago)
DTSTART:20220302T160000Z
DTEND:20220302T170000Z
DTSTAMP:20260422T212557Z
UID:WCS/50
DESCRIPTION:Title: Sta
tionary random graphs and groups\nby Mikolaj Fraczyk (Chicago) as part
of Warwick Combinatorics Seminar\n\n\nAbstract\nA stationary random graph
is a random rooted graphs $(G\,o)$ such that replacing the root $o$ by it
s random neighbor results in the same probability distribution. The more w
ell known unimodular random graphs are always stationary\, but the unimodu
larity assumption is in fact much stronger. Invariant random subgroups and
unimodular random graphs are now a household name in measured group theor
y\, and they found several applications in geometry and topology. In my ta
lk I want to advertise and describe some applications of the stationary ra
ndom graphs and groups. I will explain how they can be used to find non-ex
pander sub-graphs inside any given graph and how to prove that any higher
rank locally symmetric space of infinite volume must have points of arbitr
ary large injectivity radius. The talk is based on a joint work with Woute
r Van Limbeek and with Tsachik Gelander.\n
LOCATION:https://researchseminars.org/talk/WCS/50/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ján Špakula (Southampton)
DTSTART:20220309T140000Z
DTEND:20220309T150000Z
DTSTAMP:20260422T212557Z
UID:WCS/51
DESCRIPTION:Title: On
measured expanders\nby Ján Špakula (Southampton) as part of Warwick
Combinatorics Seminar\n\n\nAbstract\nBy a "measured graph" we simply mean
a graph with weights\nassigned to its vertices. The classical isoperimetri
c (a.k.a. Cheeger)\nconstant describing connectedness of a graph generalis
es to this\nsetting\, leading to a notion of a "measured expander": a sequ
ence of\nfinite graphs with a uniform positive lower bound on this isoperi
metric\nconstant.\nThe talk will walk through a bit of coarse geometry to
a functional\nanalytic question that led us to consider this notion. Our m
ain result\nis a characterisation of measured expanders through a Poincare
\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://researchseminars.org/talk/WCS/51/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xizhi Liu (Warwick)
DTSTART:20220427T130000Z
DTEND:20220427T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/52
DESCRIPTION:Title: The
feasible region of induced graphs\nby Xizhi Liu (Warwick) as part of
Warwick Combinatorics Seminar\n\n\nAbstract\nFix a graph $F$. A classical
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 kno
w the asymptotic solution is when $F$ is a complete graph\, and it was sol
ved completely only recently by Reiher using the flag algebra machinery. W
e will consider the other cases and show some results when $F$ is a comple
te bipartite graph or a complete graph minus one edge. Many interesting re
lated open problems will also be introduced. Joint work with Dhruv Mubayi
and Christian Reiher.\n
LOCATION:https://researchseminars.org/talk/WCS/52/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alistair Benford (Birmingham)
DTSTART:20220504T130000Z
DTEND:20220504T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/53
DESCRIPTION:Title: Tre
es 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 to guara
ntee $G$ contains a copy of $T$? A strengthening of Sumner’s conjecture
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 progress
towards this conjecture. We shall also consider how this problem can be ad
dressed by instead considering the maximum degree of the tree\, rather tha
n the number of leaves\, and state some open problems in this maximum degr
ee setting. This is joint work with Richard Montgomery.\n
LOCATION:https://researchseminars.org/talk/WCS/53/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Péter Pál Pach (Budapest)
DTSTART:20220511T130000Z
DTEND:20220511T140000Z
DTSTAMP:20260422T212557Z
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\nAbstract\n
The Alon-Jaeger-Tarsi conjecture states that for any finite field $F$ of s
ize at least 4 and any nonsingular matrix $M$ over $F$ there exists a ve
ctor $x$ such that neither $x$ nor $Mx$ has a 0 component. In joint work w
ith János Nagy we proved this conjecture when the size of the field is su
fficiently large\, namely\, when $61<|F|\\ne 79$. In this talk we will dis
cuss this result.\n
LOCATION:https://researchseminars.org/talk/WCS/54/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Richard Montgomery (Warwick)
DTSTART:20220525T130000Z
DTEND:20220525T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/55
DESCRIPTION:Title: On
the Ryser-Brualdi-Stein conjecture\nby Richard Montgomery (Warwick) as
part of Warwick Combinatorics Seminar\n\n\nAbstract\nThe Ryser-Brualdi-St
ein conjecture states that every Latin square of order $n$ should have a p
artial transversal with $n-1$ elements\, and a full transversal if $n$ is
odd. In 2020\, Keevash\, Pokrovskiy\, Sudakov and Yepremyan improved the l
ong-standing best known bounds on this conjecture by showing that a partia
l transversal with $n-O(\\log n/\\log\\log n)$ elements always exists. I w
ill discuss how to show\, for large $n$\, that a partial transversal with
$n-1$ elements always exists.\n
LOCATION:https://researchseminars.org/talk/WCS/55/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gal Kronenberg (Oxford)
DTSTART:20220615T130000Z
DTEND:20220615T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/56
DESCRIPTION:Title: Ind
ependent sets in random subgraphs of the hypercube\nby Gal Kronenberg
(Oxford) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nIndepende
nt sets in bipartite regular graphs have been studied extensively in combi
natorics\, probability\, computer science and more. The problem of countin
g independent sets is particularly interesting in the $d$-dimensional hype
rcube $\\{0\,1\\}^d$\, motivated by the lattice gas hardcore model from st
atistical physics. Independent sets also turn out to be very interesting i
n the context of random graphs.\n\nThe number of independent sets in the h
ypercube $\\{0\,1\\}^d$ was estimated precisely by Korshunov and Sapozhenk
o in the 1980s and recently refined by Jenssen and Perkins.\n\nIn this tal
k we will discuss new results on the number of independent sets in a rando
m subgraph of the hypercube. The results extend to the hardcore model and
rely on an analysis of the antiferromagnetic Ising model on the hypercube.
\n\nThis talk is based on joint work with Yinon Spinka.\n
LOCATION:https://researchseminars.org/talk/WCS/56/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miek Messerschmidt (Pretoria)
DTSTART:20220622T130000Z
DTEND:20220622T140000Z
DTSTAMP:20260422T212557Z
UID:WCS/57
DESCRIPTION:Title: Com
pact packings of the plane with discs\nby Miek Messerschmidt (Pretoria
) as part of Warwick Combinatorics Seminar\n\n\nAbstract\nAfter explaining
what a compact packing of the plane by discs is\, I will discuss the foll
owing question: "For which $n$-tuples of distinct positive real numbers is
there a compact packing of the plane with discs\, so that\, firstly\, onl
y the mentioned $n$ numbers are used as radii of discs in the packing\, an
d secondly\, every one of the mentioned $n$ numbers occurs at least once a
s a radius of a disc in the packing?"\n\nI will discuss some aspects of th
is question along with its history\, which is surprisingly recent (e.g.\,
the case $n=2$ was only solved in 2006).\n
LOCATION:https://researchseminars.org/talk/WCS/57/
END:VEVENT
END:VCALENDAR