This online seminar is organized by Hehui Wu (SCMS), Qiqin Xie (SCMS) and Ping Hu (SYSU).

You may also check our seminar schedule through researchseminars.org.

Current schedule

December 3rd, 2020, 10:00 (UTC+8): Guantao Chen (Georgia State University)

Graph Edge Coloring
zoom password 030303

Graph edge coloring is a well established subject in the field of graph theory, it is one of the basic combinatorial optimization problems: color the edges of a graph G with as few colors as possible such that each edge receives a color and 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 χ(G). By a result of Holyer, the determination of the chromatic index is an NP-hard optimization problem. The NP-hardness gives rise to the necessity of using heuristic algorithms. In particular, we are interested in upper bounds for the chromatic index that can be efficiently realized by a coloring algorithm. In this talk, we will start with the well-known Goldberg-Seymour conjecture and its proof, then talk about the recent development of recoloring techniques and its applications to a number of classic problems in critical class 2 simple graphs.

December 10th, 2020, 10:00 (UTC+8): Youngho Yoo (Georgia Institute of Technology)

zoom password 121323

December 17th, 2020, 15:00 (UTC+8): Xujin Chen (Chinese Academy of Sciences)

Ranking Tournaments with No Errors
zoom password 121323

We examine the classical problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament, with the objective of minimizing the total number of upsets, where an upset occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments, which arises in a rich variety of applications and has been a subject of extensive research. We study this NP-hard problem using structure-driven and linear programming approaches.

