This student seminar will be held online every two weeks on Friday, between the SCMS seminar. It is organized by the following five students, please contact us if you are interested in giving a talk.

Organizers:

Fan Chang, Shandong University,

Yaobin Chen, Fudan University,

Hongjun Ge, University of Science and Technology of China,

Chaoliang Tang, Fudan University,

Junxue Zhang, Nankai University.

### Dec 22， 2023, 10:00-11:00 (UTC+8):Longfei Fang, East China University of Science and Technology

**Uniqueness and Rapid Mixing in the Bipartite Hardcore Model**

Abstract:

Let ${\rm ex}(n,F)$ and ${\rm spex}(n,F)$ be the maximum size and maximum spectral radius of an $F$-free graph of order $n$, respectively. The value ${\rm spex}(n,F)$ is called the spectral extremal value of $F$. Nikiforov [J. Graph Theory 62 (2009) 362–368] gave the spectral Stability Lemma, which implies that for every $\varepsilon>0$, sufficiently large $n$ and a non-bipartite graph $H$ with chromatic number $\chi(H)$, the extremal graph for ${\rm spex}(n,H)$ can be obtained from the Tur'{a}n graph $T_{\chi(H)-1}(n)$ by adding and deleting at most $\varepsilon n^2$ edges. It is still a challenging problem to determine the exact spectral extremal values of many non-bipartite graphs. Given a graph $F$ and an integer $p\geq 2$, the edge blow-up of $F$, denoted by $F^{p+1}$, is the graph obtained from replacing each edge in $F$ by a $K_{p+1}$, where the new vertices of $K_{p+1}$ are all distinct. In this paper, we determine the exact spectral extremal values of the edge blow-up of all non-bipartite graphs and provide the asymptotic spectral extremal values of the edge blow-up of all bipartite graphs for sufficiently large $n$, which can be seen as a spectral version of the theorem on ${\rm ex}(n,F^{p+1})$ given by Yuan [J. Combin. Theory Ser. B 152 (2022) 379–398]. As applications, on the one hand, we generalize several previous results on ${\rm spex}(n,F^{p+1})$ for $F$ being a matching and a star for $p\geq 3$. On the other hand, we obtain the exact values of ${\rm spex}(n,F^{p+1})$ for $F$ being a path, a cycle and a complete graph. This is a joint work with Huiqiu Lin.

## Past talks

### Dec 7， 2023, 14:30-15:30 (UTC+8):Xiaoyu Chen, Nanjing University

**Uniqueness and Rapid Mixing in the Bipartite Hardcore Model**

slides video

Abstract:

