Combinatorics Seminar
Upcoming talks
Past talks
2023

Tuesday (Jun 27, 2023), 10:3011: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 KadisonSinger problem by Marcus, Spielman, and Srivastava (Annals of Mathematics, 2015) implies the above edge partition exists, but no polynomialtime algorithms are known. We will describe a polynomialtime algorithm for a special class of circulant graphs.

Tuesday (May 30, 2023), 45 pm: Luoxin Zhang (National University of Singapore)
Network Classes and Their Mathematical Properties
Abstract(Click to expand)
Phylogenetic networks over a set of taxa are rooted, directed acyclic graphs in which leaves represent the taxa, the nonleaf indegree1 nodes represent speciation events and the nodes with multiple incoming edges represent reticulation events when they are used to model the evolutionary history of a set of genomes. In the study of algorithmic issues of phylogenetic networks, different classes of phylogenetic networks have been investigated. The popular network classes include galled network, treechild network, treebased network, etc. I will discuss our recent work on how to count treechild networks and its subclasses.

Friday (Apr 7, 2023), 4:305:30 pm: ZhiWei Sun (Nanjing University)
A new result similar to the GrahamPollak theorem
Abstract(Click to expand)
In 1971, R.L. Graham and H.O. Pollak obtained a beautiful result on determinants of distance matrices for trees. In this talk, we introduce the speaker's recent work which is similar to the GrahamPollak theorem. Namely, we will prove the following result:Let $n > 1$ be an integer, and let $T$ be any tree with $n+1$ vertices $v_1,\ldots,v_{n+1}$, where $v_1$ and $v_{n+1}$ are two leaves of $T$. Then $$\det[q^{d(v_{j+1},v_k)}t]_{1\le j,k\le n}=t(q1)^n(q+1)^{n2},$$ where $d(v_{j+1},v_k)$ is the distance between $v_{j+1}$ and $v_k$ in the tree $T$.