This online seminar is organized by Ping Hu (SYSU), Jiaxi Nie (SCMS), 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

Dec 16, 2022, 14:00-15:00 (UTC+8): Yunkun Zhou (Stanford University)

On product sets of arithmetic progressions
zoom 891 9095 7929 pw 121323

We prove that the size of the product set of any finite arithmetic progression $\mathcal{A}\subset \mathbb{Z}$ satisfies $|\mathcal A \cdot \mathcal A| \ge \frac{|\mathcal A|^2}{(\log |\mathcal A|)^{2\theta +o(1)} } ,$ where $2\theta=1-(1+\log\log 2)/(\log 2)$ is the constant appearing in the celebrated Erd\H{o}s multiplication table problem. This confirms a conjecture of Elekes and Ruzsa from about two decades ago.

If instead $\mathcal{A}$ is relaxed to be a subset of a finite arithmetic progression in integers with positive constant density, we prove that $|\mathcal A \cdot \mathcal A | \ge \frac{|\mathcal A|^{2}}{(\log |\mathcal A|)^{2\log 2- 1 + o(1)}}.$ This solves the typical case of another conjecture of Elekes and Ruzsa on the size of the product set of a set $\mathcal{A}$ whose sum set is of size $O(|\mathcal{A}|)$.

Joint work with Max Wenqiang Xu.

Feb 10, 2022, 09:00-10:00 (UTC+8): Xiaoyu He (Princeton University)

Two New Bounds for Deletion Codes
zoom 891 6158 9255 pw 121323

Deletion channels, introduced by Levenshtein in the 60’s, are noisy channels that delete bits from the input. A (binary) $k$-deletion code of length n is a set $C$ of binary strings of length $n$ capable of correcting $k$ such errors, i.e. satisfying the property that no pair of elements of $C$ shares a common subsequence of length at least $n-k$. Let $D(n, k)$ be the size of the largest $k$-deletion code of length $n$. Two central problems are to determine (a) the order of $D(n, k)$ for constant $k$, and (b) the supremum of all $0<p<1$ such that $D(n, pn)$ grows exponentially in $n$ (the so-called “positive-rate threshold”). In this talk, we establish the first nontrivial lower bound for problem (a) when $k > 1$, improving the “greedy” lower bound for $D(n,k)$ by a logarithmic factor. We also prove the first nontrivial upper bound for problem (b), showing that $D(n,pn) = 2^{o(n)}$ for $p > 1/2 - 10^{-60}$. The proofs use a variety of techniques from extremal combinatorics including probabilistic methods and regularity.

Based on joint works with Noga Alon, Gabriela Bourla, Ben Graham, Venkatesan Guruswami, Noah Kravitz, and Ray Li.

Past Talks from this Semester

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

Dec 2, 2022: Allan Lo (University of Birmingham)

Cycle decompositions in k-uniform hypergraphs video

We show that $k$-uniform hypergraphs on $n$ vertices whose codegree is at least $(2/3 + o(1))n$ can be decomposed into tight cycles, subject to the trivial divisibility condition that every vertex degree is divisible by $k$. As a corollary, we show that such hypergraphs also have a tight Euler tour answering a question of Glock, Joos, Kühn and Osthus. This is joint work with Simón Piga and Nicolás Sanhueza-Matamala.

Nov 18, 2022: Fan Wei (Princeton University)

Graph limits and common graphs with arbitrarily large chromatic number

Graph limits is a recently developed powerful theory in studying graphs from a continuous perspective. In this talk, we will show how the perspective of graph limits helps with graph homomorphism inequalities and how to make advances in a common theme in extremal combinatorics: when does randomness give nearly optimal bounds? For example, we show this perspective recently helps us answer a question on Ramsey theory raised by Jagger-Stovicek-Thomason’96, Hatami-Hladky-Kral’-Norine-Razborov’12, Conlon-Fox-Sudakov’15, where they asked whether there are common graphs with arbitrarily large chromatic numbers. This is based on a joint work with Dan Kral’ and Jan Volec.

Nov 4, 2022, 14:00-15:00 (UTC+8): Jin, Xian’An (Xiamen University)

Partial-dual polynomials and signed intersection graphs

Abstract: Recently, Gross, Mansour and Tucker introduced the partial-dual polynomial of a ribbon graph as a generating function that enumerates all partial duals of the ribbon graph by Euler genus. To investigate the partial-dual polynomial one only needs to focus on bouquets, i.e., ribbon graphs with exactly one vertex. In this talk, we shall further show that the partial-dual polynomial of a bouquet essentially depends on the signed intersection graph of the bouquet rather than on the bouquet itself. We then give a characterization of when a bouquet has a planar partial dual in terms of its signed intersection graph. Finally we consider a conjecture posed by Gross, Mansour and Tucker that there is no orientable ribbon graph whose partial-dual polynomial has only one non-constant term, this conjecture is false and we give a characterization of when all partial duals of a bouquet have the same Euler genus. This is joint work with Qi Yan (Qi Yan, Xian’an Jin, Partial-dual polynomials and signed intersection graphs, Forum Math. Sigma 10 (2022) e69.).

Oct 21, 2022: Shichang Song (Beijing Jiaotong University)

Applications of nonstandard analysis to graphon theory video

Abstract: In 2006, Lovász and Szegedy introduced the notion of graphon. A graphon could be considered as a limit of a sequence of finite graphs. However, a graphon is not a graph but a symmetric measurable function from $[0,1]^2$ to $[0,1]$. In this talk, we use methods from nonstandard analysis to present a new construction of graphons. Take a hyperfinite set H. An internal graph on H is a graph whose edge set is an internal subset of H×H. We will build a correspondence between hyperfinite internal graphs and graphons. Graphons are not graphs, but internal graphs on H are indeed graphs.