Counting the number of independent sets in a bipartite graph (#BIS) is a central open problem in approximate counting. Its weighted variant is known as the bipartite hardcore model. In this work, we study the bipartite hardcore model in the high-temperature regime. We show a uniqueness threshold for bipartite graphs that has almost the same form as the tree uniqueness threshold for general graphs, except with degree bounds only on one side of the bipartition. Moreover, under this uniqueness threshold, we are able to give a nearly linear time sampling algorithm and show that the standard Glauber dynamics mix in polynomial time.

### Nov 24， 2023, 15:30-16:30 (UTC+8):Yixiao Zhang, Fuzhou University

**Hypergraphs with infinitely many extremal constructions**

slides video

Abstract:

We give the first exact and stability results for a hypergraph Tur'{a}n problem with infinitely many extremal constructions
that are far from each other in edit-distance. This includes an example of triple systems with Tur'{a}n density $2/9$, thus answering some questions posed by the third and fourth authors and Reiher about the feasible region of hypergraphs. Our results also provide extremal constructions whose shadow density is a transcendental number. Our novel approach is to construct certain multilinear polynomials that attain their maximum (in the standard simplex) on a line segment and then to use these polynomials to define an operation on hypergraphs that gives extremal constructions. This is joint work with Jianfeng Hou, Heng Li, Xizhi Liu and Dhruv Mubayi.

### Nov 17， 2023, 14:00-15:00 (UTC+8):Yueping Shi, Sun Yat-sen University

**Upper bounds on the bichromatic number of some graphs**

slides video

Abstract:

For a pair of nonnegative integers $k$ and $l$, a graph $G$ is {\em $(k, l)$-colorable} if its vertices can be partitioned into $k+l$ subsets $S_{1},\ldots,S_{k},C_{1},\ldots,C_{l}$ (possibly empty) such that each $S_{i}$ is an independent set and each $C_{j}$ is a clique in $G$. The {\em bichromatic number } $\chi^{b}(G)$ of $G$ is the least integer $r$ such that for all nonnegative integers $k$ and $l$ with $k+l=r$, $G$ is $(k, l)$-colorable. Let $\chi(G)$ and $\theta(G)$ denote the chromatic number and the clique covering number of $G$, respectively. There is a natural upper bound $\chi^{b}(G)\leq\chi(G)+\theta(G)-1$. Epple and Huang (2010) characterized all extremal graphs $G$ with $\chi^{b}(G) = \chi(G)+\theta(G)-1$. Let $r\geq 2$ be an integer, and let $G$ be a graph with clique number less than $r+1$. In this talk, we show that $\chi^{b}(G)\leq\theta(G)+r-1$ if $r=2$ or $3$, or if $r\geq4$ and $G$ is a line graph of a simple graph, and characterize all extremal graphs.

### Nov 10， 2023, 15:00-16:00 (UTC+8):Ziming Zhou, University of Shanghai for Science and Technology

**On the sum of the two largest signless Laplacian eigenvalues**

slides video

Abstract:

Let $G$ be a simple connected graph and let $S_k(G)$ be the sum of the first $k$ largest signless Laplacian eigenvalues of $G$.
It was conjectured by Ashraf, Omidi and Tayfeh-Rezaibe in 2013 that $S_k(G)\leq e(G)+\binom{k+1}{2}$ holds for $1\leq k\leq n-1$.
They gave a proof for the conjecture when $k = 2$,
but applied an incorrect key lemma.
Therefore, the conjecture is still open when $k = 2$.
In this paper, we prove that $S_2(G)< e(G)+3$ is true for any graphs which also confirm the conjecture when $k = 2$.

### Oct 27， 2023, 15:00-16:00 (UTC+8):Mingyang Guo, Xi‘an Jiaotong University

**Anti-Ramsey number of matchings in $3$-uniform hypergraphs**

slides video

Abstract:

Let $n,s,$ and $k$ be positive integers such that $k\geq 3$, $s\geq 3$ and $n\geq ks$. An $s$-matching $M_s$ in a $k$-uniform hypergraph is a set of $s$ pairwise disjoint edges. The anti-Ramsey number ar(n,k,$M_s$) of an $s$-matching is the smallest integer $c$ such that each edge-coloring of the $n$-vertex $k$-uniform hypergraph with exactly $c$ colors contains an $s$-matching with distinct colors. The value of ar(n,k,$M_s$) was conjectured by "Ozkahya and Young for all $n \geq sk$ and $k \geq 3$ in 2013. This conjecture was verified for all $n \geq sk+(s-1)(k-1)$ and $k \geq 3$ by Frankl and Kupavskii in 2019. We aim to determine the value of ar(n,3,$M_s$) for $3s \leq n < 5s-2$ in this paper. Namely, we prove that if 3s<n<5s-2 and $n$ is large enough, then ar(n,3,M_s)=ex(n,3,$M_{s-1}$)+2. Here ex(n,3,$M_{s-1}$) is the Tur'an number of an $(s-1)$-matching. Thus this result confirms the conjecture of "Ozkahya and Young for $k=3$, 3s<n<5s-2 and sufficiently large $n$. For $n=ks$ and $k\geq 3$, we present a new construction for the lower bound of ar(n,k,$M_s$) which shows the conjecture of "Ozkahya and Young is not true. In particular, for $n=3s$, we prove that ar(n,3,M_s)=ex(n,3,$M_{s-1}$)+5 for sufficiently large $n$. This is joint work with Hongliang Lu and Xing Peng.

## Current Schedule

### Dec 7， 2023 :Xiaoyu Chen, Nanjing University

**TBC**

Abstract:

TBC.

## Past talks

### Nov 24， 2023, 15:30-16:30 (UTC+8):Yixiao Zhang, Fuzhou University

**Hypergraphs with infinitely many extremal constructions**

Abstract:

We give the first exact and stability results for a hypergraph Tur'{a}n problem with infinitely many extremal constructions
that are far from each other in edit-distance. This includes an example of triple systems with Tur'{a}n density $2/9$, thus answering some questions posed by the third and fourth authors and Reiher about the feasible region of hypergraphs. Our results also provide extremal constructions whose shadow density is a transcendental number. Our novel approach is to construct certain multilinear polynomials that attain their maximum (in the standard simplex) on a line segment and then to use these polynomials to define an operation on hypergraphs that gives extremal constructions. This is joint work with Jianfeng Hou, Heng Li, Xizhi Liu and Dhruv Mubayi.

### Nov 17， 2023, 14:00-15:00 (UTC+8):Yueping Shi, Sun Yat-sen University

**Upper bounds on the bichromatic number of some graphs**

Abstract:

For a pair of nonnegative integers $k$ and $l$, a graph $G$ is {\em $(k, l)$-colorable} if its vertices can be partitioned into $k+l$ subsets $S_{1},\ldots,S_{k},C_{1},\ldots,C_{l}$ (possibly empty) such that each $S_{i}$ is an independent set and each $C_{j}$ is a clique in $G$. The {\em bichromatic number } $\chi^{b}(G)$ of $G$ is the least integer $r$ such that for all nonnegative integers $k$ and $l$ with $k+l=r$, $G$ is $(k, l)$-colorable. Let $\chi(G)$ and $\theta(G)$ denote the chromatic number and the clique covering number of $G$, respectively. There is a natural upper bound $\chi^{b}(G)\leq\chi(G)+\theta(G)-1$. Epple and Huang (2010) characterized all extremal graphs $G$ with $\chi^{b}(G) = \chi(G)+\theta(G)-1$. Let $r\geq 2$ be an integer, and let $G$ be a graph with clique number less than $r+1$. In this talk, we show that $\chi^{b}(G)\leq\theta(G)+r-1$ if $r=2$ or $3$, or if $r\geq4$ and $G$ is a line graph of a simple graph, and characterize all extremal graphs.

### Nov 10， 2023, 15:00-16:00 (UTC+8):Ziming Zhou, University of Shanghai for Science and Technology

**On the sum of the two largest signless Laplacian eigenvalues**

Abstract:

Let $G$ be a simple connected graph and let $S_k(G)$ be the sum of the first $k$ largest signless Laplacian eigenvalues of $G$.
It was conjectured by Ashraf, Omidi and Tayfeh-Rezaibe in 2013 that $S_k(G)\leq e(G)+\binom{k+1}{2}$ holds for $1\leq k\leq n-1$.
They gave a proof for the conjecture when $k = 2$,
but applied an incorrect key lemma.
Therefore, the conjecture is still open when $k = 2$.
In this paper, we prove that $S_2(G)< e(G)+3$ is true for any graphs which also confirm the conjecture when $k = 2$.

### Oct 27， 2023, 15:00-16:00 (UTC+8):Mingyang Guo, Xi‘an Jiaotong University

**Anti-Ramsey number of matchings in $3$-uniform hypergraphs**

slides video

Abstract:

Let $n,s,$ and $k$ be positive integers such that $k\geq 3$, $s\geq 3$ and $n\geq ks$. An $s$-matching $M_s$ in a $k$-uniform hypergraph is a set of $s$ pairwise disjoint edges. The anti-Ramsey number ar(n,k,$M_s$) of an $s$-matching is the smallest integer $c$ such that each edge-coloring of the $n$-vertex $k$-uniform hypergraph with exactly $c$ colors contains an $s$-matching with distinct colors. The value of ar(n,k,$M_s$) was conjectured by "Ozkahya and Young for all $n \geq sk$ and $k \geq 3$ in 2013. This conjecture was verified for all $n \geq sk+(s-1)(k-1)$ and $k \geq 3$ by Frankl and Kupavskii in 2019. We aim to determine the value of ar(n,3,$M_s$) for $3s \leq n < 5s-2$ in this paper. Namely, we prove that if 3s<n<5s-2 and $n$ is large enough, then ar(n,3,M_s)=ex(n,3,$M_{s-1}$)+2. Here ex(n,3,$M_{s-1}$) is the Tur'an number of an $(s-1)$-matching. Thus this result confirms the conjecture of "Ozkahya and Young for $k=3$, 3s<n<5s-2 and sufficiently large $n$. For $n=ks$ and $k\geq 3$, we present a new construction for the lower bound of ar(n,k,$M_s$) which shows the conjecture of "Ozkahya and Young is not true. In particular, for $n=3s$, we prove that ar(n,3,M_s)=ex(n,3,$M_{s-1}$)+5 for sufficiently large $n$. This is joint work with Hongliang Lu and Xing Peng.

### Oct 13， 2023, 17:00-18:00 (UTC+8):Jingyuan Zhang, Xiamen University

**On The Edge Reconstruction Of Six Digraph Polynomials**

slides video

Abstract:

Let $G=(V,E)$ be a digraph having no loops and no multiple arcs, with vertex set $V$ and arc set $E$. Denote the adjacency matrix and the vertex in-degree diagonal matrix of $G$ by $A$ and $D$. Set $f_1(G;x)=\det(xI-A), f_2(G;x)=\det(xI-D+A),f_3(G;x)=\det(xI-D-A),f_4(G;x)={\rm per}(xI-A), f_5(G;x)={\rm per}(xI-D+A),f_6(G;x)={\rm per}(xI-D-A)$, where $\det(X)$ and ${\rm per}(X)$ denote the determinant and the permanent of a square matrix $X$, respectively. In this paper, we consider a variant of the Ulam’s vertex reconstruction conjecture and the Harary’s edge reconstruction conjecture, and prove that, for any $1\leq i\leq 6$, $(|E|-|V|)f_i(G;x)+xf_i’(G;x)=\sum\limits_{e\in E}f_i(G-e;x)$, and hence $f_2(G;x)$ can be reconstructed from ${f_2(G-e;x)|e\in E(G)}$, and for any $i=1,3,4,5,6$, if $|V|\neq |E|$, $f_i(G;x)$ can be reconstructed from ${f_i(G-e;x)|e\in E(G)}$, and for $i=1,4$, if $|V|=|E|$, some counterexamples are given to show that $f_i(G;x)$ can not be determined by ${f_i(G-e;x)|e\in E(G)}$.

### Sep 27， 2023, 10:00-11:00 (UTC+8):Yuze Wu, University of Science and Technology of China

**Phase Transitions of Structured Codes of Graphs**

slides video

Abstract:

We consider the symmetric difference of two graphs on the same vertex set $[n]$, which is the graph on $[n]$ whose edge set consists of all edges that belong to exactly one of the two graphs. Let $\mathcal{F}$ be a class of graphs, and let $M_{\mathcal{F}}(n)$ denote the maximum possible cardinality of a family $\mathcal{G}$ of graphs on $[n]$ such that the symmetric difference of any two members in $\mathcal{G}$ belongs to $\mathcal{F}$. These concepts are recently investigated by Alon, Gujgiczer, K"{o}rner, Milojevi'{c}, and Simonyi, with the aim of providing a new graphic approach to coding theory. In particular, $M_{\mathcal{F}}(n)$ denotes the maximum possible size of this code. Existing results show that as the graph class $\mathcal{F}$ changes, $M_{\mathcal{F}}(n)$ can vary from $n$ to $2^{(1+o(1))\binom{n}{2}}$. We study several phase transition problems related to $M_{\mathcal{F}}(n)$ in general settings and present a partial solution to a recent problem posed by Alon et. al.

### Sep 15， 2023, 17:00-18:00 (UTC+8):Sihao Liu, Guangdong University of Technology

**Rainbow structures in a collection of graphs with degree conditions**

Abstract:

Let $\mathbf{G}={G_1,\ldots,G_s}$ be a collection of not necessarily distinct $n$-vertex graphs
with the same vertex set $V$. We use $\mathbf{\widetilde{G}}$ to denote an edge-colored multigraph
of $\mathbf{G}$ with $V(\mathbf{\widetilde{G}})=V$ and $E(\mathbf{\widetilde{G}})$ a multiset
consisting of $E(G_1),\ldots, E(G_s)$, and the edge $e$ of $\mathbf{\widetilde{G}}$ is colored by $i$
if $e\in E(G_i)$. A graph $H$ is {\em rainbow} in $\mathbf{G}$ if any two edges of $H$ belong to different
graphs of $\mathbf{G}$. We say that $\mathbf{G}$ is \emph{rainbow vertex-pancyclic} if each vertex of $V$
is contained in a rainbow cycle of $\mathbf{G}$ with length $\ell$ for every integer $\ell \in [3, n]$,
and that $\mathbf{G}$ is \emph{rainbow panconnected} if for any pair of vertices $u$ and $v$ of $V$
there exists a rainbow path of $\mathbf{G}$ with length $\ell$ joining $u$ and $v$ for every integer
$\ell\in [d_{\mathbf{\widetilde{G}}}(u,v),n-1]$.
In this talk, we study the existences of rainbow
spanning trees and rainbow Hamiltonian paths in $\mathbf{G}$ under the Ore-type conditions.
Moreover, we study the rainbow vertex-pancyclicity and rainbow panconnectedness, as well as the existence
of rainbow cliques in $\mathbf{G}$ under the Dirac-type conditions. We also give some examples to show
the sharpness of our results. This is joint work with Ping Li and Xueliang Li.

### July 21， 2023, 10:00-11:00 (UTC+8):Luyi Li, Nankai University

**Learn to solve dominating set problem with graph neural networks**

slides video

Abstract:

The idea using neural networks to solve combinatorial optimization problems has been shown to be effective and time-saving in recent years. Inspired by these studies, we train a neural network by DDQN to solve dominating set problem. To better capture the features and structure of the graph, we use a message passing network for the graph representation. We validate our model on graphs of different sizes, and even on real-world networks.

### June 25， 2023, 10:00-11:00 (UTC+8):Ji Zeng, University of California San Diego

**On higher dimensional point sets in general position**

slides video pw:anob

Abstract:

A finite point set in $R^d$ is in general position if no $d+1$ points lie on a common hyperplane. Let $α_d(N)$ be the largest integer such that any set of N points in Rd with no $d+2$ members on a common hyperplane, contains a subset of size $α_d(N)$ in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that $α_2(N) < N^{5/6}+o(1)$. In this paper, we also use the container method to obtain new upper bounds for αd(N) when d≥3. More precisely, we show that if $d$ is odd, then $α_d(N) < N^{1/2+1/2d}−1+o(1)$, and if $d$ is even, we have $α_d(N) < N^{1/2+1/d}−1+o(1)$. We also study the classical problem of determining the maximum number $a(d,k,n)$ of points selected from the grid $[n]^d$ such that no k+2 members lie on a $k$-flat. For fixed $d$ and $k$, we show that $a(d,k,n)≤O(n^{d/2⌊(k+2)/4⌋(1−1/2⌊(k+2)/4⌋d+1)})$, which improves the previously best known bound of $O(n^{d⌊(k+2)/2⌋})$ due to Lefmann when $k+2$ is congruent to 0 or 1 mod 4.

### June 23， 2023, 15:30-16:30 (UTC+8):Yongtao Li, Hunan University

**Structure and Spectral Radius of Graphs**

slides video
Abstract:

It is well-known that eigenvalues of graphs can be used to describe structural properties and parameters of graphs. The spectral extremal graph problem is an important research topic in extremal graph theory and algebraic graph theory. Let $\lambda (G)$ be the spectral radius of a graph $G$. A famous result in extremal spectral graph theory,
due to Nosal and Nikiforov, states that if $G$ is a triangle-free graph on $n$ vertices, then $\lambda (G) \le \lambda (K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil })$, equality holds if and only if $G=K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil }$. Later, Guiduli, and Nikiforov extended this result to $K_{r+1}$-free graphs for every integer $r\ge 2$. This is known as the spectral Tur'{a}n theorem. In 2021, Lin, Ning and Wu proved a refinement on this result for non-bipartite triangle-free graphs. For two non-adjacent vertices, by comparing the sums of weights of their neighbors, we provide alternative proofs for the result of Nikiforov and the result of Lin, Ning and Wu. The proof can be viewed as a spectral extension of Zykov’s symmetrization. Importantly, using local changes and switches on edges, our proof can allow us to extend the later result to non-r-partite $K_{r+1}$-free graphs. Our result refines the theorem of Nikiforov and it also can be viewed as a spectral version of a theorem of Brouwer.

