Past Talks

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

Independent domination of graphs with bounded maximum degree video slides

abstract An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $\Delta=4$ or $\Delta\ge 6$, every connected $n$-vertex graph of maximum degree at most $\Delta$ has an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })(n-1)+1$. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-\frac{\Delta}{ \lfloor\Delta^2/4\rfloor+\Delta })n$. This is joint work with Eun-Kyung Cho, Jinha Kim, and Minki Kim.

Jan 10, 2022, 10:00-11:00: Jiaxi Nie (University of California San Diego)

Randomized Greedy Algorithm for Independent Sets in Regular Uniform Hypergraphs with Large Girth video

abstract In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $\alpha(G)\geq (f(d,r)-\epsilon(g,d,r))n$, where $\epsilon(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

Jan 3, 2022: Gu, Xiaofeng (University of West Georgia)

Some properties of (n, d, λ)-graphs and generalizations video

abstract A $d$-regular graph on $n$ vertices with the second largest absolute eigenvalue at most $\lambda$ is called an $(n, d, \lambda)$-graph. It is well known that an $(n, d, \lambda)$-graph for which $\lambda = \Theta(\sqrt{d})$ is a very good pseudorandom graph, behaving, in many aspects, like a truly random graph. In this talk, we present some properties of $(n, d, \lambda)$-graphs, in particular, we study graph toughness. The toughness $t(G)$ of a connected graph $G$ is defined to be the minimum of $|S|/c(G-S)$ taken over all proper vertex subset $S$ such that $G-S$ is disconnected, where $c(G-S)$ denotes the number of components of $G-S$. For any $(n, d, \lambda)$-graph, Alon proved that $t(G)>\frac{1}{3}(\frac{d^2}{d\lambda+\lambda^2}-1)$, through which, he showed that for every $t$ and $g$ there are $t$-tough graphs of girth strictly greater than $g$, thus disproved a conjecture of Chv\'atal on pancyclicity in a strong sense. Brouwer independently discovered that $t(G)>\frac{d}{\lambda}-2$, and he conjectured the lower bound can be improved slightly to $t(G)\ge \frac{d}{\lambda} - 1$. We filled the small gap and confirmed this 25-year-old conjecture. We will also discuss some generalizations and related problems.

Dec 27, 2021: Peter Bradshaw (Simon Fraser University)

Single-conflict colorings in degenerate graphs video slides

abstract We will consider single-conflict colorings, a variant of graph colorings in which each edge of a graph has a single forbidden color pair. We will walk through the history of this graph coloring variant, and we will show that for any d-degenerate simple graph, O(√d log n) colors are always enough for a single-conflict coloring. This answers a question of Dvořák, Esperet, Kang, and Ozeki for simple graphs (Journal of Graph Theory 2021). Joint work with Tomáš Masařík.

Dec 20, 2021: Fei Peng (National University of Singapore)

Coprime Mappings and Lonely Runners video

abstract The lonely runner conjecture can be stated as follows: for any n positive integers v1 < v2 < ... < vn there exists a real number t such that each vit is at least 1/(n+1) away from the nearest integer. In this paper we prove that this is true if vn < (2−ϵ)n. This is an approximate version of a natural next step for the study of the lonely runner conjecture suggested by Tao. The key ingredient in our proof is a result on coprime mappings. Let A and B be sets of integers. A bijection f: A→B is a coprime mapping if a and f(a) are coprime for every a∈A. We show that if A,B⊂[n] are intervals of length 2m where m=exp(Ω((loglog n)2)), then there exists a coprime mapping from A to B. This is based on joint work with Tom Bohman.

Dec 13, 2021: Jianfeng Hou (Fuzhou University)

On Min-Bisections of graphs video

abstract A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. The Min-Bisection problem, which is to find a bisection of a given graph with the minimum size, is prototypical to graph partitioning problems and has been arisen in numerous contexts. In this paper, we show that a graph G with n vertices and m edges has a bisection of size at most m/2-cn for some c>0 if G has small maximum degree; or G is sparse and has minimum degree at least 2 and no K2,l; or G has minimum degree at least 2 and girth at least 6. We also show that for any constant ε>0, there exists a graph G with n vertex, m=Θ(n3/2) edges and girth at least 5 such that each bisection of G has size at least (1/2-ε)m.

Dec 6, 2021: Shagnik Das (NTU)

Isomorphic bisections of cubic graphs video

abstract Graph partitioning is the division of a graph into two or more parts based on certain combinatorial conditions, and problems of this kind of have been studied extensively. In the 1990s, Ando conjectured that the vertices of every cubic graph can be partitioned into two parts that induce isomorphic subgraphs. Using probabilistic methods together with delicate recolouring arguments, we prove Ando's conjecture for large connected graphs. This is joint work with Alexey Pokrovskiy and Benny Sudakov.

Nov 29, 2021, 16:00-17:00 (UTC+8): Ross Kang (Radboud University)

Colouring graphs of bounded local density video

abstract What is the best upper bound on the chromatic number for graphs of given maximum degree Δ and given maximum local density -- that is, with neighbourhood subgraphs each inducing at most a certain edge density? This Ramsey-type problem has deep roots going back more than half a century, for example, to a question of Vizing from the 1960s on triangle-free graphs, corresponding to local density 0. I will give a quick survey of the history of this question, particularly for large Δ, including discussion of some selected related problems (such as the conjecture of Erdos and Nesetril). Then I will discuss some recent progress on this problem, with emphasis on the regime of dense (i.e. Θ(Δ)) local sparsity. This talk will touch on numerous joint works with, variously, Davies, Hurley, de Joannis de Verclos, Pirot, Sereni.

Nov 22, 2021, 14:00-15:00 (UTC+8): Guanghui Wang (Shandong University)

Applications of sublinear expanders video

abstract We will introduce the sublinear expander and cover some applications of sublinear expander. We prove that for any bipartite graph H, every H-free graph G with average degree d contains a clique immersion of order (1 − o(1))d, implying that Lescure and Meyniel’s conjecture holds asymptotically for graphs without fixed bipartite graph. We also mention the existence of cycles in hypercubes.

Nov 15, 2021: Qizhong Lin (Fuzhou University)

Ramsey numbers of 4-cycle versus books video

abstract A book Bn is a graph which consists of n triangles sharing a common edge. In this paper, we study Ramsey numbers of quadrilateral versus books. Previous results give the exact value of r(C4 ,Bn) for 1≤ n≤ 14. We aim to determine the exact value of r(C4 ,Bn) for infinitely many n. As a special case, we show r(C4,Bq2-q-2) = q2+q-1 for all prime powers q≥4. We will also consider a conjecture proposed by Fox, He and Wigderson (arXiv:2109.09205v1, 2021). Joint with Chunchao Fan, Tianyu Li and Xing Peng.

Nov 8, 2021: Tuan Tran (IBS, Korea)

Maximal 3-wise intersecting families video

abstract A family F of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from F has a common element, and moreover, no set can be added to F while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family, for k≥3. We resolve this problem for k=3 and n even and sufficiently large. This is joint work with Ben Lund, Kevin Hendrey, Casey Tompkins.

Nov 1, 2021: Yan Wang (SJTU)

Balanced subdivisions of a large clique in graphs with high average degree video

abstract In 1984, Thomassen conjectured that for every constant k ∈ N, there exists d such that every graph with average degree at least d contains a subdivision of a complete graph on k vertices in which each edge is subdivided the same number of times. Recently, Liu and Montgomery confirmed Thomassen's conjecture. In this talk, we show that for sufficiently large d, every n-vertex graph with average degree at least d contains a subdivision of a complete graph of size at least Ω(d1/2/log10n) in which each edge is subdivided the same number of times.

Oct 25, 2021: Bhargav Narayanan (Rutgers University)

Friendly Bisections of Random Graphs video slides

abstract We prove that with high probability, the random graph G(n,1/2) on an even number of vertices admits a partition of its vertex set into two parts of equal size in which n − o(n) vertices have more neighbours on their own side than across. This settles an old conjecture of Furedi from 1988, which also appears as Problem 91 in Green’s list of 100 open problems.

Oct 18, 2021: Shinya Fujita (Yokohama City University)

A short survey on properly colored connectivity of graphs video

abstract We consider edge-colored connected graphs. An edge-colored graph is called properly colored if no two adjacent edges share a color. We say that an edge-colored graph is properly connected, if between every pair of distinct vertices, there exists a properly colored path connecting them. In this talk, we focus on edge-colored graphs that are properly connected and some recent results in this topic will be reviewed.

Oct 11, 2021: Ruth Luo (UC San Diego)

A Dirac Theorem for hamiltonian hypergraphs video

abstract Dirac proved that every n-vertex graph with minimum degree at least n/2 contains a hamiltonian cycle. We prove an analogue for hypergraphs: we give exact bounds for the minimum degree of a uniform hypergraph that implies the existence of hamiltonian Berge cycles. This is joint work with Alexandr Kostochka and Grace McCourt.

Sept 27, 2021: Jinha Kim (Institute of Basic Science, Korea)

The homotopy type of the independence complex of ternary graphs video slides

abstract A graph is called a ternary graph if it has no induced cycle of length divisible by 3. We prove Engstr\"{o}m's conjecture that the independence complex of a ternary graph is either contractible or homotopy equivalent to a sphere. Our result strengthens a result by Zhang and Wu, which verifies a conjecture of Kalai and Meshulam about the total Betti number of the independence complex of ternary graphs.

Sept 20, 2021: Gexin Yu (College of William & Mary)

Sufficient conditions for 2-dimensional graph rigidity video

abstract A graph is rigid in Rd if one places the vertices of the graph in the Rd, in general position, there will be no simultaneous continuous motion of all the points, other than Euclidean congruences, that preserves the lengths of all the graph edges. In R2, Geiringer in 1927, and independently Laman in 1970, gave a nice combinatorial characterization of rigid graphs. Using another characterization, Lovasz and Yemini in 1982 showed that every 6-connected graph is rigid. We give two further sufficient connectivity conditions for a graph to be rigid. Our proofs surprisingly involve a discharging argument. This is based on a joint work with Xiaofeng Gu, Wei Meng, Martin Rolek, and Yue Wang.

Sept 13, 2021, 14:00-16:00 (UTC+8): Xuding Zhu (Zhejiang Normal University)

On 1-2-3 Conjecture video slides

abstract An edge-weighting vertex colouring of a graph G is a mapping f: E(G) → R such that for any edge uv of G, ∑ e ∈ E(u)f(e) ≠ ∑ e ∈ E(v) f(e). The well-known 1-2-3 conjecture asserts that any graph with no isolated edges has an edge-weighting vertex colouring using weights 1,2 and 3. The list version of this conjecture asserts that if each edge e is given a list L(e) of 3 real numbers as permissible weights, then there is an edge-weighting vertex colouring f using permissible weights for each edge e. In this talk, I will give a detailed sketch of the proof that if each edge e is given a list L(e) of 5 permissible weights, then there is an edge-weighting vertex colouring f using permissible weights from L(e) for each edge e.

July 29, 2021: Henry Liu (Sun Yat-sen University)

Highly connected subgraphs of graphs with given independence number video

abstract Let G be a graph on n vertices with independence number α. How large a k-connected subgraph must G contain? Such a k-connected subgraph cannot be guaranteed to have more than ⌈n/α⌉ vertices, since G might be the disjoint union of α near equal cliques. It turns out that if n is sufficiently large (n≥α2k+1 will do), then G always contains a k-connected subgraph on at least ⌈n/α⌉ vertices. What is the correct threshold for n for which this result is true? Previously with Shinya Fujita and Amites Sarkar in 2018, we determined the exact thresholds for n when α=2,3. In this talk, we shall present a new result for α=4. For general α, we also present an improvement on the bound n≥α2k+1. Finally, several open problems will be mentioned. Joint work with Shinya Fujita (Yokohama City University, Japan), Boram Park (Ajou University, South Korea), and Amites Sarkar (Western Washington University, USA).

July 22, 2021: Boram Park (Ajou University)

Decomposing planar graphs under degree restriction video

abstract Given a graph G, a decomposition of G is a partition of its edges. A graph is (d, h)-decomposable if its edge set can be partitioned into a d-degenerate graph and a graph with maximum degree at most h. For d ≤ 4, we are interested in the minimum integer hd such that every planar graph is (d,hd)-decomposable. It was known that h3 ≤ 4, h2 ≤ 8, and h1 = ∞. In this talk, we present a result that h4=1, h3=2, and 4 ≤ h2 ≤ 6. This is a joint work with Eun-Kyung Cho, Ilkyoo Choi, Ringi Kim, Tingting Shan, Xuding Zhu.

July 15, 2021: Andrew Treglown (University of Birmingham)

Extremal problems for multigraphs video

abstract An (n,s,q)-graph is an n-vertex multigraph in which every s-set of vertices spans at most q edges. Turan-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry posed the problem of determining the maximum of the product of the edge multiplicities in (n,s,q)-graphs. In this talk we will discuss recent progress on this problem, including a result that shows for infinitely many choices of (s,q), the solution is transcendental. This answers a question of Alon. This is joint work with Nick Day and Victor Falgas-Ravry.

July 8, 2021: Zhiyu Wang (Georgia Institute of Technology)

Polynomial χ-binding functions for t-broom-free graphs video

abstract For any positive integer t, a t-broom is a graph obtained from K1,t+1 by subdividing an edge once. In this paper, we show that, for graphs G without induced t-brooms, we have χ(G) = o(ω(G)t+1), where χ(G) and ω(G) are the chromatic number and clique number of G, respectively. When t=2, this answers a question of Schiermeyer and Randerath. Moreover, for t=2, we strengthen the bound on χ(G) to 7.5ω(G)2, confirming a conjecture of Sivaraman. For t ≥ 3 and {t-broom, Kt,t}-free graphs, we improve the bound to o(ω(G)t-1+2/(t+1)). Joint work with Xiaonan Liu, Joshua Schroeder and Xingxing Yu.

July 1, 2021: József Balogh (University of Illinois)

Improved upper bounds on the size of Sidon sets

abstract In this entry point into the subject, combining two elementary proofs, we decrease the gap between the upper and lower bounds by 0.2% in a classical combinatorial number theory problem. We show that the maximum size of a Sidon set of {1, 2,..., n} is at most √n+ 0.998n1/4 for sufficiently large n. The talk is based on joint work with Zoltán Füredi and Souktik Roy.

June 24, 2021: Zdeněk Dvořák (Charles University)

On generalized coloring numbers video

abstract Weak and strong coloring numbers are a generalization of the notion of graph degeneracy to longer distances.  We survey some interesting results and applications of these concepts.

June 17, 2021: Wenqiang Xu (Stanford University)

Discrepancy in Modular Arithmetic Progressions video

abstract Celebrated theorems of Roth and of Matoušek and Spencer together show that the discrepancy of arithmetic progressions in the first n positive integers is Θ(n1/4). We study the analogous problem in the Zn setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in Zn for all positive integer n. We further determine up to a constant factor the discrepancy of arithmetic progressions in Zn for many n. For example, if n=pk is a prime power, then the discrepancy of arithmetic progressions in Zn is Θ(n1/3+rk/(6k)), where rk ∈ {0,1,2} is the remainder when k is divided by 3. This solves a problem of Hebbinghaus and Srivastav.   Joint work with Jacob Fox and Yunkun Zhou. 

June 8, 2021: Baogang Xu (Nanjing Normal University)

On coloring of graphs of girth 2l+1 without longer odd holes slides
Round the World Relay in Combinatorics

abstract A hole is an induced cycle of length at least 4. Let l≥2 be a positive integer, let Ĝl denote the family of graphs which have girth 2l+1 and have no holes of odd length at least 2l+3, and let G ∈ Ĝl. For a vertex u ∈ V(G) and a nonempty set S ⊆ V(G), let d(u,S) = min{d(u,v) : v∈S}, and let Li(S)={u∈V(G) and d(u,S)=i} for any integer i≥0. We show that if G[S] is connected and G[Li(S)] is bipartite for each i∈{1,…,l-1}, then G[Li(S)] is bipartite for each i>0, and consequently χ(G)≤4, where G[S] denotes the subgraph induced by S. For a graph G∈ Ĝ2, we show that χ(G)≤3 if G induces no two cycles of length 5 sharing edges. Let θ+ be the graph obtained from the Petersen graph by removing two adjacent vertices. We show that if G ∈ Ĝ2 is 3-connected and has no unstable 3-cutset, then G does not induce θ+. As a corollary, minimal non-3-colorable graphs of Ĝ2 induce no θ+. This is a joint work with Di Wu and Yian Xu.

June 3, 2021: Xiaofan Yuan (Georgia Institute of Technology)

Rainbow matchings for 3-unifrom hypergraphs video and slides

abstract Kuhn, Osthus and Treglown and, independently, Khan proved that if H is a 3-uniform hypergraph with n vertices such that n ∈ 3Z and large, and the minimum vertex degree of H is greater than {n-1\choose 2}-{2n/3\choose 2}, then H contains a perfect matching. Huang, Loh, and Sudakov showed that if, for 1≤ i≤ t, where t<n/(3k2), Fi ⊆ {[n]\choose k} and |Fi|>\binom{n}{k}-\binom{n-t+1}{k}, then {F1,...,Ft} admits a rainbow matching. We show that for n ∈ 3Z sufficiently large, if, for i∈ {1, ..., n/3}, Fi ⊆ {[n]\choose 3} and δ1(Fi)>{n-1\choose 2}-{2n/3\choose 2}, then {F1,..., Fn/3} admits a rainbow matching. This is joint work with Hongliang Lu and Xingxing Yu.

May 27, 2021: Huiqiu Lin (ECUST)

On sum of powers of graph eigenvalues: problems and progress video and slides

abstract In this talk, we will introduce some open problems and conjectures in the spectral graph theory, such as the Bollob\'as-Nikiforov's conjecture, the Brouwer's conjecture and the sum of squares of positive eigenvalues problem. In addition, progress will also be introduced.

May 20, 2021: Lutz Warnke (Georgia Institute of Technology)

Prague dimension of random graphs video and slides

abstract The Prague dimension of graphs was introduced by Nesetril, Pultr and Rodl in the 1970s: as a combinatorial measure of complexity, it is closely related to clique edges coverings and partitions. Proving a conjecture of Furedi and Kantor, we show that the Prague dimension of the binomial random graph is typically of order n/(log n) for constant edge-probabilities. The main new proof ingredient is a Pippenger-Spencer type edge-coloring result for random hypergraphs with large uniformities, i.e., edges of size O(log n). Based on joint work with He Guo and Kalen Patton, see https://arxiv.org/abs/2011.09459

May 13, 2021: Yijia Chen (Shanghai Jiaotong University)

Lovász meets Łoś and Tarski - understanding forbidden induced subgraphs by model theory video and slides

abstract The following result is attributed to Lovász. For every k\ge 1, there are graphs F_1, \ldots, F_{m_k} such that a graph G has a vertex cover of size at most k if and only if G has no (induced) subgraph isomorphic to any F_i. In this talk I will explain a proof of the above result using the Łoś-Tarski Theorem from model theory, and discuss its extensions to other graph properties/classes, e.g., graphs of bounded tree-depth and graphs of bounded shrub-depth. A simple yet vital step of our logic proof is to go from finite graphs to infinite graphs, without which, we show that the Łoś-Tarski Theorem fails on finite graphs. This is joint work with Jörg Flum.

May 6, 2021: Chieu-Minh Tran (University of Notre Dame)

Point-box incidences and logarithmic density of semilinear graphs video

abstract Zarankiewicz’s problem in graph theory asks to determine for each n and k the largest possible number of edges \|E\| in a  K_{k,k}-free bipartite graph G = (V_1, V_2; E) with \|V_1\|+\|V_2\|=n. Semialgebraic graphs enjoy stronger bounds than the usual Kovari-Sos-Turan bounds for general graphs, providing an abstract setting for the Szemerédi-Trotter theorem and related incidence bounds. We obtain even stronger bounds for semilinear graphs, demonstrate that these are close to being optimal, and apply them to show that the number of incidences between points and boxes with axis parallel sides on the plane whose incidence graph is K_{k,k}-free is almost linear. I will also discuss how these results are related to the notion of modularity in model theory. (Joint with Abdul Basit, Artem Chernikov, Sergei Starchenko, and Terence Tao).

April 29, 2021: Daniel Kráľ (Masaryk University)

Quasirandom combinatorial structures video and slides

abstract A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is. We will discuss quasirandom properties of other combinatorial structures, tournaments, permutations and Latin squares in particular, and present several recent results obtained using analytic tools of the theory of combinatorial limits. The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Adam Kabela, Ander Lamaison, Taísa Martins, Roberto Parente, Samuel Mohr, Jonathan A. Noel, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Fiona Skerman and Jan Volec.

April 22, 2021: Ander Lamaison Vidarte (Masaryk University)

Ramsey upper density of infinite graphs video and slides

abstract Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for wide classes of bipartite graphs and infinite factors.

April 15, 2021: Kenta Ozeki (Yokohama National University)

A survey on Hamiltonicity of graphs on surfaces video

abstract Since Whiteny proved that every 4-connected plane triangulation contains a Hamiltonian cycle, Hamiltonicity of graphs on surfaces has been widely studied. In this talk, we give a survey on the topic from the view of toughness and scattering number of graphs. We also introduce recent works.

April 8, 2021: Bernard Lidický (Iowa State University)

11/4-colorability of subcubic triangle-free graphs video

abstract We prove that every connected subcubic triangle-free graph except for two exceptional graphs on 14 vertices has fractional chromatic number at most 11/4. This is a joint work with Zdenek Dvorak and Luke Postle.

April 1, 2021: Bundit Laekhanukit (SUFE)

Vertex Sparsification for Edge Connectivity video and slides

abstract Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1+ϵ)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity-c mimicking networks with O(kc^4) edges exist and can be found in time m(clogn)O(c). We also give a separate algorithm that constructs such graphs with k⋅O(c)^{2c} edges in time mc^O(c)polylog(n). These results lead to the first data structures for answering fully dynamic offline c-edge-connectivity queries for c≥4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs. This is a jointwork with Parinya Chalermsook, Syamantak Das, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke and Daniel Vaz.

