BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Hong Liu (University of Warwick)
DTSTART:20200604T070000Z
DTEND:20200604T083000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/1
DESCRIPTION:Title: Basics on the hypergraph container method V\nby Hong Liu (University
of Warwick) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nThis is a
gentle introduction to basics of the hypergraph container method introduc
ed independently by Balogh\, Samotij and Morris\, and Saxton and Thomason.
The method has seen numerous applications in extremal combinatorics and o
ther related areas in the past decade. We will focus mostly on examples\,
illustrating how to apply this method on various types of problems.\n\nTal
k 5: In the last talk\, we sketch a few more applications of hypergraph co
ntainer methods and variations of the method.\n
LOCATION:https://researchseminars.org/talk/SCMSComb/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv University)
DTSTART:20200611T070000Z
DTEND:20200611T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/2
DESCRIPTION:Title: Large deviations of triangle counts in the binomial random graph I\nb
y Wojciech Samotij (Tel Aviv University) as part of SCMS Combinatorics Sem
inar\n\n\nAbstract\nSuppose that $Y_1\, \\ldots \, Y_N$ are i.i.d. (indepe
ndent identically distributed) random variables and let $X = Y_1 + … + Y
_N$. The classical theory of large deviations allows one to accurately est
imate the probability of the tail events $X < (1-c)E[X]$ and $X > (1+c)E[X
]$ for any positive $c$. However\, the methods involved strongly rely on t
he fact that X is a linear function of the independent variables $Y_1\,
…\, Y_N.$ There has been considerable interest—both theoretical and pr
actical—in developing tools for estimating such tail probabilities also
when $X$ is a nonlinear function of the $Y_i$. One archetypal example stud
ied by both the combinatorics and the probability communities is when $X$
is the number of triangles in the binomial random graph $G(n\,p)$.\n\nTalk
I: We will give a very gentle introduction to the theory of large deviati
ons and discuss the history of the large deviation problem for triangle co
unts.\n
LOCATION:https://researchseminars.org/talk/SCMSComb/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv University)
DTSTART:20200618T070000Z
DTEND:20200618T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/3
DESCRIPTION:Title: Large deviations of triangle counts in the binomial random graph II\n
by Wojciech Samotij (Tel Aviv University) as part of SCMS Combinatorics Se
minar\n\n\nAbstract\nSuppose that $Y_1\, \\ldots \, Y_N$ are i.i.d. (indep
endent identically distributed) random variables and let $X = Y_1 + … +
Y_N$. The classical theory of large deviations allows one to accurately es
timate the probability of the tail events $X < (1-c)E[X]$ and $X > (1+c)E[
X]$ for any positive $c$. However\, the methods involved strongly rely on
the fact that X is a linear function of the independent variables $Y_1\,
…\, Y_N.$ There has been considerable interest—both theoretical and pr
actical—in developing tools for estimating such tail probabilities also
when $X$ is a nonlinear function of the $Y_i$. One archetypal example stud
ied by both the combinatorics and the probability communities is when $X$
is the number of triangles in the binomial random graph $G(n\,p)$.\n\nTalk
II: We will present a complete solution to the upper tail problem for tri
angle counts in $G(n\,p)$ that was obtained recently in a joint work with
Matan Harel and Frank Mousset.\n\nPassword 061801\n
LOCATION:https://researchseminars.org/talk/SCMSComb/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lina Li (University of Illinois at Urbana-Champaign)
DTSTART:20200625T020000Z
DTEND:20200625T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/4
DESCRIPTION:Title: Independent sets in middle two layers of Boolean lattice\nby Lina Li
(University of Illinois at Urbana-Champaign) as part of SCMS Combinatorics
Seminar\n\n\nAbstract\nIn recent decades\, independent sets in the discre
te hypercube has received a lot of attention from many notable researchers
.\nThe classical result of Korshunov and Sapozhenko in 1983 counts the num
ber of independent sets in the hypercube\, and then shows that typical ind
ependent sets are not far from the trivial construction.\nFor an odd integ
er $n=2d-1$\, let $\\mathcal{B}(n\, d)$ be the subgraph of the hypercube i
nduced by the two largest layers. \nOur new results describe the typical s
tructure of independent sets in $\\mathcal{B}(n\, d)$ and also give precis
e asymptotics on the number of them.\nThe proofs use Sapozhenko's graph co
ntainer lemma\, and a recently developed method of Jenssen and Perkins\, w
hich combines Sapozhenko's graph container lemma with a classcal tool from
statistical physics\, the cluster expansion for polymer models.\nThis is
a joint work with with Jozsef Balogh and Ramon I. Garcia.\n\nPassword 0168
01\n
LOCATION:https://researchseminars.org/talk/SCMSComb/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bojan Mohar (Simon Fraser University)
DTSTART:20200702T080000Z
DTEND:20200702T090000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/5
DESCRIPTION:Title: Can the genus of a graph be approximated?\nby Bojan Mohar (Simon Fras
er University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nThe ge
nus g(G) of a graph G is defined as the minimum genus of a surface in whic
h G can be embedded (drawn without crossings). Thomassen proved that it is
NP-hard to determine whether g(G) < k\, when the graph G and an integer k
are given to us as the input. Robertson and Seymour (and the speaker) pro
ved that this problem is FPT (fixed-parameter tractable). However\, it is
wide open whether the value of g(G) can be approximated.\n\nThe speaker wi
ll give an overview of this problem\, describe underlying conjectures\, an
d present a complete solution for the case when the graph is dense. The so
lution uses Szemeredi Regularity Lemma and a result on the genus of quasi-
random graphs.\n\nThis is joint work with Yifan Jing.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yifan Jing (Search Results Web Result with Site Links University
of Illinois Urbana-Champaign)
DTSTART:20200709T020000Z
DTEND:20200709T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/6
DESCRIPTION:Title: Structures of sets with minimum measure growth\nby Yifan Jing (Search
Results Web Result with Site Links University of Illinois Urbana-Champai
gn) as part of SCMS Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/SCMSComb/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yufei Zhao (Massachusetts Institute of Technology)
DTSTART:20200806T020000Z
DTEND:20200806T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/7
DESCRIPTION:Title: Equiangular lines\, spherical two-distance sets\, and spectral graph theo
ry\nby Yufei Zhao (Massachusetts Institute of Technology) as part of S
CMS Combinatorics Seminar\n\n\nAbstract\nSolving a longstanding problem on
equiangular lines\, we determine\, for each given fixed angle and in all
sufficiently large dimensions\, the maximum number of lines pairwise separ
ated by the given angle. The answer is expressed in terms of spectral radi
i of graphs.\n\nGeneralizing to spherical two-distance sets\, we conjectur
ally relate the problem to a certain eigenvalue problem for signed graphs\
, and solve it in a number of cases.\n\nA key ingredient is a new result i
n spectral graph theory: the adjacency matrix of a connected bounded degre
e graph has sublinear second eigenvalue multiplicity.\n\nJoint work with Z
ilin Jiang\, Jonathan Tidor\, Yuan Yao\, and Shengtong Zhang (all MIT)\n\n
password 111317\n
LOCATION:https://researchseminars.org/talk/SCMSComb/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zilin Jiang (Massachusetts Institute of Technology)
DTSTART:20200813T020000Z
DTEND:20200813T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/8
DESCRIPTION:Title: Negligible obstructions and Turán exponents\nby Zilin Jiang (Massach
usetts Institute of Technology) as part of SCMS Combinatorics Seminar\n\n\
nAbstract\nThe conjecture on the realizability of rational exponents state
s that for every rational number r in (1\,2) there is a graph F such that
ex(n\, F) = Θ(n^r). In their beautiful work\, Bukh and Conlon resolved a
weaker version of the conjecture\, where F is allowed to be a family of gr
aphs. Subsequent work has been focusing on narrowing this family down to a
single graph. We formulate a framework\, that is taking shape in recent w
ork\, to attack the conjecture\, and we showcase an application of the fra
mework to obtain infinitely many new Turán exponents.\n\nJoint work with
Tao Jiang and Jie Ma.\n
LOCATION:https://researchseminars.org/talk/SCMSComb/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oliver Janzer (University of Cambridge)
DTSTART:20200820T080000Z
DTEND:20200820T090000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/9
DESCRIPTION:Title: Rainbow Turán number of even cycles\nby Oliver Janzer (University of
Cambridge) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nThe rainb
ow Tur\\'an number $\\mathrm{ex}^*(n\,H)$ of a\ngraph $H$ is the maximum p
ossible number of edges in a properly\nedge-coloured $n$-vertex graph with
no rainbow subgraph isomorphic to\n$H$. We prove that for any integer $k\
\geq 2$\,\n$\\mathrm{ex}^*(n\,C_{2k})=O(n^{1+1/k})$. This is tight and est
ablishes a\nconjecture of Keevash\, Mubayi\, Sudakov and Verstra\\"ete. We
use the same\nmethod to prove several other conjectures in various topics
. For\nexample\, we give an upper bound for the Tur\\'an number of the blo
w-ups\nof even cycles\, which can be used to disprove a conjecture of Erd\
\H os\nand Simonovits.\n\npassword 111317\n
LOCATION:https://researchseminars.org/talk/SCMSComb/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jaehoon Kim (KAIST)
DTSTART:20200910T070000Z
DTEND:20200910T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/10
DESCRIPTION:Title: Extremal density for sparse minors and subdivisions\nby Jaehoon Kim
(KAIST) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nWe prove an a
symptotically tight bound on the extremal density guaranteeing subdivision
s of bounded-degree bipartite graphs with a separability condition. As cor
ollaries\, we answered several questions of Reed and Wood on embedding spa
rse minors. In particular\, we prove that a graph with average degree $(3/
2+ o(1))t$ contains every $t$-vertex planar graph as a minor and this cons
tant $3/2$ is best possible. This is joint work with John Haslegrave and
Hong Liu.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Volec (Czech Technical University in Prague)
DTSTART:20200917T070000Z
DTEND:20200917T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/11
DESCRIPTION:Title: Non-bipartite k-common graphs\nby Jan Volec (Czech Technical Univers
ity in Prague) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nFor a
given integer $k\\ge2$\, a graph H is said to be "k-common" if the number
of monochromatic copies of H in a k-coloring of the edges of an n-vertex c
omplete graph is asymptotically minimized by a random coloring. Note that
the case $k=2$ coincides with the notion of common graphs introduced in 19
60s.\n\nWe construct the first examples of non-bipartite k-common graphs f
or $k\\ge3$\, which resolves a problem of Jagger\, Stovícek and Thomason
from 1996.\n\nThis is a joint work with Dan Kral\, Jon Noel\, Sergey Norin
and Fan Wei.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tao Jiang (Miami University)
DTSTART:20200924T020000Z
DTEND:20200924T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/12
DESCRIPTION:Title: Linear cycles of given lengths in linear hypergraphs\nby Tao Jiang (
Miami University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nA w
ell-known result of Verstraete states that for each integer k\\geq 2 every
graph G with average degree at least 8k contains cycles of k consecutive
even lengths\, the shortest of which is at most twice the radius of G.\n\n
In this talk\, we extend Verstraete's result for linear cycles in linear r
-uniform hypergraphs\, where r\\geq 3.\nWe show that for each k\\geq 2\, t
here exist constants c_1\,c_2 depending only on r such that every linear r
-graph with average degree at least c_1 k contains linear cycles of k cons
ecutive even lengths and every linear r-graph with average degree at c_2k
contains linear cycles of k consecutive lengths. For the even consecutive
lengths case\, our bound on the shortest cycle length among the cycles obt
ained is tight\, which also yields improved upper bound on the linear Tura
n number of an even cycle of given length. For the consecutive lengths cas
e\, our bound on the shortest cycle length is tight within a constant fact
or.\n\nThe talk will focus on the tools used in establishing the results.
We think that these tools can find further applications to other extremal
problems on cycles in the hypergraph setting.\n\nThis is joint work with J
ie Ma and Liana Yepremyan.\n\npassword 061801\n
LOCATION:https://researchseminars.org/talk/SCMSComb/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kevin Hendrey (IBS)
DTSTART:20200827T070000Z
DTEND:20200827T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/13
DESCRIPTION:Title: Counting cliques in 1-planar graphs\nby Kevin Hendrey (IBS) as part
of SCMS Combinatorics Seminar\n\n\nAbstract\nA 1-planar graph is a graph w
hich can be drawn in the plane so that every edge is crossed at most once.
It is well known that the maximum number of edges in a 1-planar graph is
4n-8. It is natural consider extending this result to larger cliques. We p
recisely determine the maximum number of cliques of any given size in a 1-
planar graph\, and also determine the family of 1-planar graphs which are
extremal for this question. This is joint work with Pascal Gollin\, Abhish
ek Methuku\, Casey Tompkins and Xin Zhang.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hongliang Lu (XJTU)
DTSTART:20200903T070000Z
DTEND:20200903T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/14
DESCRIPTION:Title: Co-degree condition for matchings in $k$-partite $k$-graphs\nby Hon
gliang Lu (XJTU) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nLet
$H$ be a $k$-partite $k$-graph with $n$ vertices in each partition class\
, and let\n$\\delta_{k-1}(H)$ denote the minimum co-degree of $H$. We cha
racterize those $H$ with $\\delta_{k-1}(H) \\geq n/2$ and with no perfect
matching. As a consequence we give an affirmative answer to the following
question of R\\"odl and Ruci\\'nski: If $k$ is even or $n \\not\\equiv 2 \
\pmod 4$\, does $\\delta_{k-1}(H) \\geq n/2$ imply that $H$ has a perfect
matching? We give an example indicating that it is not sufficient to impo
se this degree bound on only two types of $(k-1)$-sets. For near perfect m
atching\, we gave a tight sufficient condition in term of co-degree\, whic
h is also independently obtained by Han\, Zang and Zhao. Moreover\, I woul
d like to introduce several problems I am interested in.\n\npassword 12132
3\n
LOCATION:https://researchseminars.org/talk/SCMSComb/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Cranston (Virginia Commonwealth University)
DTSTART:20201015T020000Z
DTEND:20201015T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/15
DESCRIPTION:Title: Vertex Partitions into an Independent Set and a Forest with Each Compone
nt Small\nby Daniel Cranston (Virginia Commonwealth University) as par
t of SCMS Combinatorics Seminar\n\n\nAbstract\nFor each integer $k \\ge 2$
\, we determine a sharp bound on\nmad(G) such that V(G) can be partitioned
into sets I and $F_k$\, where I\nis an independent set and $G[F_k]$ is a
forest in which each component\nhas at most $k$ vertices. For each $k$ we
construct an infinite family of\nexamples showing our result is best possi
ble. Hendrey\, Norin\, and Wood\nasked for the largest function g(a\,b) su
ch that if mad(G) < g(a\,b)\nthen V(G) has a partition into sets A and B s
uch that mad(G[A]) < a\nand mad(G[B]) < b. They specifically asked for the
value of g(1\,b)\,\nwhich corresponds to the case that A is an independen
t set.\nPreviously\, the only values known were g(1\,4/3) and g(1\,2). We
find\nthe value of g(1\,b) whenever 4/3 < b < 2. This is joint work with\n
Matthew Yancey.\n\npassword 061801\n
LOCATION:https://researchseminars.org/talk/SCMSComb/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fan Wei (Princeton University)
DTSTART:20201022T020000Z
DTEND:20201022T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/16
DESCRIPTION:Title: Some variants of the graph removal lemma\nby Fan Wei (Princeton Univ
ersity) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nAmong the num
erous applications of the regularity lemma\, a classical one is the graph
removal lemma. It has applications in fields such as number theory and the
oretical computer science. For every fixed graph H\, the H-removal lemma g
ives a highly nontrivial equivalence between the density of H in G and the
L1 distance between a graph G to the set of H-free graphs. Whether the hu
ge bound in the quantitative estimate is necessary remains a big open ques
tion in graph theory. In this talk\, I will discuss some recent works on a
strengthening of the usual graph removal lemma. This talk is based on
some joint work with Jacob Fox.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jiaao Li (Nankai University)
DTSTART:20201029T070000Z
DTEND:20201029T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/17
DESCRIPTION:Title: Flows and Cycle Covers of Signed Graphs\nby Jiaao Li (Nankai Univers
ity) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nFlow theory of s
igned graphs was introduced by Bouchet as dual notion to local tensions of
graphs embedded on non-orientable surfaces\, which generalized Tutte's fl
ow theory of ordinary graphs. Recently\, we prove that every flow-admissib
le signed graph admits a nowhere-zero balanced $Z_2\\times Z_3$-flow. This
extends Seymour's 6-flow theorem from ordinary graphs (which are signed g
raphs without unbalanced circuit) to long-barbell-free signed graphs (whic
h are signed graphs without vertex-disjoint unbalanced circuits). In this
talk\, we will show how to apply this theorem to extend some classical res
ults on flow and cycle decomposition/cover\, due to Jaeger\, Fan\, Alon-Ta
rsi\, etc.\, to some signed graphs. Those classical results may not be tig
ht for ordinary graphs\, whose expected improvements are known as Tutte's
$5$-flow Conjecture\, Berge-Fulkerson Conjecture\, Cycle Double Cover Conj
ecture and Shortest Cycle Cover Conjecture. In contrast\, we shall see tha
t the signed analogies of those classical results are indeed sharp for cer
tain signed graphs.\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hao Huang (Emory University)
DTSTART:20201008T020000Z
DTEND:20201008T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/18
DESCRIPTION:Title: Covering cubes by hyperplanes\nby Hao Huang (Emory University) as pa
rt of SCMS Combinatorics Seminar\n\n\nAbstract\nNote that the vertices of
the $n$-dimensional cube $\\{0\, 1\\}^n$ can be covered by two affine hype
rplanes $x_1=1$ and $x_1=0$. However if we leave one vertex uncovered\, th
en suddenly at least $n$ affine hyperplanes are needed. This was a classic
al result of Alon and F\\"uredi\, followed from the Combinatorial Nullstel
lensatz.\n\nIn this talk\, we consider the following natural generalizatio
n of the Alon-F\\"uredi theorem: what is the minimum number of affine hype
rplanes such that the vertices in $\\{0\, 1\\}^n \\setminus \\{\\vec{0}\\}
$ are covered at least $k$ times\, and $\\vec{0}$ is uncovered? We answer
the problem for $k \\le 3$ and show that a minimum of $n+3$ affine hyperpl
anes is needed for $k=3$\, using a punctured version of the Combinatorial
Nullstellensatz. We also develop an analogue of the Lubell-Yamamoto-Meshal
kin inequality for subset sums\, and solve the problem asymptotically for
fixed $n$ and $k \\rightarrow \\infty$\, and pose a conjecture for fixed $
k$ and large $n$.\n\nJoint work with Alexander Clifton (Emory University).
\n\npassword 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jie Han (University of Rhode Island)
DTSTART:20201105T070000Z
DTEND:20201105T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/19
DESCRIPTION:Title: $F$-factors in graphs with randomness conditions\nby Jie Han (Univer
sity of Rhode Island) as part of SCMS Combinatorics Seminar\n\n\nAbstract\
nThe celebrated Hajnal-Szemerédi Theorem is a cornerstone in extremal gra
ph theory and has many applications and extensions. We will focus on a cla
ss of extensions where the host graph enjoys mild randomness conditions (e
.g.\, does not have large independent set\, or contains a small amount of
random edges) and discuss some recent problems and developments.\n\npasswo
rd 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weifan Wang (Zhejing Normal University)
DTSTART:20201112T070000Z
DTEND:20201112T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/20
DESCRIPTION:Title: Simultaneous Colorings of Plane Graphs (In Chinese)\nby Weifan Wang
(Zhejing Normal University) as part of SCMS Combinatorics Seminar\n\n\nAbs
tract\nGiven a plane graph G = (V\, E\, F)\, we can define the vertex colo
ring for V\, the edge coloring for E\, the face coloring for F\, the total
coloring for V∪E\, the coupled coloring for V∪F\, the edge-face color
ing for E∪F\, and the entire coloring V∪E∪F\, such that adjacent or
incident elements have different colors. In this talk we shall give a surv
ey on these colorings and list colorings of plane graphs. Some recent resu
lts and open problems about this direction are mentioned.\n\npassword 1213
23\n
LOCATION:https://researchseminars.org/talk/SCMSComb/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Postle (University of Waterloo)
DTSTART:20201126T020000Z
DTEND:20201126T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/21
DESCRIPTION:Title: Further progress towards Hadwiger's conjecture\nby Luke Postle (Univ
ersity of Waterloo) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nI
n 1943\, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-
1)$-colorable for every $t\\ge 1$. In the 1980s\, Kostochka and Thomason
independently proved that every graph with no $K_t$ minor has average degr
ee $O(t\\sqrt{\\log t})$ and hence is $O(t\\sqrt{\\log t})$-colorable. R
ecently\, Norin\, Song and I showed that every graph with no $K_t$ minor i
s $O(t(\\log t)^{\\beta})$-colorable for every $\\beta > 1/4$\, making the
first improvement on the order of magnitude of the $O(t\\sqrt{\\log t})$
bound. Here we show that every graph with no $K_t$ minor is $O(t (\\log t)
^{\\beta})$-colorable for every $\\beta > 0$\; more specifically\, they ar
e $O(t (\\log \\log t)^{6})$-colorable.\n\npw 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Youngho Yoo (Georgia Institute of Technology)
DTSTART:20201210T020000Z
DTEND:20201210T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/22
DESCRIPTION:Title: Packing A-paths and cycles with modularity constraints\nby Youngho Y
oo (Georgia Institute of Technology) as part of SCMS Combinatorics Seminar
\n\n\nAbstract\nWe study the approximate packing-covering duality\, also k
nown as the Erdős-Pósa property\, of various families of paths and cycle
s with modularity constraints. Our main tool is a structure theorem for un
directed group-labelled graphs refining the flat wall theorem of Robertson
and Seymour\, and as a first consequence we obtain the Erdős-Pósa prope
rty of cycles of length L mod m for any integer L and odd prime power m.\n
This partially answers a question of Dejter and Neumann-Lara from 1987 on
characterizing all such integer pairs L and m. With some more work\, we al
so prove the Erdős-Pósa property of A-paths of length 0 mod p for prime
p\, resolving a recent question of Bruhn and Ulmer and thereby characteriz
ing when A-paths of length L mod m satisfy the Erdős-Pósa property. Join
t work with Robin Thomas.\n\npw 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chun-Hung Liu (Texas A&M University)
DTSTART:20201119T020000Z
DTEND:20201119T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/23
DESCRIPTION:Title: Clustered coloring for Hadwiger type problems\nby Chun-Hung Liu (Tex
as A&M University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nHa
dwiger (Hajos and Gerards and Seymour\, respectively) conjectured that \nt
he vertices of every graph with no $K_{t+1}$ minor (topological minor \na
nd odd minor\, respectively) can be colored with t colors such that any \
npair of adjacent vertices receive different colors. These conjectures \na
re stronger than the Four Color Theorem and are either open or false \nin
general. A weakening of these conjectures is to consider clustered \ncolo
ring which only requires every monochromatic component to have \nbounded s
ize instead of size 1. It is known that t colors are still \nnecessary for
the clustered coloring version of those three conjectures. \nJoint with D
avid Wood\, we prove a series of tight results about \nclustered coloring
on graphs with no subgraph isomorphic to a fixed \ncomplete bipartite grap
h. These results have a number of applications. \nIn particular\, they imp
ly that the clustered coloring version of Hajos’ \nconjecture is true fo
r bounded treewidth graphs in a stronger sense: \n$K_{t+1}$ topological mi
nor free graphs of bounded treewidth are clustered \nt-list-colorable. The
y also lead to the first linear upper bound for the \nclustered coloring v
ersion of Hajos’ conjecture and the currently best \nupper bound for the
clustered coloring version of the Gerards-Seymour \nconjecture.\n\npw 030
332\n
LOCATION:https://researchseminars.org/talk/SCMSComb/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xujin Chen (Chinese Academy of Sciences)
DTSTART:20201217T070000Z
DTEND:20201217T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/24
DESCRIPTION:Title: Ranking Tournaments with No Errors\nby Xujin Chen (Chinese Academy o
f Sciences) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nWe examin
e the classical problem of ranking a set of players on the basis of a set
of\npairwise comparisons arising from a sports tournament\, with the objec
tive of minimizing the total number of upsets\,\nwhere an upset occurs if
a higher ranked player was actually defeated by a lower ranked player. Thi
s problem\ncan be rephrased as the so-called minimum feedback arc set prob
lem on tournaments\, which arises in a rich variety\nof applications and h
as been a subject of extensive research. We study this NP-hard problem usi
ng\nstructure-driven and linear programming approaches.\n\nLet $T=(V\,A)$
be a tournament with a nonnegative integral weight\n$w(e)$ on each arc $e$
. A subset $F$ of arcs is called a feedback arc set if $T\\setminus F$ con
tains no cycles\n(directed). A collection $C$ of cycles (with repetition a
llowed) is called a cycle packing if each arc\n$e$ is used at most $w(e)$
times by members of $C$. We call $T$ cycle Mengerian if\, for every nonne
gative\nintegral function ${w}$ defined on $A$\, the minimum total weight
of a feedback arc set is equal to the maximum\nsize of a cycle packing. In
this talk\, we\nwill discuss the characterization that a tournament is cy
cle Mengerian if and only if it contains none of\nfour Möbius ladders as
a subgraph. (Joint work with Guoli Ding\, Wenan Zang\, and Qiulan Zhao.)\n
\npw 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guantao Chen (Georgia State University)
DTSTART:20201203T020000Z
DTEND:20201203T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/25
DESCRIPTION:Title: Graph Edge Coloring\nby Guantao Chen (Georgia State University) as p
art of SCMS Combinatorics Seminar\n\n\nAbstract\nGraph edge coloring is a
well established subject in the field of graph theory\, it is one of the b
asic combinatorial optimization problems: color the edges of a graph G wit
h as few colors as possible such that each edge receives a color and adjac
ent edges\, that is\, different edges incident to a common vertex\, receiv
e different colors. The minimum number of colors needed for such a colorin
g of G is called the chromatic index of G\, written $\\chi(G)$. By a resul
t of Holyer\, the determination of the chromatic index is an NP-hard optim
ization problem. The NP-hardness gives rise to the necessity of using heur
istic algorithms. In particular\, we are interested in upper bounds for th
e chromatic index that can be efficiently realized by a coloring algorithm
. In this talk\, we will start with the well-known Goldberg-Seymour conjec
ture and its proof\, then talk about the recent development of recoloring
techniques and its applications to a number of classic problems in critica
l class 2 simple graphs.\n\npw 030303\n
LOCATION:https://researchseminars.org/talk/SCMSComb/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zi-Xia Song (University of Central Florida)
DTSTART:20201231T020000Z
DTEND:20201231T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/26
DESCRIPTION:Title: Hadwiger’s Conjecture\nby Zi-Xia Song (University of Central Flori
da) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nHadwiger’s conj
ecture from 1943 states that for every integer $t\\ge 1$\, every graph eit
her can be t-colored or has a subgraph that can be contracted to the compl
ete graph on t + 1 vertices. This is a far-reaching generalization of the
Four-Color Theorem and perhaps the most famous conjecture in graph theory.
In this talk we will survey the history of Hadwiger’s conjecture and th
e main ideas of recent results.\n\npw 030303\n
LOCATION:https://researchseminars.org/talk/SCMSComb/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benjamin Gunby (Harvard University)
DTSTART:20210107T020000Z
DTEND:20210107T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/27
DESCRIPTION:Title: Upper Tails in Random Regular Graphs\nby Benjamin Gunby (Harvard Uni
versity) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nFix a graph
K. What is the probability that a sparse random regular graph contains man
y more copies of K than expected?\n\npw 030303\n
LOCATION:https://researchseminars.org/talk/SCMSComb/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pinyan Lu (Shanghai University of Finance and Economics)
DTSTART:20201224T070000Z
DTEND:20201224T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/28
DESCRIPTION:Title: Classifying Computational Counting Problems\nby Pinyan Lu (Shanghai
University of Finance and Economics) as part of SCMS Combinatorics Seminar
\n\n\nAbstract\nAbstract: The main theme of theoretical computer science i
s to classify various computational problems in terms of their inherent co
mputational difficulty. In this talk\, I will try to demonstrate this gene
ral theme by some cases study of my own research on the algorithms and com
plexity for counting problems defined on graphs.\n\npw 030303\n
LOCATION:https://researchseminars.org/talk/SCMSComb/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hong Liu (University of Warwick)
DTSTART:20210114T070000Z
DTEND:20210114T080000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/29
DESCRIPTION:Title: A solution to Erdős and Hajnal’s odd cycle problem\nby Hong Liu (
University of Warwick) as part of SCMS Combinatorics Seminar\n\n\nAbstract
\nIn 1981\, Erdős and Hajnal asked whether the sum of the reciprocals of
the odd cycle lengths in a graph with infinite chromatic number is necessa
rily infinite. Let C(G) be the set of cycle lengths in a graph G and let C
_odd(G) be the set of odd numbers in C(G). We prove that\, if G has chroma
tic number k\, then ∑_{ℓ∈C_odd(G)} 1/ℓ≥(1/2−o_k(1))log k. This
solves Erdős and Hajnal’s odd cycle problem\, and\, furthermore\, this
bound is asymptotically optimal.\n\nIn 1984\, Erdős asked whether there
is some d such that each graph with chromatic number at least d (or perhap
s even only average degree at least d) has a cycle whose length is a power
of 2. We show that an average degree condition is sufficient for this pro
blem\, solving it with methods that apply to a wide range of sequences in
addition to the powers of 2.\n\nFinally\, we use our methods to show that\
, for every k\, there is some d so that every graph with average degree at
least d has a subdivision of the complete graph K_k in which each edge is
subdivided the same number of times. This confirms a conjecture of Thomas
sen from 1984.\nJoint work with Richard Montgomery.\n\npw 061801\n
LOCATION:https://researchseminars.org/talk/SCMSComb/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joonkyung Lee (University College London)
DTSTART:20210121T110000Z
DTEND:20210121T120000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/30
DESCRIPTION:by Joonkyung Lee (University College London) as part of SCMS C
ombinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/SCMSComb/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bundit Laekhanukit (SUFE)
DTSTART:20210401T060000Z
DTEND:20210401T070000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/31
DESCRIPTION:Title: Vertex Sparsification for Edge Connectivity\nby Bundit Laekhanukit (
SUFE) as part of SCMS Combinatorics Seminar\n\nAbstract: TBA\n\npw 121323\
n
LOCATION:https://researchseminars.org/talk/SCMSComb/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bernard Lidický (Iowa State University)
DTSTART:20210408T020000Z
DTEND:20210408T030000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/32
DESCRIPTION:Title: 11/4-colorability of subcubic triangle-free graphs\nby Bernard Lidic
ký (Iowa State University) as part of SCMS Combinatorics Seminar\n\n\nAbs
tract\nWe prove that every connected subcubic triangle-free graph except f
or two exceptional graphs on 14 vertices has fractional chromatic number a
t most 11/4. This is a joint work with Zdenek Dvorak and Luke Postle.\n\np
w 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kenta Ozeki (Yokohama National University)
DTSTART:20210415T060000Z
DTEND:20210415T070000Z
DTSTAMP:20260422T225636Z
UID:SCMSComb/33
DESCRIPTION:by Kenta Ozeki (Yokohama National University) as part of SCMS
Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/SCMSComb/33/
END:VEVENT
END:VCALENDAR