Welcome to the USTC Combinatorics Group

This is the homepage of the Combinatorics Group at the School of Mathematical Sciences, University of Science and Technology of China (USTC).

Our research interests cover various branches of Combinatorics, including graph theory, extremal combinatorics, probabilistic combinatorics, combinatorial design, and their applications to theoretical computer science, information theory and optimization.

We are looking for highly motivated Postdocs, PhD students, and Master students to join the group (more info) !

 
 
 
 
 
 
 

Talks

Thursday (Dec 21, 2023), 3:00-4:00 pm: Xiaofan Yuan (Arizona State University)
Rainbow Connectivity in Edge-colored Graphs
Abstract(Click to expand) Fujita and Magnant proved that if the minimum color degree of an edge-colored graph $(G,c)$ of order $n (>2)$ is at least $n/2$, then each pair of vertices in $(G,c)$ is connected by a properly-colored path. We show that for large $n$, the same minimum color degree condition implies rainbow connectivity of the edge-colored graph; that is, each pair of vertices in $(G,c)$ is connected by a path whose edges are distinctly colored. This is joint work with Andrzej Czygrinow.
Place: 5206, the 5th Teaching Building
Tuesday (Jun 27, 2023), 10:30-11:30 pm: Peng Zhang (Rutgers University)
Splitting a special class of circulant graphs
Abstract(Click to expand) Given a graph $G = (V,E)$ where each edge has effective resistance (treating $G$ as an electrical network where each edge is a resistor) at most $\alpha > 0$, we want to partition the edges of $G$ into $E = E_1 \cup E_2$ so that both graphs $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ with doubled edge weights are $(1 +/- O(\sqrt{\alpha}))$ approximation to $G$. We say a graph $H$ is a $(1+/-\epsilon)$ approximation to another graph $G$ if the Laplacian matrix of $H$, denoted by $L_H$, and the Laplacian matrix of $G$, denoted by $L_G$, satisfies $(1-\epsilon) L_G \preceq L_H \preceq (1+\epsilon) L_G$ (the Loewner order). The proof of the Kadison-Singer problem by Marcus, Spielman, and Srivastava (Annals of Mathematics, 2015) implies the above edge partition exists, but no polynomial-time algorithms are known. We will describe a polynomial-time algorithm for a special class of circulant graphs.
Place: 2205, the 2nd Teaching Building

... see all Talks