### June 9， 2023, 10:00-11:00 (UTC+8):Jing Yu, Georgia Institute of Technology

**Large scale geometry of graphs of polynomial growth**

Abstract: In 1995, Levin and Linial, London, and Rabinovich conjectured that every connected graph $G$ of polynomial growth admits an injective homomorphism to the $n$-dimensional grid graph for some $n$. Moreover, they conjectured that if every ball of radius $r$ in $G$ contains at most $O(r^\rho)$ vertices, then one can take $n = O(\rho)$. Krauthgamer and Lee confirmed the first part of this conjecture and refuted the second in 2007. By constructing some finite expander graphs, they showed the best possible upper bound on $n$ is $O(\rho \log \rho)$. Prompted by these results, Papasoglu asked whether a graph $G$ of polynomial growth admits a coarse embedding into a grid graph. We give an affirmative answer to this question. Moreover, it turns out that the dimension of the grid graph only needs to be linear in the asymptotic growth rate of $G$, which confirms the original Levin–Linial–London–Rabinovich conjecture ``on the large scale.’‘ Besides, we find an alternative proof of the result of Papasoglu that graphs of polynomial growth rate $\rho < \infty$ have asymptotic dimension at most $\rho$. Furthermore, our proof works in the Borel setting and shows that Borel graphs of polynomial growth rate $\rho < \infty$ have Borel asymptotic dimension at most $\rho$. This is joint work with Anton Bernshteyn.