March 25, 2021: Xizhi Liu (University of Illinois at Chicago)

An approach to strong hypergraph stability video and slides

abstract I will talk about a method which provides a unified framework for many stability theorems that have been proved in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph problems to the simpler question of checking that a hypergraph H with large minimum degree that omits the forbidden structures is vertex-extendable. This means that if v is a vertex of H and H-v is a subgraph of the extremal configuration(s), then H is also a subgraph of the extremal configuration(s). In many cases vertex-extendability is quite easy to verify. Our method always yields an Andrásfai-Erdős-Sós type result, which says if H has large minimum degree, then it must be a subgraph of one of the extremal configurations. This is joint work with Dhruv Mubayi and Christian Reiher.

March 18, 2021: Long-Tu Yuan (ECNU)

The anti-Ramsey number for paths video

abstract A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. For a given graph H, the anti-Ramsey number AR(n,H) of H is the maximum number of colors in an edge-colored K_n such that K_n does not contain a copy of rainbow H. We determine the exactly anti-Ramsey number for paths. This confirms a conjecture posed by Erdős, Simonovits and Sós in 1970s.

March 11, 2021: Natasha Morrison (University of Victoria)

The Typical Structure of Sets with Small Sumset

abstract One of the central objects of interest in additive combinatorics is the sumset A+B= {a+b:a \in A, b \in B} of two sets A,B of integers. Our main theorem, which improves results of Green and Morris, and of Mazur, implies that the following holds for every fixed lambda > 2 and every k>(log n)^4: if omega goes to infinity as n goes to infinity (arbitrarily slowly), then almost all sets A of \[n\] with \|A\|=k and \|A + A\|<lambda k are contained in an arithmetic progression of length lambda k/2 + omega. This is joint work with Marcelo Campos, Mauricio Collares, Rob Morris and Victor Souza.

