Combinatorics Seminar
Upcoming talks
Past talks
2023

Thursday (Dec 21, 2023), 3:004:00 pm: Xiaofan Yuan (Arizona State University)
Rainbow Connectivity in Edgecolored Graphs
Abstract(Click to expand)
Fujita and Magnant proved that if the minimum color degree of an edgecolored graph $(G,c)$ of order $n (>2)$ is at least $n/2$, then each pair of vertices in $(G,c)$ is connected by a properlycolored path. We show that for large $n$, the same minimum color degree condition implies rainbow connectivity of the edgecolored 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.

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$.