### May 12, 2023, 10:00-11:00 (UTC+8):Yisai Xue, Shanghai University

**Anti-Ramsey number of matchings in r-partite r-uniform**

slides video pw:f5ni
Abstract:

An edge-colored hypergraph is rainbow if all of its edges have different colors. Given two hypergraphs H and $G$, the anti-Ramsey number $ar(G,H)$ of $H$ in $G$ is the maximum number of colors in a coloring of the edges of $G$ so that there does not exist a rainbow copy of $H$. Li et al. determined the anti-Ramsey number of $k$-matchings in complete bipartite graphs. Jin and Zang showed the uniqueness of the extremal coloring. In this talk, as a generalization of these results, we determine the anti-Ramsey number $ar_r (K_{n_1 ,\dots,n_r} ,M_k)$ of $k$-matchings in complete $r$-partite $r$-uniform hypergraphs and show the uniqueness of the extremal coloring. Also, we show that $K_{k-1,n_2,\dots,n_r}$ is the unique extremal hypergraph for Turán number $ex_r (K_{n_1 ,\dots,n_r} ,M_k)$ and show that $ar_r (K_{n_1 ,\dots,n_r} ,M_k) = ex_r (K_{n_1 ,\dots,n_r} ,M_{k-1}) + 1$, which gives a multi-partite version result of Ozkahya and Young’s conjecture.

