Combinatorics Seminar
Upcoming talks
Past talks
2022

Friday (Dec 16, 2022), 10:3011:20 pm: Weifan Wang (Zhejiang Normal University)
Arboricity and Partition video
Abstract(Click to expand)
For a positive integer $n$, the linear $n$arboricity of a graph $G$ is the least number $k$ such that $G$ can be edgepartitioned into $k$ forests, whose component trees are paths of length at most $n$. When $n$ is infinite, the corresponding parameter is called the linear arboricity of $G$. In this talk, we give a survey for the research progress about the arboricity, linear arboricity, linear $2$arboricity and other edgepartition problems of graphs. Some unsolved problems will be provided.

Thursday (Dec 15, 2022), 23 pm: Changhong Lu (East China Normal University)
A bridge between the coinweighing problem and the double resolving problem of graphs video
Abstract(Click to expand)
硬币称重问题（Coinweighing problems）是个经典的组合优化问题，其中一个经典形式为：给定$n$个硬币，假定真硬币的重量和假硬币的重量均已知，用弹簧称对硬币进行称重，用最少的称重次数将所有的假币找出来。图的$2$分辨集（double resolving problem）是Caceres 等人在2007年为了研究图的分辨集问题（resolving set problem）提出的一个工具性的新概念。最近，我们证明了超方体的$2$分辨集问题与硬币称重问题的等价关系，我们利用硬币称重问题的Lindström方法给出计算超方体和折叠超方体$2$分辨集问题的快速算法，给出了一些新结果，包括解决公开问题；反过来，$2$分辨集问题的图论结果也给硬币称重问题带来了一些新进展，比如$14$,$16$,$18$个硬币称重问题的新上界。

Thursday (Dec 8, 2022), 3:304:30 pm: Pan Peng (University of Science and Technology of China)
SublinearTime Algorithms for Max Cut and Unique Label Cover on Expanders
Abstract(Click to expand)
We give the first sublineartime algorithm for the Max Cut problem with nontrivial approximation guarantee for a natural class of graphs, i.e., expander graphs. Given query access to the adjacency list of such a graph with $m$ edges and conductance at least $\phi$, our algorithm runs in $\tilde{O}\left(\frac{m^{1/2+O(\varepsilon/\phi^2)}}{\phi^2}\right)$ time and provides a $(1/2+\varepsilon)$approximation to ${\rm MC}(G)$, the maximum fraction of the edges cut by a bipartition of $G$. We also give a sublineartime algorithm for the Unique Label Cover (also known as Unique Games) problem on expanders in the boundeddegree model. Previously, it was only known that the latter problem can be solved in polynomial time by using semidefinite programming. In contrast, our algorithms and analysis are based on spectral, random walk, and property testing techniques.

Thursday (Nov 24, 2022), 34 pm: Hongliang Lu (Xi'an Jiaotong University)
AntiRamsey number of matchings in $3$uniform hypergraphs video
Abstract(Click to expand)
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 antiRamsey number ${\rm ar}(n,k,M_s)$ of an $s$matching is the smallest integer $c$ such that each edgecoloring of the $n$vertex $k$uniform complete hypergraph with exactly $c$ colors contains an $s$matching with distinct colors. The value of ${\rm ar}(n,k,M_s)$ was conjectured by Ozkahya and Young (AntiRamsey number of matchings in hypergraphs, Discrete Math., 313 (2013), 23592364) for all $n \geq sk$ and $k \geq 3$. Frankl and Kupavskii (Two problems on matchings in set families  in the footsteps of Erdos and Kleitman, J. Combin. Theory ser. B, 138 (2019), 286313) verified this conjecture for all $n \geq sk+(s1)(k1)$ and $k \geq 3$. We aim to determine the value of ${\rm ar}(n,3,M_s)$ for $3s \leq n < 5s2$ in this paper. Namely, we prove that if $3s < n < 5s2$ and $n$ is large enough, then ${\rm ar}(n,3,M_s)={\rm ex}(n,3,M_{s1})+2$. Here ${\rm ex}(n,3,M_{s1})$ is the Turan number of an $(s1)$matching. Thus this result confirms the conjecture of Ozkahya and Young for $k=3$, $3s < n < 5s2$ and sufficiently large $n$. For $n=ks$ and $k\geq 3$, we present a new construction for the lower bound of ${\rm ar}(n,k,M_{s})$ which shows the conjecture by Ozkahya and Young is not true. In particular, for $n=3s$, we prove that ${\rm ar}(n,3,M_s)={\rm ex}(n,3,M_{s1})+5$ for sufficiently large $n$.

Thursday (Nov 10, 2022), 34 pm (offline talk): Xue Chen (University of Science and Technology of China)
Improved Decoding of Expander Codes
Abstract(Click to expand)
We study the classical expander codes, introduced by Sipser and Spielman. Given any constants $0<\alpha$, $\varepsilon<\frac{1}{2}$, and an arbitrary bipartite graph with $N$ vertices on the left, $M < N$ vertices on the right, and left degree $D$ such that any left subset $S$ of size at most $\alpha N$ has at least $(1−\varepsilon)SD$ neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly $\frac{\alpha N}{2\varepsilon}$. This is strictly better than the best known previous result of $2(1−\varepsilon)\alpha N$ whenever $\varepsilon<\frac{1}{2}$, and improves the previous result significantly when $\varepsilon$ is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes.
Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever $\varepsilon<\frac{1}{4}$. Finally, we also give a bound on the listdecoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate).
Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new sizeexpansion tradeoff, which may be of independent interests.

Thursday (Oct 27, 2022), 34 pm: Guanghui Wang (Shandong University)
Embeddings in “random like” graphs video
Abstract(Click to expand)
An archetype problem in extremal combinatorics is to study the structure of subgraphs appearing in different classes of (hyper)graphs. We will focus on such embedding problems in “random like” graphs. In practice, we will mention ramseyturan problems and related results.

Thursday (Oct 13, 2022), 34 pm: Hehui Wu (Fudan University)
Partition of graphs with high minimum degree
Abstract(Click to expand)
In 2003, Kuhn and Osthus showed that for every number $k$, every graph with minimum degree at least $l(k)=3\times 2^{11}\times k^2$ can be partition into noneempty sets $S$ and $T$, such that both $G[S]$ and $G[T]$ has minimum degree at least $k$, and each vertex of $S$ has at least $k$ neighbors in $T$. We improve this result by showing that it is true for $l(k)=100k$ when $k$ is sufficiently large. This is joint work with Jie Ma from University of Science and Technology of China.

Thursday (Sep 29, 2022), 34 pm: Jie Han (Beijing Institute of Technology)
Perfect Matchings in hypergraphs video
Abstract(Click to expand)
Matchings are fundamental objects in the study of graph theory. Unlike in graphs, finding maximum matchings in general hypergraphs is NPhard  its decision problem is actually one of the Karp’s 21 NPcomplete problems in 1972. Here we shall introduce some recent developments on perfect matchings in hypergraphs from both the extremal and the computational aspects in the past decade.