Tata Institute of Fundamental Research
The Critical Exponent: A Novel Graph Invariant
STCS Colloquium
Speaker:
Apoorva Khare (Indian Institute of Science
Department of Mathematics
Bangalore 560012)
Organiser:
Hariharan Narayanan
Date:
Tuesday, 17 Oct 2017, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Given a graph $G$, let $\mathbb{P}_G$ denote the cone of positive semidefinite (psd) matrices, with non-negative entries, and zeros according to $G$. Which powers preserve psd-ness when applied entrywise to all matrices in $\mathbb{P}_G$?
In recent work, joint with D. Guillot and B. Rajaratnam, we show how preserving positivity relates to the geometry of the graph $G$. This leads us to propose a novel graph invariant: the "critical exponent" of $G$. Our main result shows how this combinatorial invariant resolves the problem for all chordal graphs. We also report on progress for several families of non-chordal graphs.
| Speaker: | Apoorva Khare (Indian Institute of Science Department of Mathematics Bangalore 560012) |
| Organiser: | Hariharan Narayanan |
| Date: | Tuesday, 17 Oct 2017, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Given a graph $G$, let $\mathbb{P}_G$ denote the cone of positive semidefinite (psd) matrices, with non-negative entries, and zeros according to $G$. Which powers preserve psd-ness when applied entrywise to all matrices in $\mathbb{P}_G$?
In recent work, joint with D. Guillot and B. Rajaratnam, we show how preserving positivity relates to the geometry of the graph $G$. This leads us to propose a novel graph invariant: the "critical exponent" of $G$. Our main result shows how this combinatorial invariant resolves the problem for all chordal graphs. We also report on progress for several families of non-chordal graphs.
In recent work, joint with D. Guillot and B. Rajaratnam, we show how preserving positivity relates to the geometry of the graph $G$. This leads us to propose a novel graph invariant: the "critical exponent" of $G$. Our main result shows how this combinatorial invariant resolves the problem for all chordal graphs. We also report on progress for several families of non-chordal graphs.