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.

Current Schedule

Sep 15， 2023, 17:00-18:00 (UTC+8):Sihao Liu, Nankai University

Rainbow structures in a collection of graphs with degree conditions
slides video

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.

Past talks

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

Learn to solve dominating set problem with graph neural networks
Tencent meeting:434353301 pw:235711

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

slides

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

slides

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

slides video pw emyu

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