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

You may also check our seminar schedule through

Current schedule

September 24th, 2020, 10:00 (UTC+8): Tao Jiang (Miami University)

Some degenerate hypergraph Turan problems
zoom password 061801

Given an r-uniform hypergraph H, the Turan number ex(n,H) is the maximum number of edges in an r-uniform hypergraph that does not contain H as a subgraph. When ex(n,H)=o(n^r), we will say that the problem is degenerate, mirroring the graph case.

In this talk, we will discuss some degenerate hypergraph Turan problems, particularly problems in which ex(n,H) is in the \Theta(n^{r-1}) range.

No seminar on October 1st & 8th, 2020 (Holiday break)

October 15th, 2020, 10:00 (UTC+8): Daniel Cranston (Virginia Commonwealth University)

Vertex Partitions into an Independent Set and a Forest with Each Component Small
zoom password 061801

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 22nd, 2020, 10:00 (UTC+8): Fan Wei (Princeton University)

October 29th, 2020, 15:00 (UTC+8): Jiaao Li (Nankai University)

Flows and Cycle Covers of Signed Graphs
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.

Past talks

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.

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)

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

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