### Apr 28, 2023, 9:00-10:00 (UTC+8):Gang Yang, University of Shanghai for Science and Technology

**Gallai-Rado Numbers and Their Multiplicities**

Abstract:

Let $\mathcal{E}$ be a linear equation. The \emph{$r$-color Gallai-Rado number} for $\mathcal{E}$ is defined as the minimal integer $GR(\mathcal{E};r)$, if it exists, such that any $r$-coloring of $[1,n]$ with $n \geq GR(\mathcal{E};r)$
admits either a rainbow or monochromatic solution to $\mathcal{E}$. We provide exact values for $GR(x+y+b=z;r)$ for all $b \in \mathbb{Z}^+$. We also provide upper and lower bounds on the minimum number of rainbow and monochromatic solutions to $x+y=z$ over all $r$-colorings of $[1,n]$. In the process we provide a new lower bound on the minimum number of Schur triples in any 3-coloring of $[1,n]$. We also give upper and lower bounds for the strict Schur numbers. Lastly, we investigate the minimum number of monochromatic and rainbow solutions to $z > x + y $ over $r$-colorings of $[1,n]$.

### Apr 13, 2023, 9:00-10:00 (UTC+8):Guozhen Dai, Zhejiang University

**Tail Bounds on the Spectral Norm of Sub-Exponential Random Matrices**

