ÀÏÍõÂÛ̳

Speaker: , associate professor of mathematics, Indian Institute of Science

Title: On Maximizing Satisfied Vertex Requests in List Coloring

Abstract:
In 1971, Graham and Pollak showed that if \(D_T\) is the distance matrix of a tree \(T\) on \(n\) nodes, then \(\det(D_T)\) depends only on \(n\), not \(T\). This independence from the tree structure has been verified for many different variants of weighted bi-directed trees. In this talk:

1. We a general setting which strictly subsumes every known variant, and where we show that \(\det(D_T)\) - as well as another graph invariant, the cofactor-sum - depends only on the edge-data, not the tree-structure.
2. More generally - even in the original unweighted setting - we strengthen the state-of-the-art, by computing the minors of \(D_T\) where one removes rows and columns indexed by equal-sized sets of pendant nodes. (In fact we go beyond pendant nodes.)
3. We explain why our result is the "most general possible", in two ways. First, allowing greater freedom in the parameters leads to dependence on the tree-structure. Second, the result holds over all unital commutative rings - shown via Zariski density, which seemed to be unutilized in the field, yet was richly rewarding.

If time permits, a formula for \(D_T^{-1}\) will be presented, whose special case answers an open problem of Bapat-Lal-Pati (LAA 2006), and which extends to our general setting a result of Graham-Lovasz (Advances 1978). 

This is joint work with Projesh Nath Choudhury.

Discrete Applied Math Seminar