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:20260404T110653Z
UID:SCMSComb/1
DESCRIPTION:Title: Basics on the hypergraph container method V\nby Hong Liu (Univ
ersity of Warwick) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nTh
is is a gentle introduction to basics of the hypergraph container method i
ntroduced independently by Balogh\, Samotij and Morris\, and Saxton and Th
omason. The method has seen numerous applications in extremal combinatoric
s and other related areas in the past decade. We will focus mostly on exam
ples\, illustrating how to apply this method on various types of problems.
\n\nTalk 5: In the last talk\, we sketch a few more applications of hyperg
raph container methods and variations of the method.\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv University)
DTSTART:20200611T070000Z
DTEND:20200611T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/2
DESCRIPTION:Title: Large deviations of triangle counts in the binomial random graph I
\nby Wojciech Samotij (Tel Aviv University) as part of SCMS Combinator
ics Seminar\n\n\nAbstract\nSuppose that $Y_1\, \\ldots \, Y_N$ are i.i.d.
(independent identically distributed) random variables and let $X = Y_1 +
… + Y_N$. The classical theory of large deviations allows one to accurat
ely estimate 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 re
ly on the fact that X is a linear function of the independent variables $Y
_1\, …\, Y_N.$ There has been considerable interest—both theoretical a
nd practical—in developing tools for estimating such tail probabilities
also when $X$ is a nonlinear function of the $Y_i$. One archetypal example
studied 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 de
viations and discuss the history of the large deviation problem for triang
le counts.\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Wojciech Samotij (Tel Aviv University)
DTSTART:20200618T070000Z
DTEND:20200618T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/3
DESCRIPTION:Title: Large deviations of triangle counts in the binomial random graph I
I\nby Wojciech Samotij (Tel Aviv University) as part of SCMS Combinato
rics Seminar\n\n\nAbstract\nSuppose that $Y_1\, \\ldots \, Y_N$ are i.i.d.
(independent identically distributed) random variables and let $X = Y_1 +
… + Y_N$. The classical theory of large deviations allows one to accura
tely estimate 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 r
ely 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 practical—in developing tools for estimating such tail probabilities
also when $X$ is a nonlinear function of the $Y_i$. One archetypal exampl
e studied by both the combinatorics and the probability communities is whe
n $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 f
or triangle 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://stable.researchseminars.org/talk/SCMSComb/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lina Li (University of Illinois at Urbana-Champaign)
DTSTART:20200625T020000Z
DTEND:20200625T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/4
DESCRIPTION:Title: Independent sets in middle two layers of Boolean lattice\nby L
ina Li (University of Illinois at Urbana-Champaign) as part of SCMS Combin
atorics Seminar\n\n\nAbstract\nIn recent decades\, independent sets in the
discrete hypercube has received a lot of attention from many notable rese
archers.\nThe classical result of Korshunov and Sapozhenko in 1983 counts
the number of independent sets in the hypercube\, and then shows that typi
cal independent sets are not far from the trivial construction.\nFor an od
d integer $n=2d-1$\, let $\\mathcal{B}(n\, d)$ be the subgraph of the hype
rcube induced by the two largest layers. \nOur new results describe the ty
pical structure of independent sets in $\\mathcal{B}(n\, d)$ and also give
precise asymptotics on the number of them.\nThe proofs use Sapozhenko's g
raph container lemma\, and a recently developed method of Jenssen and Perk
ins\, which combines Sapozhenko's graph container lemma with a classcal to
ol from statistical physics\, the cluster expansion for polymer models.\nT
his is a joint work with with Jozsef Balogh and Ramon I. Garcia.\n\nPasswo
rd 016801\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bojan Mohar (Simon Fraser University)
DTSTART:20200702T080000Z
DTEND:20200702T090000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/5
DESCRIPTION:Title: Can the genus of a graph be approximated?\nby Bojan Mohar (Sim
on Fraser University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\
nThe genus g(G) of a graph G is defined as the minimum genus of a surface
in which G can be embedded (drawn without crossings). Thomassen proved tha
t it is NP-hard to determine whether g(G) < k\, when the graph G and an in
teger k are given to us as the input. Robertson and Seymour (and the speak
er) proved that this problem is FPT (fixed-parameter tractable). However\,
it is wide open whether the value of g(G) can be approximated.\n\nThe spe
aker will give an overview of this problem\, describe underlying conjectur
es\, and present a complete solution for the case when the graph is dense.
The solution uses Szemeredi Regularity Lemma and a result on the genus of
quasi-random graphs.\n\nThis is joint work with Yifan Jing.\n\npassword 1
21323\n
LOCATION:https://stable.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:20260404T110653Z
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-
Champaign) as part of SCMS Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yufei Zhao (Massachusetts Institute of Technology)
DTSTART:20200806T020000Z
DTEND:20200806T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/7
DESCRIPTION:Title: Equiangular lines\, spherical two-distance sets\, and spectral gra
ph theory\nby Yufei Zhao (Massachusetts Institute of Technology) as pa
rt of SCMS Combinatorics Seminar\n\n\nAbstract\nSolving a longstanding pro
blem on equiangular lines\, we determine\, for each given fixed angle and
in all sufficiently large dimensions\, the maximum number of lines pairwis
e separated by the given angle. The answer is expressed in terms of spectr
al radii of graphs.\n\nGeneralizing to spherical two-distance sets\, we co
njecturally 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 r
esult in spectral graph theory: the adjacency matrix of a connected bounde
d degree graph has sublinear second eigenvalue multiplicity.\n\nJoint work
with Zilin Jiang\, Jonathan Tidor\, Yuan Yao\, and Shengtong Zhang (all M
IT)\n\npassword 111317\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zilin Jiang (Massachusetts Institute of Technology)
DTSTART:20200813T020000Z
DTEND:20200813T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/8
DESCRIPTION:Title: Negligible obstructions and Turán exponents\nby Zilin Jiang (
Massachusetts Institute of Technology) as part of SCMS Combinatorics Semin
ar\n\n\nAbstract\nThe conjecture on the realizability of rational exponent
s states that for every rational number r in (1\,2) there is a graph F suc
h that ex(n\, F) = Θ(n^r). In their beautiful work\, Bukh and Conlon reso
lved a weaker version of the conjecture\, where F is allowed to be a famil
y of graphs. Subsequent work has been focusing on narrowing this family do
wn to a single graph. We formulate a framework\, that is taking shape in r
ecent work\, to attack the conjecture\, and we showcase an application of
the framework to obtain infinitely many new Turán exponents.\n\nJoint wor
k with Tao Jiang and Jie Ma.\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oliver Janzer (University of Cambridge)
DTSTART:20200820T080000Z
DTEND:20200820T090000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/9
DESCRIPTION:Title: Rainbow Turán number of even cycles\nby Oliver Janzer (Univer
sity of Cambridge) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nTh
e rainbow Tur\\'an number $\\mathrm{ex}^*(n\,H)$ of a\ngraph $H$ is the ma
ximum possible number of edges in a properly\nedge-coloured $n$-vertex gra
ph with no rainbow subgraph isomorphic to\n$H$. We prove that for any inte
ger $k\\geq 2$\,\n$\\mathrm{ex}^*(n\,C_{2k})=O(n^{1+1/k})$. This is tight
and establishes 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 blow-ups\nof even cycles\, which can be used to disprove a conjecture
of Erd\\H os\nand Simonovits.\n\npassword 111317\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jaehoon Kim (KAIST)
DTSTART:20200910T070000Z
DTEND:20200910T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/10
DESCRIPTION:Title: Extremal density for sparse minors and subdivisions\nby Jaeho
on Kim (KAIST) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nWe pro
ve an asymptotically tight bound on the extremal density guaranteeing subd
ivisions of bounded-degree bipartite graphs with a separability condition.
As corollaries\, we answered several questions of Reed and Wood on embedd
ing sparse minors. In particular\, we prove that a graph with average degr
ee $(3/2+ o(1))t$ contains every $t$-vertex planar graph as a minor and th
is constant $3/2$ is best possible. This is joint work with John Haslegra
ve and Hong Liu.\n\npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Volec (Czech Technical University in Prague)
DTSTART:20200917T070000Z
DTEND:20200917T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/11
DESCRIPTION:Title: Non-bipartite k-common graphs\nby Jan Volec (Czech Technical
University 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-v
ertex complete graph is asymptotically minimized by a random coloring. Not
e that the case $k=2$ coincides with the notion of common graphs introduce
d in 1960s.\n\nWe construct the first examples of non-bipartite k-common g
raphs for $k\\ge3$\, which resolves a problem of Jagger\, Stovícek and Th
omason from 1996.\n\nThis is a joint work with Dan Kral\, Jon Noel\, Serge
y Norin and Fan Wei.\n\npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tao Jiang (Miami University)
DTSTART:20200924T020000Z
DTEND:20200924T030000Z
DTSTAMP:20260404T110653Z
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\nAbstra
ct\nA well-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 conse
cutive even lengths\, the shortest of which is at most twice the radius of
G.\n\nIn this talk\, we extend Verstraete's result for linear cycles in l
inear r-uniform hypergraphs\, where r\\geq 3.\nWe show that for each k\\ge
q 2\, there exist constants c_1\,c_2 depending only on r such that every l
inear r-graph with average degree at least c_1 k contains linear cycles of
k consecutive even lengths and every linear r-graph with average degree a
t c_2k contains linear cycles of k consecutive lengths. For the even conse
cutive lengths case\, our bound on the shortest cycle length among the cyc
les obtained is tight\, which also yields improved upper bound on the line
ar Turan number of an even cycle of given length. For the consecutive leng
ths case\, our bound on the shortest cycle length is tight within a consta
nt factor.\n\nThe talk will focus on the tools used in establishing the re
sults. We think that these tools can find further applications to other ex
tremal problems on cycles in the hypergraph setting.\n\nThis is joint work
with Jie Ma and Liana Yepremyan.\n\npassword 061801\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kevin Hendrey (IBS)
DTSTART:20200827T070000Z
DTEND:20200827T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/13
DESCRIPTION:Title: Counting cliques in 1-planar graphs\nby Kevin Hendrey (IBS) a
s part of SCMS Combinatorics Seminar\n\n\nAbstract\nA 1-planar graph is a
graph which can be drawn in the plane so that every edge is crossed at mos
t once. It is well known that the maximum number of edges in a 1-planar gr
aph is 4n-8. It is natural consider extending this result to larger clique
s. We precisely determine the maximum number of cliques of any given size
in a 1-planar graph\, and also determine the family of 1-planar graphs whi
ch are extremal for this question. This is joint work with Pascal Gollin\,
Abhishek Methuku\, Casey Tompkins and Xin Zhang.\n\npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hongliang Lu (XJTU)
DTSTART:20200903T070000Z
DTEND:20200903T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/14
DESCRIPTION:Title: Co-degree condition for matchings in $k$-partite $k$-graphs\
nby Hongliang Lu (XJTU) as part of SCMS Combinatorics Seminar\n\n\nAbstrac
t\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 characterize those $H$ with $\\delta_{k-1}(H) \\geq n/2$ and with no p
erfect matching. As a consequence we give an affirmative answer to the fol
lowing question of R\\"odl and Ruci\\'nski: If $k$ is even or $n \\not\\eq
uiv 2 \\pmod 4$\, does $\\delta_{k-1}(H) \\geq n/2$ imply that $H$ has a p
erfect matching? We give an example indicating that it is not sufficient
to impose this degree bound on only two types of $(k-1)$-sets. For near pe
rfect matching\, we gave a tight sufficient condition in term of co-degree
\, which is also independently obtained by Han\, Zang and Zhao. Moreover\,
I would like to introduce several problems I am interested in.\n\npasswor
d 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/14/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Cranston (Virginia Commonwealth University)
DTSTART:20201015T020000Z
DTEND:20201015T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/15
DESCRIPTION:Title: Vertex Partitions into an Independent Set and a Forest with Each
Component Small\nby Daniel Cranston (Virginia Commonwealth University)
as part 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 part
itioned 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 bes
t possible. Hendrey\, Norin\, and Wood\nasked for the largest function g(a
\,b) such that if mad(G) < g(a\,b)\nthen V(G) has a partition into sets A
and B such 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 ind
ependent 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\nMatthew Yancey.\n\npassword 061801\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/15/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fan Wei (Princeton University)
DTSTART:20201022T020000Z
DTEND:20201022T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/16
DESCRIPTION:Title: Some variants of the graph removal lemma\nby Fan Wei (Princet
on University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nAmong
the numerous applications of the regularity lemma\, a classical one is the
graph removal lemma. It has applications in fields such as number theory
and theoretical computer science. For every fixed graph H\, the H-removal
lemma gives 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 huge bound in the quantitative estimate is necessary remains a big op
en question in graph theory. In this talk\, I will discuss some recent wor
ks on a strengthening of the usual graph removal lemma. This talk is ba
sed on some joint work with Jacob Fox.\n\npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/16/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jiaao Li (Nankai University)
DTSTART:20201029T070000Z
DTEND:20201029T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/17
DESCRIPTION:Title: Flows and Cycle Covers of Signed Graphs\nby Jiaao Li (Nankai
University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nFlow theo
ry of signed graphs was introduced by Bouchet as dual notion to local tens
ions of graphs embedded on non-orientable surfaces\, which generalized Tut
te's flow theory of ordinary graphs. Recently\, we prove that every flow-a
dmissible signed graph admits a nowhere-zero balanced $Z_2\\times Z_3$-flo
w. This extends Seymour's 6-flow theorem from ordinary graphs (which are s
igned graphs without unbalanced circuit) to long-barbell-free signed graph
s (which are signed graphs without vertex-disjoint unbalanced circuits). I
n this talk\, we will show how to apply this theorem to extend some classi
cal results on flow and cycle decomposition/cover\, due to Jaeger\, Fan\,
Alon-Tarsi\, etc.\, to some signed graphs. Those classical results may not
be tight for ordinary graphs\, whose expected improvements are known as T
utte's $5$-flow Conjecture\, Berge-Fulkerson Conjecture\, Cycle Double Cov
er Conjecture and Shortest Cycle Cover Conjecture. In contrast\, we shall
see that the signed analogies of those classical results are indeed sharp
for certain signed graphs.\n\npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hao Huang (Emory University)
DTSTART:20201008T020000Z
DTEND:20201008T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/18
DESCRIPTION:Title: Covering cubes by hyperplanes\nby Hao Huang (Emory University
) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nNote that the verti
ces of the $n$-dimensional cube $\\{0\, 1\\}^n$ can be covered by two affi
ne hyperplanes $x_1=1$ and $x_1=0$. However if we leave one vertex uncover
ed\, then suddenly at least $n$ affine hyperplanes are needed. This was a
classical result of Alon and F\\"uredi\, followed from the Combinatorial N
ullstellensatz.\n\nIn this talk\, we consider the following natural genera
lization of the Alon-F\\"uredi theorem: what is the minimum number of affi
ne hyperplanes such that the vertices in $\\{0\, 1\\}^n \\setminus \\{\\ve
c{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
hyperplanes is needed for $k=3$\, using a punctured version of the Combina
torial Nullstellensatz. We also develop an analogue of the Lubell-Yamamoto
-Meshalkin inequality for subset sums\, and solve the problem asymptotical
ly for fixed $n$ and $k \\rightarrow \\infty$\, and pose a conjecture for
fixed $k$ and large $n$.\n\nJoint work with Alexander Clifton (Emory Unive
rsity).\n\npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jie Han (University of Rhode Island)
DTSTART:20201105T070000Z
DTEND:20201105T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/19
DESCRIPTION:Title: $F$-factors in graphs with randomness conditions\nby Jie Han
(University of Rhode Island) as part of SCMS Combinatorics Seminar\n\n\nAb
stract\nThe celebrated Hajnal-Szemerédi Theorem is a cornerstone in extre
mal graph theory and has many applications and extensions. We will focus o
n a class of extensions where the host graph enjoys mild randomness condit
ions (e.g.\, does not have large independent set\, or contains a small amo
unt of random edges) and discuss some recent problems and developments.\n\
npassword 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Weifan Wang (Zhejing Normal University)
DTSTART:20201112T070000Z
DTEND:20201112T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/20
DESCRIPTION:Title: Simultaneous Colorings of Plane Graphs (In Chinese)\nby Weifa
n Wang (Zhejing Normal University) as part of SCMS Combinatorics Seminar\n
\n\nAbstract\nGiven a plane graph G = (V\, E\, F)\, we can define the vert
ex coloring for V\, the edge coloring for E\, the face coloring for F\, th
e total coloring for V∪E\, the coupled coloring for V∪F\, the edge-fac
e coloring for E∪F\, and the entire coloring V∪E∪F\, such that adjac
ent or incident elements have different colors. In this talk we shall give
a survey on these colorings and list colorings of plane graphs. Some rece
nt results and open problems about this direction are mentioned.\n\npasswo
rd 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luke Postle (University of Waterloo)
DTSTART:20201126T020000Z
DTEND:20201126T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/21
DESCRIPTION:Title: Further progress towards Hadwiger's conjecture\nby Luke Postl
e (University of Waterloo) as part of SCMS Combinatorics Seminar\n\n\nAbst
ract\nIn 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 Th
omason independently proved that every graph with no $K_t$ minor has avera
ge degree $O(t\\sqrt{\\log t})$ and hence is $O(t\\sqrt{\\log t})$-colorab
le. Recently\, Norin\, Song and I showed that every graph with no $K_t$
minor is $O(t(\\log t)^{\\beta})$-colorable for every $\\beta > 1/4$\, mak
ing the first improvement on the order of magnitude of the $O(t\\sqrt{\\lo
g 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 are $O(t (\\log \\log t)^{6})$-colorable.\n\npw 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Youngho Yoo (Georgia Institute of Technology)
DTSTART:20201210T020000Z
DTEND:20201210T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/22
DESCRIPTION:Title: Packing A-paths and cycles with modularity constraints\nby Yo
ungho Yoo (Georgia Institute of Technology) as part of SCMS Combinatorics
Seminar\n\n\nAbstract\nWe study the approximate packing-covering duality\,
also known as the Erdős-Pósa property\, of various families of paths an
d cycles with modularity constraints. Our main tool is a structure theorem
for undirected group-labelled graphs refining the flat wall theorem of Ro
bertson and Seymour\, and as a first consequence we obtain the Erdős-Pós
a property of cycles of length L mod m for any integer L and odd prime pow
er m.\nThis partially answers a question of Dejter and Neumann-Lara from 1
987 on characterizing all such integer pairs L and m. With some more work\
, we also 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 char
acterizing when A-paths of length L mod m satisfy the Erdős-Pósa propert
y. Joint work with Robin Thomas.\n\npw 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Chun-Hung Liu (Texas A&M University)
DTSTART:20201119T020000Z
DTEND:20201119T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/23
DESCRIPTION:Title: Clustered coloring for Hadwiger type problems\nby Chun-Hung L
iu (Texas A&M University) as part of SCMS Combinatorics Seminar\n\n\nAbstr
act\nHadwiger (Hajos and Gerards and Seymour\, respectively) conjectured t
hat \nthe vertices of every graph with no $K_{t+1}$ minor (topological mi
nor \nand odd minor\, respectively) can be colored with t colors such tha
t any \npair of adjacent vertices receive different colors. These conjectu
res \nare stronger than the Four Color Theorem and are either open or fals
e \nin general. A weakening of these conjectures is to consider clustered
\ncoloring which only requires every monochromatic component to have \nbo
unded size instead of size 1. It is known that t colors are still \nnecess
ary for the clustered coloring version of those three conjectures. \nJoint
with David Wood\, we prove a series of tight results about \nclustered co
loring on graphs with no subgraph isomorphic to a fixed \ncomplete biparti
te graph. These results have a number of applications. \nIn particular\, t
hey imply that the clustered coloring version of Hajos’ \nconjecture is
true for bounded treewidth graphs in a stronger sense: \n$K_{t+1}$ topolog
ical minor free graphs of bounded treewidth are clustered \nt-list-colorab
le. They also lead to the first linear upper bound for the \nclustered col
oring version of Hajos’ conjecture and the currently best \nupper bound
for the clustered coloring version of the Gerards-Seymour \nconjecture.\n\
npw 030332\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Xujin Chen (Chinese Academy of Sciences)
DTSTART:20201217T070000Z
DTEND:20201217T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/24
DESCRIPTION:Title: Ranking Tournaments with No Errors\nby Xujin Chen (Chinese Ac
ademy of Sciences) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nWe
examine the classical problem of ranking a set of players on the basis of
a set of\npairwise comparisons arising from a sports tournament\, with th
e objective of minimizing the total number of upsets\,\nwhere an upset occ
urs if a higher ranked player was actually defeated by a lower ranked play
er. This problem\ncan be rephrased as the so-called minimum feedback arc s
et problem on tournaments\, which arises in a rich variety\nof application
s and has been a subject of extensive research. We study this NP-hard prob
lem using\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$ contains no cycles\n(directed). A collection $C$ of cycles (with repet
ition allowed) 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 ever
y nonnegative\nintegral function ${w}$ defined on $A$\, the minimum total
weight of a feedback arc set is equal to the maximum\nsize of a cycle pack
ing. In this talk\, we\nwill discuss the characterization that a tournamen
t is cycle Mengerian if and only if it contains none of\nfour Möbius ladd
ers as a subgraph. (Joint work with Guoli Ding\, Wenan Zang\, and Qiulan Z
hao.)\n\npw 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guantao Chen (Georgia State University)
DTSTART:20201203T020000Z
DTEND:20201203T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/25
DESCRIPTION:Title: Graph Edge Coloring\nby Guantao Chen (Georgia State Universit
y) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nGraph edge colorin
g is a well established subject in the field of graph theory\, it is one o
f the basic combinatorial optimization problems: color the edges of a grap
h G with as few colors as possible such that each edge receives a color an
d adjacent edges\, that is\, different edges incident to a common vertex\,
receive different colors. The minimum number of colors needed for such a
coloring of G is called the chromatic index of G\, written $\\chi(G)$. By
a result of Holyer\, the determination of the chromatic index is an NP-har
d optimization problem. The NP-hardness gives rise to the necessity of usi
ng heuristic algorithms. In particular\, we are interested in upper bounds
for the chromatic index that can be efficiently realized by a coloring al
gorithm. In this talk\, we will start with the well-known Goldberg-Seymour
conjecture and its proof\, then talk about the recent development of reco
loring techniques and its applications to a number of classic problems in
critical class 2 simple graphs.\n\npw 030303\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zi-Xia Song (University of Central Florida)
DTSTART:20201231T020000Z
DTEND:20201231T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/26
DESCRIPTION:Title: Hadwiger’s Conjecture\nby Zi-Xia Song (University of Centra
l Florida) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nHadwiger
’s conjecture from 1943 states that for every integer $t\\ge 1$\, every
graph either can be t-colored or has a subgraph that can be contracted to
the complete graph on t + 1 vertices. This is a far-reaching generalizatio
n of the Four-Color Theorem and perhaps the most famous conjecture in grap
h theory. In this talk we will survey the history of Hadwiger’s conjectu
re and the main ideas of recent results.\n\npw 030303\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benjamin Gunby (Harvard University)
DTSTART:20210107T020000Z
DTEND:20210107T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/27
DESCRIPTION:Title: Upper Tails in Random Regular Graphs\nby Benjamin Gunby (Harv
ard University) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nFix a
graph K. What is the probability that a sparse random regular graph conta
ins many more copies of K than expected?\n\npw 030303\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pinyan Lu (Shanghai University of Finance and Economics)
DTSTART:20201224T070000Z
DTEND:20201224T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/28
DESCRIPTION:Title: Classifying Computational Counting Problems\nby Pinyan Lu (Sh
anghai University of Finance and Economics) as part of SCMS Combinatorics
Seminar\n\n\nAbstract\nAbstract: The main theme of theoretical computer sc
ience is to classify various computational problems in terms of their inhe
rent computational difficulty. In this talk\, I will try to demonstrate th
is general theme by some cases study of my own research on the algorithms
and complexity for counting problems defined on graphs.\n\npw 030303\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hong Liu (University of Warwick)
DTSTART:20210114T070000Z
DTEND:20210114T080000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/29
DESCRIPTION:Title: A solution to Erdős and Hajnal’s odd cycle problem\nby Hon
g Liu (University of Warwick) as part of SCMS Combinatorics Seminar\n\n\nA
bstract\nIn 1981\, Erdős and Hajnal asked whether the sum of the reciproc
als of the odd cycle lengths in a graph with infinite chromatic number is
necessarily infinite. Let C(G) be the set of cycle lengths in a graph G an
d let C_odd(G) be the set of odd numbers in C(G). We prove that\, if G has
chromatic 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
perhaps 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 t
his problem\, solving it with methods that apply to a wide range of sequen
ces in addition to the powers of 2.\n\nFinally\, we use our methods to sho
w that\, for every k\, there is some d so that every graph with average de
gree 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
Thomassen from 1984.\nJoint work with Richard Montgomery.\n\npw 061801\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joonkyung Lee (University College London)
DTSTART:20210121T110000Z
DTEND:20210121T120000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/30
DESCRIPTION:by Joonkyung Lee (University College London) as part of SCMS C
ombinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bundit Laekhanukit (SUFE)
DTSTART:20210401T060000Z
DTEND:20210401T070000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/31
DESCRIPTION:Title: Vertex Sparsification for Edge Connectivity\nby Bundit Laekha
nukit (SUFE) as part of SCMS Combinatorics Seminar\n\nAbstract: TBA\n\npw
121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Bernard Lidický (Iowa State University)
DTSTART:20210408T020000Z
DTEND:20210408T030000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/32
DESCRIPTION:Title: 11/4-colorability of subcubic triangle-free graphs\nby Bernar
d Lidický (Iowa State University) as part of SCMS Combinatorics Seminar\n
\n\nAbstract\nWe prove that every connected subcubic triangle-free graph e
xcept for two exceptional graphs on 14 vertices has fractional chromatic n
umber at most 11/4. This is a joint work with Zdenek Dvorak and Luke Postl
e.\n\npw 121323\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kenta Ozeki (Yokohama National University)
DTSTART:20210415T060000Z
DTEND:20210415T070000Z
DTSTAMP:20260404T110653Z
UID:SCMSComb/33
DESCRIPTION:by Kenta Ozeki (Yokohama National University) as part of SCMS
Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://stable.researchseminars.org/talk/SCMSComb/33/
END:VEVENT
END:VCALENDAR