slides video pw:3df2
Abstract:

Let $X$ be an $n\times n$ symmetric random matrix with independent but non-identically distributed entries. The deviation inequalities of the spectral norm of $X$ with Gaussian entries have been obtained by using the standard concentration of measure results in Gauss space which is unfortunately not suitable for the sub-Exponential case. This talk concentrates on upper tail bounds of $\Vert X\Vert$ with sub-Exponential entries. Our general method relies upon a crucial ingredient of a novel chaining argument that essentially depends on the distribution of coordinates of a point on the unit sphere. What makes this approach work is the particular structure of the sets used for the chaining.

### Mar 30, 2023, 16:30-17:30 (UTC+8):Heng Li, Fuzhou University

**A step towards a general density Corradi-Hajnal Theore**

slides video pw:rj54

Abstract:

For a nondegenerate $r$-graph $F$, large $n$, and $t$ in the regime $[0, c_{F} n]$, where $c_F>0$ is a constant depending only on $F$,
we present a general approach for determining the maximum number of edges in an $n$-vertex $r$-graph that does not contain $t+1$ vertex-disjoint copies of $F$.
In fact, our method results in a rainbow version of the above result and includes a characterization of the extremal constructions. Our approach applies to many well-studied hypergraphs (including graphs) such as the edge-critical graphs, the Fano plane, the generalized triangles, hypergraph expansions, the expanded triangles, and hypergraph books.Our results extend old results of Simonovits and Moon on complete graphs and can be viewed as a step towards a general density version of the classical Corr'{a}di–Hajnal Theorem.

