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
May 12, 2023, 10:00-11:00 (UTC+8):Yisai Xue, Shanghai University
Anti-Ramsey number of matchings in r-partite r-uniform
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.
Past talks
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
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