March 4, 2021: Jonathan Noel (University of Victoria)

Forcing Quasirandomness in Permutations video

abstract A striking result in graph theory is that the property of being quasirandom (i.e. resembling a random graph) can be characterised in several equivalent ways. One way is to say that the number of edges and the number of 4-cycles are both close to what one would expect in a random graph. Král’ and Pikhurko (2013) proved that quasirandom permutations are characterised by the densities of all permutations of length 4. We improve on this result by showing that there is a single expression consisting of a sum of densities of 8 permutations of length 4 whose value forces quasirandomness. Moreover, we characterize all permutation expressions of this type which force quasirandomness. Joint work with Timothy F. N. Chan, Daniel Král’, Yanitsa Pehova, Maryam Sharifzadeh and Jan Volec.

January 21, 2021: Joonkyung Lee (University College London)

On graph norms for complex-valued functions video

abstract For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once $H$ is paired with a $2$-edge-colouring $\alpha$ to assign conjugates. We say that $H$ is \emph{real-norming} (resp. \emph{complex-norming}) if $\|.\|_H$ (resp. $\|.\|_{H,\alpha}$) is a norm on the vector space of real-valued (resp. complex-valued) functions. These generalise the Gowers octahedral norms, a widely used tool in extremal combinatorics to quantify quasirandomness. We unify these two seemingly different notions of graph norms in real- and complex-valued settings. Namely, we prove that $H$ is complex-norming if and only if it is real-norming and simply call the property \emph{norming}. Our proof does not explicitly construct a suitable $2$-edge-colouring $\alpha$ but obtains its existence and uniqueness, which may be of independent interest. As an application, we give various example graphs that are not norming. In particular, we show that hypercubes are not norming, which resolves the last outstanding problem posed in Hatami's pioneering work on graph norms. Joint work with Sasha Sidorenko.