### Mar 3, 2023, 9:00-10:00 (UTC+8):Meiqiao Zhang, Nanyang Technological University

**An Introdution to DP-color functions**

slides video pw:3df2
Abstract:

DP coloring is a recently introduced generalization of proper coloring that is to take all possible compatibility or repulsion relationships between the colors used
on every pair of adjacent vertices into consideration. The DP color function was then defined based on the counting of DP colorings, and turns out to have a direct but complex relationship with the chromatic polynomial. In this talk, I will introduce the basic definition and research status of DP color functions.

### Dec 23, 2022, 15:30-16:30 (UTC+8):Wenling Zhou, Shandong University

**Integer colorings with no rainbow k-term arithmetic progression**

Abstract:

In this talk, we study the rainbow Erd\H{o}s-Rothschild problem with respect to $k$-term arithmetic progressions. For a set of positive integers $S \subseteq [n]$,
an $r$-coloring of $S$ is \emph{rainbow $k$-AP-free} if it contains no rainbow $k$-term arithmetic progression. Let $g_{r,k}(S)$ denote the maximum number of rainbow $k$-AP-free $r$-colorings of $S$. For sufficiently large $n$ and fixed integers $r\ge k\ge 3$, we show that $g_{r,k}(S)\le g_{r,k}([n])$ for any proper subset $S\subset [n]$. Further, we prove that $\lim_{n\to \infty}g_{r,k}([n])/(k-1)^n = \binom{r}{k-1}$. Our result is asymptotically best possible and implies that, almost all rainbow $k$-AP-free $r$-colorings of $[n]$ use at most $k-1$ colors. This is joint work with Hao Lin and Guanghui Wang.

### Dec 9, 2022, 10:00-11:00 (UTC+8):Zhiqian Wang, Nankai University

**On circular Chromatic Number of Signed Planar Graphs of Girth At Least 5**

slides video pw:6i1z

Abstract:

In 2020, X. Zhu et al. introduced the concept of circular $r$-coloring of a signed graph $(G, \sigma)$, which is the extension of circular $r$-coloring brought up by Vince in 1988. Recently, J. Li et al. introduced the concept of circular $r$-flow as the dual notion of circular $r$-coloring in the sense of signed planar graphs, and several results of edge connectivity and circular flow index (equivalently, girth and circular chromatic number) were obtained. In this paper, we extend their results and prove that for every signed planar graph of girth at least 5 with $n$ vertices, the circular chromatic number is no more than $4-\frac{12}{5n-4}$. At the end, we propose two conjectures from our work about signed version of 3-flow conjecture. This paper is joint work with Jiaao Li.

### Nov 25, 2022, 16:00-17:00 (UTC+8):Jinye He, University of Oxford

**A non-uniform extension of Baranyai’s Theorem**

slides video pw:7l0u

Abstract:

A celebrated theorem of Baranyai states that when $k$ divides $n$, the family $K_n^k$ of all $k$-subsets of an $n$-element set can be partitioned into perfect matchings. In other words, $K_n^k$ is $1$-factorable. In this paper, we determine all $n, k$, such that the family $K_n^{\le k}$ consisting of subsets of $[n]$ of size up to $k$ is $1$-factorable, and thus extend Baranyai’s Theorem to the non-uniform setting. In particular, our result implies that for fixed $k$ and sufficiently large $n$, $K_n^{\le k}$ is $1$-factorable if and only if $n \equiv 0$ or $-1 \pmod k$. This talk is based on joint works with Hao Huang and Jie Ma.

### Nov 11, 2022, 10:00-11:00 (UTC+8):Lanchao Wang, Nanjing University

slides video pw:ajmy

Abstract:

