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 26, 2024), 3:00-4:00 pm: Do Tuan Anh (Beijing Institute of Technology)
Tree- and rank-width of supercritical random graphs
Abstract(Click to expand) In this talk, we consider the width of a supercritical random graph according to some commonly studied width measures. We give short, direct proofs of results of Lee, Lee and Oum, and of Perarnau and Serra, on the rank- and tree-width of the random graph $G(n,p)$ when $p= \frac{1+\epsilon}{n}$ for $\epsilon > 0$ constant. Our proofs avoid the use, as a black box, of a result of Benjamini, Kozma and Wormald on the expansion properties of the giant component in this regime, and so as a further benefit we obtain explicit bounds on the dependence of these results on $\epsilon$. Finally, we also consider the width of the random graph in the \emph{weakly supercritical regime}, where $\epsilon = o(1)$ and $\epsilon^3n \to \infty$. In this regime, we determine, up to a constant multiplicative factor, the rank- and tree-width of $G(n,p)$ as a function of $n$ and $\epsilon$. This is a joint work with Joshua Erde and Mihyun Kang (Graz University of Technology, Austria).
Place: 5307, the 5th Teaching Building
Thursday (Sep 26, 2024), 4:00-5:00 pm: Ngo Viet Trung (Institute of Mathematics, Vietnam Academy of Science and Technology)
Ear decompositions of graphs$\colon$ an unexpected tool in Combinatorial Commutative Algebra
Abstract(Click to expand) Ear decomposition is a classical notion in Graph Theory. It has been shown in [1, 2] that this notion can be used to solve difficult problems on homological properties of edge ideals in Combinatorial Commutative Algebra. This talk presents the main combinatorial ideas behind these results.
 
[1] H.M. Lam and N.V. Trung, Associated primes of powers of edge ideals and ear decompositions of graphs, Trans. AMS 372 (2019)
[2] H.M. Lam, N.V. Trung, and T.N. Trung, A general formula for the index of depth stability of edge ideals, Trans. AMS, to appear.
Place: 5101, the 5th Teaching Building

... see all Talks