Let T=(V,A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set if T\F contains no cycles (directed). A collection C of cycles (with repetition allowed) is called a cycle packing if each arc e is used at most w(e) times by members of C. We call T cycle Mengerian if, for every nonnegative integral function w defined on A, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. In this talk, we will discuss the characterization that a tournament is cycle Mengerian if and only if it contains none of four Möbius ladders as a subgraph. (Joint work with Guoli Ding, Wenan Zang, and Qiulan Zhao.)

December 24rd, 2020, 15:00 (UTC+8): Pinyan Lu (SUFE)

zoom password 030303

December 31rd, 2020, 10:00 (UTC+8): Zi-Xia Song (University of Central Florida)

zoom password 030303

January 7th, 2021, 10:00 (UTC+8): Benjamin Gunby (Harvard University)

zoom password 030303

January 14th, 2021, 15:00 (UTC+8): Hong Liu (University of Warwick)

A solution to Erdős and Hajnal’s odd cycle problem

In 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 necessarily 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 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.
In 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 this problem, solving it with methods that apply to a wide range of sequences in addition to the powers of 2.
Finally, 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 Thomassen from 1984.
Joint work with Richard Montgomery.

Past talks

November 26th, 2020, 10:00 (UTC+8): Luke Postle (University of Waterloo)

Further progress towards Hadwiger’s conjecture video

abstract In 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 degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\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 are $O(t (\log \log t)^{6})$-colorable.

November 19th, 2020: Chun-Hung Liu (Texas A&M University)

Clustered coloring for Hadwiger type problems video

abstract Hadwiger (Hajos and Gerards and Seymour, respectively) conjectured that the vertices of every graph with no K_{t+1} minor (topological minor and odd minor, respectively) can be colored with t colors such that any pair of adjacent vertices receive different colors. These conjectures are stronger than the Four Color Theorem and are either open or false in general. A weakening of these conjectures is to consider clustered coloring which only requires every monochromatic component to have bounded size instead of size 1. It is known that t colors are still necessary for the clustered coloring version of those three conjectures. Joint with David Wood, we prove a series of tight results about clustered coloring on graphs with no subgraph isomorphic to a fixed complete bipartite graph. These results have a number of applications. In particular, they imply that the clustered coloring version of Hajos’ conjecture is true for bounded treewidth graphs in a stronger sense: K_{t+1} topological minor free graphs of bounded treewidth are clustered t-list-colorable. They also lead to the first linear upper bound for the clustered coloring version of Hajos’ conjecture and the currently best upper bound for the clustered coloring version of the Gerards-Seymour conjecture.

November 12th, 2020, 15:00 (UTC+8): Weifan Wang (Zhejing Normal University)

Simultaneous Colorings of Plane Graphs (In Chinese) video

Abstract Given a plane graph G = (V, E, F), we can define the vertex coloring 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 coloring 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 survey on these colorings and list colorings of plane graphs. Some recent results and open problems about this direction are mentioned.

November 5th, 2020: Jie Han (University of Rhode Island)

F-factors in graphs with randomness conditions video

Abstract The celebrated Hajnal-Szemerédi Theorem is a cornerstone in extremal graph theory and has many applications and extensions. We will focus on a class 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.

October 29th, 2020: Jiaao Li (Nankai University)

Flows and Cycle Covers of Signed Graphs video

Abstract Flow theory of signed graphs was introduced by Bouchet as dual notion to local tensions of graphs embedded on non-orientable surfaces, which generalized Tutte's flow theory of ordinary graphs. Recently, we prove that every flow-admissible 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 graphs without unbalanced circuit) to long-barbell-free signed graphs (which are signed graphs without vertex-disjoint unbalanced circuits). In this talk, we will show how to apply this theorem to extend some classical 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 Tutte's $5$-flow Conjecture, Berge-Fulkerson Conjecture, Cycle Double Cover 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.

October 22nd, 2020: Fan Wei (Princeton University)

Some variants of the graph removal lemma

Abstract Among 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 open question 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.

October 15th, 2020: Daniel Cranston (Virginia Commonwealth University)

Vertex Partitions into an Independent Set and a Forest with Each Component Small video and slides

Abstract For each integer k >= 2, we determine a sharp bound on mad(G) such that V(G) can be partitioned into sets I and F_k, where I is an independent set and G[F_k] is a forest in which each component has at most k vertices. For each k we construct an infinite family of examples showing our result is best possible. Hendrey, Norin, and Wood asked for the largest function g(a,b) such that if mad(G) < g(a,b) then V(G) has a partition into sets A and B such that mad(G[A]) < a and mad(G[B])<b. They specifically asked for the value of g(1,b), which corresponds to the case that A is an independent set. Previously, the only values known were g(1,4/3) and g(1,2). We find the value of g(1,b) whenever 4/3 < b < 2. This is joint work with Matthew Yancey.

October 8th, 2020: Hao Huang (Emory University)

Covering cubes by hyperplanes video and slides

Abstract Note that the vertices of the n-dimensional cube {0, 1}^n can be covered by two affine hyperplanes x_1=1 and x_1=0. However if we leave one vertex uncovered, then suddenly at least n affine hyperplanes are needed. This was a classical result of Alon and Füredi, followed from the Combinatorial Nullstellensatz. In this talk, we consider the following natural generalization of the Alon-Füredi theorem: what is the minimum number of affine hyperplanes such that the vertices in {0, 1}^n-{0} are covered at least k times, and 0 is uncovered? We answer the problem for k<=3 and show that a minimum of n+3 affine hyperplanes is needed for k=3, using a punctured version of the Combinatorial Nullstellensatz. We also develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and solve the problem asymptotically for fixed n and k->∞, and pose a conjecture for fixed k and large n. Joint work with Alexander Clifton (Emory University).

September 24th, 2020: Tao Jiang (Miami University)

Linear cycles of given lengths in linear hypergraphs video

Abstract A 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 consecutive even lengths, the shortest of which is at most twice the radius of G. In this talk, we extend Verstraete's result for linear cycles in linear r-uniform hypergraphs, where r\geq 3. We show that for each k\geq 2, there 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 consecutive 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 obtained is tight, which also yields improved upper bound on the linear Turan number of an even cycle of given length. For the consecutive lengths case, our bound on the shortest cycle length is tight within a constant factor. The 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. This is joint work with Jie Ma and Liana Yepremyan.

September 17th, 2020: Jan Volec (Czech Technical University in Prague)

Non-bipartite k-common graphs video, slides and poster

Abstract For a given integer k>=2, 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 complete graph is asymptotically minimized by a random coloring. Note that the case k=2 coincides with the notion of common graphs introduced in 1960s. We construct the first examples of non-bipartite k-common graphs for k>=3, which resolves a problem of Jagger, Stovícek and Thomason from 1996. This is a joint work with Dan Kral, Jon Noel, Sergey Norin and Fan Wei.

September 10th, 2020: Jaehoon Kim (KAIST)

Extremal density for sparse minors and subdivisions video and poster

Abstract We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a separability condition. As corollaries, we answered several questions of Reed and Wood on embedding sparse 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 constant 3/2 is best possible. This is joint work with John Haslegrave and Hong Liu.

September 3rd, 2020: Hongliang Lu (XJTU)

Co-degree condition for matchings in k-partite k-graphs video and poster

Abstract Let H be a k-partite k-graph with n vertices in each partition class, and let $\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 perfect matching. As a consequence we give an affirmative answer to the following question of Rödl and Ruciński: 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 impose this degree bound on only two types of (k-1)-sets. For near perfect 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.

August 27th, 2020: Kevin Hendrey (IBS)

Counting cliques in 1-planar graphs video and poster

Abstract A 1-planar graph is a graph which 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 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 which are extremal for this question. This is joint work with Pascal Gollin, Abhishek Methuku, Casey Tompkins and Xin Zhang.

August 20th, 2020: Oliver Janzer (University of Cambridge)

Rainbow Turán number of even cycles video, slides and poster

Abstract The rainbow Turán number ex\*(n,H) of a graph H is the maximum possible number of edges in a properly edge-coloured n-vertex graph with no rainbow subgraph isomorphic to H. We prove that for any integer k>= 2, ex\*(n,C_{2k})=O(n^{1+1/k}). This is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstraete. We use the same method to prove several other conjectures in various topics. For example, we give an upper bound for the Turán number of the blow-ups of even cycles, which can be used to disprove a conjecture of Erdős and Simonovits.

August 13th, 2020: Zilin Jiang (Massachusetts Institute of Technology)

Negligible obstructions and Turán exponents video, slides and poster

Abstract The conjecture on the realizability of rational exponents states 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 graphs. Subsequent work has been focusing on narrowing this family down to a single graph. We formulate a framework, that is taking shape in recent work, to attack the conjecture, and we showcase an application of the framework to obtain infinitely many new Turán exponents. Joint work with Tao Jiang and Jie Ma. https://arxiv.org/abs/2007.02975

August 6th, 2020: Yufei Zhao (Massachusetts Institute of Technology)

Equiangular lines, spherical two-distance sets, and spectral graph theory video, slides and poster

Abstract Solving 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 separated by the given angle. The answer is expressed in terms of spectral radii of graphs. Generalizing to spherical two-distance sets, we conjecturally relate the problem to a certain eigenvalue problem for signed graphs, and solve it in a number of cases. A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity. Joint work with Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang (all MIT) https://arxiv.org/abs/1907.12466 https://arxiv.org/abs/2006.06633

July 23 - 30th, 2020: Patrice Ossona de Mendez (Charles University; CAMS, CNRS/EHESS; Zhejiang Normal University)

A model theoretic approach to sparsity I - II

Abstract What does it mean for a structure to be _sparse_ or _dense_? What is the point of differentiating between sparse and dense structures? Is there an objective and essential boundary between sparse and dense structures? The aim of this talk is to address, at least partially, these questions, from the points of view of model theory, structural graph theory, and theoretical computer science.

July 16th, 2020: Bobo Hua (Fudan University)

Planar graphs with positive curvature video (in Chinese)

Abstract A curvature notion on CW complexes was introduced by Forman. In this talk, we classify the set of planar tessellations with positive Forman curvature. This is joint work with Yohji Akama, Yanhui Su, and Haohang Zhang.

July 9th, 2020: Yifan Jing (University of Illinois at Urbana-Champaign)

Structures of sets with minimum measure growth video and poster

Abstract Let G be a connected unimodular group equipped with a Haar measure $\mu_G$, and suppose A,B are nonempty measurable subsets of G. An inequality by Kemperman gives us mu_G(AB) \geq \min \{ \mu_G(A)+\mu_G(B), \mu_G(G)\}. We obtain characterizations of groups G, and sets A, B, such that the equality holds. This is the first general result of its kind in nonabelian continuous settings and, at the same time, provides a complete answer to a question asked by Kemperman in 1964. We also get near equality versions of the above result with uniform linear bound for connected compact groups, confirming conjectures made by Griesmer and by Tao. As an application, we obtain a measure expansion result for connected compact simple Lie groups. (Joint work with Chieu-Minh Tran)

July 2nd, 2020: Bojan Mohar (Simon Fraser University)

Can the genus of a graph be approximated? video, slides and poster

Abstract The 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 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) proved that this problem is FPT (fixed-parameter tractable). However, it is wide open whether the value of g(G) can be approximated. The speaker will give an overview of this problem, describe underlying conjectures, 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. This is joint work with Yifan Jing.