Let $X$ and $Y$ be any two graphs of order $n$. The friends-and-strangers graph $\mathsf{FS}(X,Y)$ of $X$ and $Y$ is a graph with vertex set consisting of all bijections $\sigma :V(X) \mapsto V(Y)$, in which two bijections $\sigma$, $\sigma’$ are adjacent if and only if they differ precisely on two adjacent vertices of $X$, and the corresponding mappings are adjacent in $Y$. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let $Lollipop_{n-k,k}$ be a lollipop graph of order $n$ obtained by identifying one end of a path of order $n-k+1$ with a vertex of a complete graph of order $k$. In this talk, we give a sufficient and necessary condition for $\mathsf{FS}(Lollipop_{n-k,k},Y)$ to be connected for all $2\leq k\leq n$. And we determine, building off of a work of Alon, Defant, and Kravitz, a threshold condition for when $\mathsf{FS}(X,Y)$ is connected when $X$ and $Y$ are random graphs with different edge probabilities. This talk is based on joint works with Yaojun Chen.

### Oct 28, 2022, 10:00-11:00 (UTC+8):Henry Simmons, Lowa State University

Abstract:

For an $r$-uniform hypergraph $H$, let $\nu^{(m)}(H)$ denote the maximum size of a set $M$ of edges in $H$ such that every two edges in $M$ intersect in less than $m$ vertices, and let $\tau^{(m)}(H)$ denote the minimum size of a collection $C$ of $m$-sets of vertices such that every edge in $H$ contains an element of $C$. The fractional analogues of these parameters are denoted by $\nu^{*(m)}(H)$ and $\tau^{*(m)}(H)$, respectively. Generalizing a famous conjecture of Tuza (1990) on covering triangles in a graph, Aharoni and Zerbib (2022) conjectured that for every $r$-uniform hypergraph $H$, $\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil\frac{r+1}{2}\rceil$. In this talk, we prove bounds on the ratio between the parameters $\tau^{(m)}$ and $\nu^{(m)}$, and their fractional analogs.

### Oct 14, 2022, 10:00-11:00 (UTC+8):Xiutao Zhu, Nanjing University

video pw:dxab

### Sep 30, 2022, 10:00-11:00 (UTC+8):Zeyu Zheng, Fudan University

### Sep 16, 2022, 15:30-17:30 (UTC+8):Shengtong Zhang, Massachusetts Institute of Technology

### Aug 5, 2022, 15:30-17:30 (UTC+8):Chengfei Xie, Capital Normal University

### July 22, 2022, 15:00-17:00 (UTC+8):Jiangdong Ai, Royal Holloway, University of London

**Results on the Small Quasi-Kernel Conjecture**

slides video pw 62ye

### July 8, 2022, 10:00-12:00 (UTC+8):Yaobing Chen, Fudan University

**Orientations of Graphs with Forbidden out-degree Lists and Combinatorics of Eulerian-type polynomials**

slides video pw okdv

### June 24, 2022, 15:00-17:00 (UTC+8):Fan Chang，Shandong University

**A Brief Introduction to Fourier Analysis on the Boolean Cube: Advances and Challenges**

slides

### June 10, 2022, 09:00-11:30 (UTC+8): Jialin He, University of Science and Technology of China

**The minimum number of clique-saturating edges**

slides

### May 27, 2022, 10:00-11:00 (UTC+8): Chaoliang Tang, Fudan University

**Turán number of the linear 3-graph Crown**

slides

### May 13, 2022, 15:00-17:00 (UTC+8): Jie Hu, Paris-Saclay University

**Crux and long cycle in graphs**

slides

### Apr 29, 2022, 09:30-11:30 (UTC+8): Zhenyu Taoqiu, Nankai University

**Good pairs in digraphs**

slides video

### Apr 15, 2022, 09:30-11:30 (UTC+8): Jun Gao, University of Science and Technology of China

**On a conjecture of Bondy and Vince**

slides video pw 8nJu

### Apr 1, 2022, 15:00-17:00 (UTC+8): Donglei Yang, Shandong University

**A Ramsey–Turán theory for tilings in graphs**

slides

### Mar 18, 2022, 15:00-17:00 (UTC+8): Tianchi Yang, University of Science and Technology of China

**Non-repeated cycle lengths and Sidon sequences**

video pw 2MzF slides

### Mar 4, 2022, 10:00-12:00 (UTC+8): Wentao Zhang, Fudan University

**The Betti Number of the Independence Complex of Ternary Graphs**

video slides