January 14, 2021: Hong Liu (University of Warwick)

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

abstract 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.

January 7, 2021: Benjamin Gunby (Harvard University)

Upper Tails in Random Regular Graphs video

abstract Fix a graph K. What is the probability that a sparse random regular graph contains many more copies of K than expected?

December 31, 2020: Zi-Xia Song (University of Central Florida)

Hadwiger’s Conjecture video

abstract Hadwiger's conjecture from 1943 states that for every integer t>=1, every graph either can be t-colored or has a subgraph that can be contracted to the complete graph on t + 1 vertices. This is a far-reaching generalization of the Four-Color Theorem and perhaps the most famous conjecture in graph theory. In this talk we will survey the history of Hadwiger's conjecture and the main ideas of recent results.

December 24, 2020: Pinyan Lu (SUFE)

Classifying Computational Counting Problems video and slides

abstract Abstract: The main theme of theoretical computer science is to classify various computational problems in terms of their inherent computational difficulty. In this talk, I will try to demonstrate this general theme by some cases study of my own research on the algorithms and complexity for counting problems defined on graphs.

December 17, 2020: Xujin Chen (Chinese Academy of Sciences)

Ranking Tournaments with No Errors video and slides

abstract 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 10, 2020: Youngho Yoo (Georgia Institute of Technology)