June 25th, 2020: Lina Li (University of Illinois at Urbana-Champaign)

Independent sets in middle two layers of Boolean lattice video, slides and poster

Abstract In recent decades, independent sets in the discrete hypercube has received a lot of attention from many notable researchers. The classical result of Korshunov and Sapozhenko in 1983 counts the number of independent sets in the hypercube, and then shows that typical independent sets are not far from the trivial construction. For an odd integer n=2d-1, let B(n, d) be the subgraph of the hypercube induced by the two largest layers. Our new results describe the typical structure of independent sets in B(n, d) and also give precise asymptotics on the number of them. The proofs use Sapozhenko's graph container lemma, and a recently developed method of Jenssen and Perkins, which combines Sapozhenko's graph container lemma with a classical tool from statistical physics, the cluster expansion for polymer models. This is a joint work with Jozsef Balogh and Ramon I. Garcia.

June 11 - 18th, 2020: Wojciech Samotij (Tel Aviv University)

Large deviations of triangle counts in the binomial random graph I - II

Abstract Suppose that Y_1, …, 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 accurately 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 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 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). The first talk of the series will give a very gentle introduction to the theory of large deviations and discuss the history of the large deviation problem for triangle counts. The second talk of the series will present a complete solution to the upper tail problem for triangle counts in G(n,p) that was obtained recently in a joint work with Matan Harel and Frank Mousset.

May 7th - June 4th, 2020: Hong Liu (University of Warwick)

Basics on the hypergraph container method I - V

Abstract This is a gentle introduction to basics of the hypergraph container method introduced independently by Balogh, Samotij and Morris, and Saxton and Thomason. The method has seen numerous applications in extremal combinatorics and other related areas in the past decade. We will focus mostly on examples, illustrating how to apply this method on various types of problems.

April 30th, 2020: Baoxuan Zhu (JSNU)

Positivity in combinatorics

April 16th - 23rd, 2020: Jinsong Xu (XJTLU)

Applications of Hodge theory in matroid theory I - II

April 9th, 2020: Xuding Zhu (ZJNU)

Coloring, sparseness and girth Video

April 2nd, 2020: Xiaolan Hu (CCNU)

A 4-choosable graph that is not (8 : 2)-choosable

March 26th, 2020: Binlong Li (NPU)

A Strengthening of Erdős-Gallai Theorem and Proof of Woodall’s Conjecture

March 19th, 2020: Jie Ma (USTC)

The number of critical subgraphs in k-critical graphs