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
Mar 15, 2024, 14:00–15:00 GMT+8: MaxWenqiang Xu (Stanford University)
Multiplicative energy in additive combinatorics and its application to number theory
Venue: Room 110, Shanghai Center for Mathematical Sciences
In this talk I will introduce the multiplicative energy, starting with its original applications in classical problems in additive combinatorics, e.g. sum-product problems. Then I will introduce the random multiplicative function and talk about the recent application of multiplicative energy to its study.
Past Talks
Check past talks for the full list of past talks with all details.
Jan 4, 2024: Yifan Jing (Oxford)
Sidon sets and sum-product phenomena bilibili
Given natural numbers $s$ and $k$, we say that a finite set $X$ of integers is an additive $B_{s}[k]$ set if for any integer $n$, the number of solutions to the equation \[ n = x_1 + … + x_s, \] with $x_1, …, x_s$ lying in $X$, is at most $k$, where we consider two such solutions to be the same if they differ only in the ordering of the summands. We define a multiplicative $B_{s}[k]$ set analogously. These sets have been studied thoroughly from various different perspectives in combinatorial and additive number theory. In this talk, we will discuss sum-product phenomena for these sets. We show that there is either an exceptionally large additive $B_{s}[k]$ set, or an exceptionally large multiplicative $B_{s}[k]$ set, with $k \ll s$. This is joint work with Akshat Mudgal.
Dec 20, 2023: Richard Peng (CMU)
Learning Augmented B^{-}-Trees bilibili
Abstract: We study learning-augmented search trees via treaps with carefully designed priorities. The result is a simple search tree where the depth of each item is determined by its predicted weight $w_x$ via setting Cartesian tree priorities to $-\lfloor\log\log(1/w_x)\rfloor + U(0, 1)$. This method generalizes the learning-augmented BSTs [Lin-Luo-Woodruff ICML`22] from Zipfian distributions to arbitrary, possibly inaccurate, predictions. It also gives the first external memory data structure that can provably take advantage of localities in access sequences via online self-reorganizations.
Dec 18, 2023: Xiaofan Yuan (Arizona State University)
On Rainbow Thresholds bilibili
Abstract: Resolving a recent problem of Bell, Frieze, and Marbach, we establish the threshold result of Frankston-Kahn-Narayanan-Park in the rainbow setting. This is joint work with Jie Han.
Dec 13, 2023: Yan Wang (SJTU)
Vertex degree sums for perfect matchings in 3-uniform hypergraphs bilibili
Let $H_{n, n/3}^2$ be the 3-graph of order $n$, whose vertex set is partitioned into two sets $S$ and $T$ of size $\frac{1}{3}n+1$ and $\frac{2}{3}n -1$, respectively, and whose edge set consists of all triples with at least $2$ vertices in $T$. Suppose that $n$ is sufficiently large and $H$ is a 3-uniform hypergraph of order $n$ with no isolated vertex. Zhang and Lu [Discrete Math. 341 (2018), 748–758] conjectured that if $\deg(u)+\deg(v) > 2(\binom{n-1}{2}-\binom{2n/3}{2})$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a perfect matching or $H$ is a subgraph of $H_{n,n/3}^2$. We construct a counter-example to the conjecture. Furthermore, we prove that if $\deg(u)+\deg(v) > (\frac{3}{5}+c)n^2$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a perfect matching or $H$ is a subgraph of $H_{n,n/3}^2$. This result implies a result of Zhang, Zhao and Lu [Electron. J. Combin. 25 (3), 2018]. This is joint work with Yi Zhang.
Oct 18, 2023: H.A. Kierstead (Arizona State University)
Sparsity from a game theoretic perspective bilibili
Abstract: Nešetřil and Ossona de Mendez introduced the notion of graph classes with bounded expansion and the more general notion of nowhere-dense graph classes. These concepts generalize those of graph classes with bounded tree-width, minor-closed classes, bounded degree classes, etc. This classification is informative as many interesting properties of simple sparse classes are shared with more general classes, while results on the general classes can often be sharpened for simpler classes. Moreover, the Nešetřil-Ossona de Mendez formulation is remarkably robust; there are many apparently disparate notions that turn out to be equivalent.
In applications it is often useful to use characterizations due to Zhu of bounded-expansion or nowhere-dense classes in terms of the generalized coloring numbers $scol_r(G)$ of a graph $G$. These numbers had been introduced earlier by Yang and me to extend the classes of graphs known to have bounded generalized game coloring numbers. Zhu’s result implies that these are exactly the classes with bounded expansion. For each distance $r$, the strong $r$-coloring number $scol_r(G)$ is determined by an “optimal” ordering of the vertices of $G$. We study the question of whether it is possible to find a single “uniform” ordering that is “good” for all distances $r$. We show that the answer to this question is essentially “yes”. Our results give new characterizations of bounded-expansion and nowhere-dense graph classes.
Much of this talk will be on joint work with Jan van den Heuvel, Department of Mathe-matics, London School of Economics and Political Science.
Oct 13, 2023: Songling Shan (Auburn University)
Towards the Overfull Conjecture bilibili
Abstract: Let $G$ be a simple graph with maximum degree denoted as $\Delta(G)$. An overfull subgraph $H$ of $G$ is a subgraph satisfying the condition $|E(H)| > \Delta(G)\lfloor \frac{1}{2}|V(H)| \rfloor$. In 1986, Chetwynd and Hilton proposed the Overfull Conjecture, stating that a graph $G$ with maximum degree $\Delta(G)> \frac{1}{3}|V(G)|$ has chromatic index equal to $\Delta(G)$ if and only if it does not contain any overfull subgraph. The Overfull Conjecture has many implications. For example, it implies a polynomial-time algorithm for determining the chromatic index of graphs $G$ with $\Delta(G) > \frac{1}{3}|V(G)|$, and implies several longstanding conjectures in the area of graph edge colorings. In this paper, we make the first improvement towards the conjecture when not imposing a minimum degree condition on the graph: for any $0<\varepsilon \le \frac{1}{22}$, there exists a positive integer $n_0$ such that if $G$ is a graph on $n\ge n_0$ vertices with $\Delta(G) \ge (1-\varepsilon)n$, then the Overfull Conjecture holds for $G$. The previous best result in this direction, due to Chetwynd and Hilton from 1989, asserts the conjecture for graphs $G$ with $\Delta(G) \ge |V(G)|-3$.
Sept 25, 2023: Yifan Jing (Ohio State University)
Measure doubling for small sets in SO(3,R)
Abstract: Let $SO(3,R)$ be the 3D-rotation group equipped with the real-manifold topology and the normalized Haar measure $\mu$. Confirming a conjecture by Breuillard and Green, we show that if A is an open subset of $SO(3,R)$ with sufficiently small measure, then $\mu(A^2) > 3.99 \mu(A)$. This is joint work with Chieu-Minh Tran (NUS) and Ruixiang Zhang (Berkeley).
Sept 18, 2023: Patrice Ossona de Mendez (CNRS and Univ. of Charles)
Twin-width and permutations bilibili
Abstract: Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.
This is a joint work with Edouard Bonnet, Jaroslav Nesetril, Sebastian Siebertz, and Stephan Thomassé.
Aug 11, 2023: Rose McCarty (Princeton)
δ-boundedness
Abstract: There are many classical constructions of graphs that have arbitrarily large minimum degree, but no big bicliques. A class of graphs is “δ-bounded” if, essentially, it avoids all such constructions. We give an overview of this area, focusing on parallels with χ-boundedness. In particular, we’ll discuss some recent joint work with Xiying Du, António Girão, Zach Hunter, and Alex Scott which gives reasonably efficient bounding functions.
July 28, 2023: Thomas Karam (Oxford)
Small sunflowers and the structure of slice rank decompositions
Let $d\ge 3$ be an integer. We show that whenever an order-$d$ tensor admits $d+1$ decompositions according to Tao’s slice rank, if the linear subspaces spanned by the one-dimensional functions constitute a sunflower for each choice of special coordinate, then the tensor admits a decomposition where these linear subspaces are contained in the centers of these respective sunflowers. As an application, we deduce that for every nonnegative integer $k$ and every finite field $\mathbb{F}$, there exists an integer $C(d,k,|\mathbb{F}|)$ such that every order-$d$ tensor with slice rank $k$ over $\mathbb{F}$ admits at most $C(d,k,|\mathbb{F}|)$ decompositions with length $k$, up to a class of transformations that can be easily described.
July 14, 2023: Marcelo Campos（Oxford）
An exponential improvement to diagonal Ramsey video
Abstract: The Ramsey Number $R(k)$ is the minimum n such that every red/blue coloring of the edges of $K_n$ contains a monochromatic $K_k$. In this talk I will discuss a recent work where we show that \(R(k)\leq (4−c)^k,\) for some c>0. This is the first exponential improvement on the Erdős and Szekeres upper bound proved in 1935.
Joint work with Simon Griffiths (PUC - Rio, Brazil), Robert Morris (IMPA, Brazil) and Julian Sahasrabudhe (University of Cambridge, England).
Jun 19, 2023, 14:00 (UTC+8): Yi Zhao (Georgia State University)
Extremal results on multipartite graphs
Let $K_r(t)$ denote the complete r-partite graph with t vertices in each part.
Erdos and Simonovits (1971) characterized extremal graphs for $K_r(t)$ when $t\le 3$. We obtain a multipartite version of this result by considering the maximum number of edges in a $K_r(t)$-free k-partite graph with n vertices in each part. We obtain an exact result whenever k=r, $t\le 3$, and n is sufficiently large, upper and lower bounds that differ $O(n)$ in all cases. This is a joint work with Jie Han.
May 19, 2023: Marius Tiba (University of Oxford)
Erdős covering systems video
Abstract: Since their introduction by Erdős in 1950, covering systems (that is, finite collections of arithmetic progressions that cover the integers) have been extensively studied, and numerous questions and conjectures have been posed regarding the existence of covering systems with various properties. In particular, Erdős asked if the moduli can be distinct and all arbitrarily large, Erdős and Selfridge asked if the moduli can be distinct and all odd, and Schinzel conjectured that in any covering system there exists a pair of moduli, one of which divides the other. In 2015, Hough resolved Erdős minimum modulus problem. In 2018, Balister, Bollobás, Morris, Sahasrabudhe and Tiba resolved Schinzel’s conjecture and, in 2019, they resolved the Erdős and Selfridge problem in the square free case. In this talk, we discuss these results and present a gentle exposition of the methods used. This talk is based on joint work with Balister, Bollobás, Morris and Sahasrabudhe.
May 6, 2023: Song, Zixia (University of Central Florida)
Coloring Graphs with Forbidden Minors
Hadwiger’s Conjecture from 1943 states that every graph with no $K_t$ minor is $(t-1)$-colorable; it remains wide open for all $t \ge 7$. For positive integers $t$ and $s$, let $\mathcal{K}^{-s}_t$ denote the family of graphs obtained from $K_t$ by removing $s$ edges. We say that a graph $G$ has no $\mathcal{K}^{-s}_t$ minor if it has no $H$ minor for every $H\in \mathcal{K}^{-s}_t$. Jakobsen in 1971 proved that every graph with no $\mathcal{K}^{-2}_7$ minor is 6-colorable. In this talk, we present our results that every graph with no $\mathcal{K}^{-4}_8$ minor is 7-colorable, and every graph with no $\mathcal{K}^{-6}_9$ minor is 8-colorable.
This is joint work with Michael Lafferty.
April 19, 2023, 15:00 UTF+8: Xizhi Liu (University of Warwick)
Turán problems in pseudorandom graphs
Abstract: A graph G is an (n, d, λ)-graph if it is a d-regular graph on n vertices and the second largest eigenvalue in absolute value of its adjacency matrix is λ. Given a graph F, we will talk about the problem of determining the densest possible (n, d, λ)-graph that contains no copy of F, and its relation with Ramsey problems. Based on joint work with Dhruv Mubayi and David Munhá Correia
April 7, 2023: Yiqiao Wang (Beijing University of Chinese Medicine)
Vertex Arboricity of Planar Graphs video
The vertex-arboricity $a(G)$ of a graph $G$ is the minimum number of subsets into which the set of vertices of $G$ can be partitioned so that each subset induces a forest. In this talk, we give a survey on the research progress of the vertex-arboricity and list vertex-arboricity of graphs. We show that every planar graph $G$ without adjacent 3-cycles has $a(G)\le 2$, which resolves a conjecture of Raspaud and Wang in 2008.
Mar 31, 2023, 10:00 UTF+8: Chong Shangguan (Shandong University)
Some problems in extremal set theory video slides
Consider an $r$-uniform hypergraph:
- it is called $t$-cover-free if for any $t+1$ distinct edges $A_1,\ldots,A_t,B$, it holds that $B\nsubseteq \cup_{i=1}^t A_i$;
- it is called $t$-union-free if for any two distinct subsets $\mathcal{A},\mathcal{B}$, each consisting of at most $t$ edges, it holds that $\cup_{A\in\mathcal{A}} A\neq \cup_{B\in\mathcal{B}} B$;
- it is called $t$-cancellative if for any $t+2$ distinct edges $A_1,\ldots,A_t,B,C$, it holds that $(\cup_{i=1}^t A_i)\cup B\neq (\cup_{i=1}^t A_i)\cup C$. Let $F_t(n,r),C_t(n,r),U_t(n,r)$ denote the maximum number of edges of these hypergraphs, respectively. In this talk, we will introduce the best known lower and upper bounds on these functions. Several interesting problems are left open.
Mar 10, 2023: Sam Spiro (Rutgers University)
Card Guessing with Feedback video
Abstract: Consider the following one player game: a deck with $m$ copies of $n$ different card types is randomly shuffled, and the player attempts to guess the cards sequentially as they are drawn. Each time a guess is made, some amount of “feedback” is given. For example, one could tell the player the true identity of the card they just guessed (the complete feedback model) or just whether they’re right or not (the partial feedback model). We consider the problem of estimating the maximum and minimum number of correct guesses the player can guarantee in expectation for both of these models. We also consider variants of these problems, which end up having connections to increasing subsequences in random multiset permutations, as well as to Rock, Paper Scissors.
Feb 24, 2023, 15:00 UTF+8: Zhicong Lin (Shandong University)
Permanents and permutation statistics video slides
I will talk about my recent joint work with Shishuo Fu and Zhi-Wei Sun on permanent conjectures relating to Genocchi numbers of the first and second kinds as well as (binomial) Euler numbers. Various permutation statistics are at the heart of our approaches.
Feb 10, 2023: Xiaoyu He (Princeton University)
Two New Bounds for Deletion Codes video slides
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.
Dec 30, 2022: Yaojun Chen (Nanjing University)
Ramsey numbers concerning quadrilaterals video
Let $G_1,G_2,…,G_k$ be k given graphs. The Ramsey number $R(G_1,G_2,…,G_k)$ is the smallest integer N such that for any k-edge colorings of a complete graph $K_N$, $K_N$ contains a subgraph in color i which is isomorphic to $G_i$ for some $1\le i\le k$. In this talk, we will introduce some results and problems on the Ramsey numbers concerning quadrilaterals, that is, a cycle of length four. We will also talk about the main methods used to investigate these problems.
Dec 16, 2022: Yunkun Zhou (Stanford University)
On product sets of arithmetic progressions video slides
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.
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 video
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 slides
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 slides
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