Oct 7, 2022: Ilkyoo Choi (Hankuk University of Foreign Studies)

Relaxations of coloring squares of graphs video

Less than a year ago, the following two notions of relaxations of coloring squares of graphs were formally introduced by Petruššševski and Škrekovski, and by Fabrici, Lužar, Rindošová, and Soták: an odd $c$-coloring (resp. proper conflict-free $c$-coloring) of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing an odd number of times (resp. exactly once) on its neighborhood.

We will survey some results around these parameters and our contributions. In particular, we show that for $c\geq 5$, every graph $G$ with $mad(G)\leq\frac{4c}{c+2}$ has a proper conflict-free $c$-coloring, unless $G$ contains a $1$-subdivision of the complete graph on $c+1$ vertices. We also provide results when $c=4$ and for planar graphs with girth restrictions. Our results completely resolve Cranston’s conjecture in a much stronger form, and also improves upon results of Caro, PetrušNevski, and Škrekovski. This is joint work with Eun-Kyung Cho, Hyemin Kwon, and Boram Park.

Sept 23, 2022: Shiping Liu (University of Science and Technology of China)

Signed graphs and Nodal domain theorems for symmetric matrices video

Abstract: A signed graph is a graph whose edges are labelled by a signature. It serves as a simple model of discrete vector bundle. We will discuss nodal domain theorems for arbitrary symmetric matrices by exploring the induced signed graph structure. This is an extension of the nodal domain theorem of Davies, Gladwell, Leydold, and Stadler for symmetric matrices with non-positive off-diagonal entrices. With the fundamental concepts of balance and switching of signed graphs, our approach provides a more conceptual understanding of Fiedler’s results on eigenfunctions of acyclic matrices. This new viewpoint further leads to a lower bound estimate for the number of strong nodal domains which generalizes and improves previous results of Berkolaiko and Xu-Yau. This talk is based on a joint work with Chuanyuan Ge (USTC).

Sept 9, 2022: Jinxin Zhou (Beijing Jiaotong University)

On primitive 2-closed permutation groups of rank at most four

In this talk, I will discuss the characterization of the primitive 2-closed groups $G$ of rank at most four that are not the automorphism group of a graph or digraph, and we show that if the degree is at least 2402 then there are just two infinite families or $G\leq {\rm A\Gamma L}_1(p^d)$, the 1-dimensional affine semilinear group. To the best of our knowledge, these are the first known examples of non-regular 2-closed groups that are not the automorphism group of a graph or digraph. This is a joint work with Michael Giudici and Luke Morgan.

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

Maximum Flow and Minimum-Cost Flows in Almost-Linear Time video

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

Aug 12, 2022: Zhouningxin Wang (Université Paris Cité and Nankai University)

Density of $C_{-4}$-critical signed graphs video slides

A signed graph $(G, \sigma)$ is a graph $G$ together with a signature $\sigma: E(G) \to \lbrace +, -\rbrace$. A homomorphism of a signed graph $(G, \sigma)$ to another signed graph $(H, \pi)$ is a mapping from $V(G)$ to $V(H)$ such that the adjacency and the signs of closed walks are preserved. Given a signed graph $(G, \sigma)$, let $g_{ij}(G, \sigma)$ ($ij \in Z_2^2$) denote the length of a shortest non-trivial closed walk whose parity of the number of negative edges is equal to $i$ modulo $2$ and parity of the length is equal to $j$ modulo $2$. We observe that if $(G, \sigma)$ admits a homomorphism to $(H, \pi)$, then $g_{ij}(G, \sigma)\geq g_{ij}(H, \pi)$ for each $ij\in Z_2^2$. A signed graph $(G, \sigma)$ is $(H, \pi)$-critical if it satisfies that $g_{ij}(G, \sigma)\geq g_{ij}(H, \pi)$, and it admits no homomorphism to $(H, \pi)$ but each of its proper subgraphs does.

By a signed indicator construction, we first show that the $k$-coloring problem of graphs is captured by the $C_{\negthinspace\scriptscriptstyle -k}$-coloring problem of signed graphs. Then we prove that, except for one particular signed graph on $7$ vertices and $9$ edges, any $C_{\negthinspace\scriptscriptstyle -4}$-critical signed graph on $n$ vertices must have at least $\lceil\frac{4n}{3}\rceil$ edges. Moreover, for each value of $n\geq 9$, there exists a $C_{\negthinspace\scriptscriptstyle -4}$-critical signed graph on $n$ vertices with either $\lceil\frac{4n}{3}\rceil$ or $\lceil\frac{4n}{3}\rceil+1$ many edges. As an application to planar graphs, we conclude that every signed bipartite planar graphs of negative-girth at least $8$ admits a homomorphism to $C_{\negthinspace\scriptscriptstyle -4}$ and, furthermore, this bound is the best possible. This fits well into a larger framework of the study of analog of Jaeger-Zhang conjecture.

This is joint work with Reza Naserasr and Lan Anh Pham.

July 29, 2022: Yongtang Shi (Nankai University)

Planar Turán number of graphs video

One of the best known results in extremal combinatorics is Turan’s Theorem. Turan-type problems of graphs and hypergraphs are widely studied in last years. In this talk, we will report the recent progress on Turan-type problems when host graphs are planar graphs.

July 15, 2022: Jinyoung Park (Stanford University)

Thresholds slides

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 1, 2022: Xujun Liu (Xi’an Jiaotong-Liverpool University)

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

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.

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