Skip to the content.

This online seminar is organized by Ping Hu (SYSU), Yan Wang (SJTU), Hehui Wu (SCMS) and Qiqin Xie (SHU). We will run it every two weeks, and run student seminars in between.

Current Schedule

July 1, 2022, 14:00-15:00 (UTC+8): Xujun Liu (Xi’an Jiaotong-Liverpool University)

Monochromatic paths and cycles in 2-edge-coloured graphs with large minimum degree
zoom pw 061801

A graph $G$ arrows a graph $H$ if in every $2$-edge-colouring of G there exists a monochromatic copy of $H$. Schelp had the idea that if the complete graph $K_n$ arrows a small graph $H$, then every ‘dense’ subgraph of $K_n$ also arrows $H$, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large $n$, if $n=3t+r$ where $r \in {0,1,2} $ and $G$ is an $n$-vertex graph with $\delta(G) \ge (3n-1)/4$, then for every $2$-edge-colouring of $G$, either there are cycles of every length ${3,4,5,…,2t+r}$ of the same colour, or there are cycles of every even length ${4,6,8,…,2t+2}$ of the samecolour.

Our result is tight in the sense that no longer cycles (of length $>2t+r$ ) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large n, every $(3t-1)$-vertex graph $G$ with minimum degree larger than $3|V(G)|/4$ arrows the path $P_{2n}$ with $2n$ vertices. Moreover, it implies for sufficiently large $n$ the conjecture by Benevides, Łuczak, Scott, Skokan and White that for $n=3t+r$ where $r \in {0,1,2} $ and every n-vertex graph $G$ with $\delta(G) \ge 3n/4$ , in each $2$-edge-colouring of G there exists a monochromatic cycle of length at least $2t+r$.

This is a joint work with Balogh, Kostochka, and Lavrov.

July 15, 2022, 09:00-10:00 (UTC+8): Jinyoung Park (Stanford University)

Thresholds
zoom pw 121323

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

July 29, 2022: Yongtang Shi (Nankai University)

Aug 12, 2022: Zhouningxin Wang

Aug 26, 2022, 10:00-11:00 (UTC+8):: Richard Peng (University of Waterloo)

zoom pw 121323

Past Talks from this Semester

Check past talks for the full list of past talks with all details.

June 17, 2022: Bo Ning (Nankai University)

A spectral condition for cycles with consecutive lengths video

As the counterpart of classical theorems on cycles of consecutive lengths due to Bondy and Bollobás in spectral graph theory, Nikiforov proposed the following open problem in 2008: What is the maximum $C$ such that for all positive $\varepsilon<C$ and sufficiently large $n$, every graph $G$ of order $n$ with spectral radius $\rho(G)>\sqrt{\lfloor\frac{n^2}{4}\rfloor}$ contains a cycle of length $\ell$ for each integer $\ell\in[3,(C-\varepsilon)n]$. We prove that $C\geq\frac{1}{4}$ by a novel method, improving the existing bounds. Besides some novel ideas, our proof technique is partly inspirited by the recent research on Ramsey numbers of star versus large even cycles due to Allen, Łuczak, Polcyn and Zhang, and with aid of a powerful spectral inequality. (Join work with Binlong Li)

June 3, 2022: Ziqing Xiang (Academia Sinica/Southern University of Science and Technology)

Line graphs over the binary field video

Abstract: There are two natural ways to project the set of natural numbers to {0, 1}: (1) mapping 0 to 0 and all positive integers to 1; (2) mapping all even natural numbers to 0 and all odd natural numbers to 1. These two projections lead to two different definitions of line graphs of multigraphs (loops and parallel edges allowed), and we mainly focus on the latter one in this talk. We will discuss their forbidden subgraph characterization, edge clique partition, linear time reconstruction algorithm, and good vertex orderings. If time permits, we will also discuss their connections with Euler quadratic form, reflection groups and root systems.

May 20, 2022: Lina Li (University of Waterloo)

The chromatic number of triangle-free hypergraphs video

A classical result of Johansson showed that for any triangle-free graph $G$ with maximum degree $\Delta$, its chromatic number is $O(\Delta/\log\Delta)$. This result was later generalized to all rank 3 hypergraphs due to the work of Copper and Mubayi. In this talk, I will present a common generalization of the above results to all hypergraphs, and this is sharp apart from the constant. Moreover, our result implies, generalizes, and improves several earlier results on the chromatic number and also independence number of hypergraphs, while its proof is based on a different approach than prior works in hypergraphs (and therefore provides alternative proofs to them). In particular, as an application, we establish a bound on chromatic number of sparse hypergraphs in which each vertex is contained in few triangles, and thus extend results of Alon, Krivelevich and Sudakov and Cooper and Mubayi from hypergraphs of rank 2 and 3, respectively, to all hypergraphs.