Packing A-paths and cycles with modularity constraints video and slides

abstract We study the approximate packing-covering duality, also known as the Erdős-Pósa property, of various families of paths and cycles with modularity constraints. Our main tool is a structure theorem for undirected group-labelled graphs refining the flat wall theorem of Robertson and Seymour, and as a first consequence we obtain the Erdős-Pósa property of cycles of length L mod m for any integer L and odd prime power m. This partially answers a question of Dejter and Neumann-Lara from 1987 on characterizing all such integer pairs L and m. With some more work, we also prove the Erdős-Pósa property of A-paths of length 0 mod p for prime p, resolving a recent question of Bruhn and Ulmer and thereby characterizing when A-paths of length L mod m satisfy the Erdős-Pósa property. Joint work with Robin Thomas.

December 3, 2020: Guantao Chen (Georgia State University)

Graph Edge Coloring video and slides

abstract 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.

November 26, 2020: 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 19, 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 12, 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 5, 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 29, 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 22, 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 15, 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 8, 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 24, 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 17, 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 10, 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 3, 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 27, 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 20, 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 13, 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 6, 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 - 30, 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 16, 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 9, 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 2, 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 25, 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 - 18, 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 7 - June 4, 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 30, 2020: Baoxuan Zhu (JSNU)

Positivity in combinatorics

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

Applications of Hodge theory in matroid theory I - II

April 9, 2020: Xuding Zhu (ZJNU)

Coloring, sparseness and girth Video

April 2, 2020: Xiaolan Hu (CCNU)

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

March 26, 2020: Binlong Li (NPU)

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

March 19, 2020: Jie Ma (USTC)

The number of critical subgraphs in k-critical graphs