Student Seminar

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

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

Upper bounds on the bichromatic number of some 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

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

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

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