Talks in 2022

  • Friday (Dec 16, 2022), 10:30-11:20 am: 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 edge-partitioned 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 edge-partition problems of graphs. Some unsolved problems will be provided.
  • Thursday (Dec 15, 2022), 2-3 pm: Changhong Lu (East China Normal University)
    A bridge between the coin-weighing problem and the double resolving problem of graphs video
    Abstract(Click to expand) 硬币称重问题（Coin-weighing problems）是个经典的组合优化问题，其中一个经典形式为：给定$n$个硬币，假定真硬币的重量和假硬币的重量均已知，用弹簧称对硬币进行称重，用最少的称重次数将所有的假币找出来。图的$2$-分辨集（double resolving problem）是Caceres 等人在2007年为了研究图的分辨集问题（resolving set problem）提出的一个工具性的新概念。最近，我们证明了超方体的$2$-分辨集问题与硬币称重问题的等价关系，我们利用硬币称重问题的Lindström方法给出计算超方体和折叠超方体$2$-分辨集问题的快速算法，给出了一些新结果，包括解决公开问题；反过来，$2$-分辨集问题的图论结果也给硬币称重问题带来了一些新进展，比如$14$,$16$,$18$个硬币称重问题的新上界。
  • Thursday (Dec 8, 2022), 3:30-4:30 pm: Pan Peng (University of Science and Technology of China)
    Sublinear-Time Algorithms for Max Cut and Unique Label Cover on Expanders
    Abstract(Click to expand) We give the first sublinear-time algorithm for the Max Cut problem with non-trivial 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 sublinear-time algorithm for the Unique Label Cover (also known as Unique Games) problem on expanders in the bounded-degree 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), 3-4 pm: Hongliang Lu (Xi'an Jiaotong University)
    Anti-Ramsey 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 anti-Ramsey number ${\rm 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 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 (Anti-Ramsey number of matchings in hypergraphs, Discrete Math., 313 (2013), 2359--2364) 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), 286--313) verified this conjecture for all $n \geq sk+(s-1)(k-1)$ and $k \geq 3$. We aim to determine the value of ${\rm 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 ${\rm ar}(n,3,M_s)={\rm ex}(n,3,M_{s-1})+2$. Here ${\rm ex}(n,3,M_{s-1})$ is the Turan 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 ${\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_{s-1})+5$ for sufficiently large $n$.
  • Thursday (Nov 10, 2022), 3-4 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)|S|D$ 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 list-decoding 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 size-expansion tradeoff, which may be of independent interests.
  • Thursday (Oct 27, 2022), 3-4 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 ramsey-turan problems and related results.
  • Thursday (Oct 13, 2022), 3-4 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 none-empty 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), 3-4 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 NP-hard -- its decision problem is actually one of the Karp’s 21 NP-complete 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.