This is joint work with Luke Postle.

May 6, 2022: Sophie Spirkl (University of Waterloo)

Counterexamples for chromatic and dichromatic number video slides

Abstract: I will present a counterexample to the following well-known conjecture: for every k, r, every graph G with clique number at most k and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least r. This is related to colouring and $\chi$-boundedness in digraphs.

Joint work with Alvaro Carbonero, Patrick Hompe, and Benjamin Moore.

Apr 22, 2022: Alexandr V. Kostochka (University of Illinois at Urbana-Champaign)

On sizes of 1-cross intersecting set pair systems video

Let ${(A_i,B_i)}_{i=1}^m$ be a set pair system. Füredi, Gyárfás and Király called it $1$-cross intersecting if the size of intersection of $A_i$ and $B_j$ is $1$ when $i$ and $j$ are distinct, and $0$ if $i=j$. They studied such systems and their generalizations, and in particular considered $m(a,b,1)$, the maximum size of a $1$-cross intersecting set pair system in which  $|A_i|\le a$ and $|B_i|\le b$ for all $i$.

Answering one of their questions, Holzman proved that if $a,b\ge 2$, then $m(a,b,1)\le (29/30)\binom{a+b}{a}$. He also conjectured that the factor $29/30$ in his bound can be replaced by $5/6$. The goal of this talk is to sketch a proof of this conjectured bound.

This is joint work with Grace McCourt and Mina Nahvi.

Apr 8, 2022: Ruonan Li (Northwestern Polytechnical University)

Properly colored cycles in edge-colored graphs and directed cycles in digraphs video

A graph is called properly colored if adjacent edges are of distinct colors. In this talk, we will introduce some results and problems on properly colored cycles from a view of relation between edge-colored graphs and directed graphs.

Mar 25, 2022: Haoran Luo (University of Illinois at Urbana-Champaign)

On the Maximum $F_5$-free Subhypergraphs of $G^3(n,p)$ video slides

Denote by $F_5$ the $3$-uniform hypergraph on vertex set ${1,2,3,4,5}$ with hyperedges ${123,124,345}$. Balogh, Butterfield, Hu, and Lenz proved that if $p > K \ln n /n$ for some large constant $K$, every maximum $F_5$-free subhypergraph of $G^3(n,p)$ is tripartite with high probability, and showed if $p_0 = 0.1\sqrt{\ln n} /n$, with high probability there exists a maximum $F_5$-free subhypergraph of $G^3(n,p_0)$ that is not tripartite. We sharpen the upper bound to be best possible up to a constant factor. We prove that when $p > C \sqrt{\ln n} /n $ for some large constant $C$, every maximum $F_5$-free subhypergraph of $G^3(n, p)$ is tripartite with high probability. In this talk, I will introduce the main technique we use to improve this bound.

This is a joint work with Igor Araujo and Jozsef Balogh.

Mar 11, 2022: Peter Van Hintum (Oxford)

Sharp stability of the planar Brunn-Minkowski inequality video

We’ll consider recent results concerning the stability of the classic Brunn-Minkowski inequality. In particular, we will look at the proof of sharp stability for sets in the plane. Assuming that the Brunn-Minkowski deficit $\delta=|A+B|^{\frac{1}{2}}/(|A|^\frac12+|B|^\frac12)-1$ is sufficiently small in terms of $t=|A|^{\frac{1}{2}}/(|A|^{\frac{1}{2}}+|B|^{\frac{1}{2}})$,  there exist homothetic convex sets $K_A \supset A$ and $K_B\supset B$ such that $\frac{|K_A\setminus A|}{|A|}+\frac{|K_B\setminus B|}{|B|} \le C t^{-\frac{1}{2}}\delta^{\frac{1}{2}}$. The key ingredient is to show for every $\epsilon,t>0$, if $\delta$ is sufficiently small then $|\operatorname{co}(A+B)\setminus (A+B)|\le (1+\epsilon)(|\operatorname{co}(A)\setminus A|+|\operatorname{co}(B)\setminus B|)$. This talk is based on joint work with Hunter Spink and Marius Tiba.

Feb 25, 2022: Sang-il Oum (Institute for Basic Science / KAIST)

Independent domination of graphs with bounded maximum degree video slides