Time: Wednesday, 19 February 2020, 2:0pm
Venue: Dept. of CSE, Room No. 109, 01st Floor, New CSE/CC Bldg.
Abstract:
A connected graph G, on two or more vertices, is matching covered if each edge belongs to some perfect matching. A subgraph H of G is conformal if G−V(H) has a perfect matching. For problems pertaining to perfect matchings of a graph G — such as those arising from the perfect matching polytope PMP(G) — one may restrict attention to matching covered graphs. Several of these problems may be stated in terms of conformal subgraphs of a graph. I will discuss 5 such problems each of which pertains to characterizing a class of graphs; these graph classes are described below. (By ‘characterize’, I mean: obtain an NP or a co - NP characterization, and ideally, show that the corresponding decision problem is in P.)
The first two graph classes arise from the perfect matching polytope PMP(G).
1. Birkhoff–von Neumann graphs: A graph G is Birkhoff–von Neumann if PMP(G) may be described solely by non-negativity and degree constraints.
2. PM-compact graphs: A graph G is PM-compact if the combinatorial diameter of PMP(G) equals 1.
The next two graph classes are inspired by a theorem of Lovász (1983): Every non-bipartite matching covered graph either “contains” K_4 or “contains” the triangular prism C_6 .
3. C_6 -free graphs: A graph G is C_6 -free if it does not “contain” C_6 .
4. K_4 -free graphs: A graph G is K 4 -free if it does not “contain” K_4 .
The last graph class, and arguably the most important one (among these 5), was defined by physicists Fisher, Kasteleyn, and Temperley (1960s) in order to solve the “dimer problem”.
5. Pfaffian graphs: A graph G is Pfaffian if it admits a “Pfaffian orientation”.
During this talk, I will discuss these 5 graph classes, and will explain their connections with conformal subgraphs. Thereafter, I will summarize my contributions (so far) towards characterizing these graph classes; these results are listed below.
In a joint work with Carvalho, Wang and Lin (https://arxiv.org/abs/1807.07339), we provided a complete description of graphs that are Birkhoff–von Neumann as well as PM-compact. The corresponding decision problem is in P.
In a joint work with Lucchesi, Carvalho and Murty (https://epubs.siam.org/doi/ abs/10.1137/17M1138704), we showed that the problem of deciding whether a graph is C_6 -free is equivalent to that of deciding whether a graph is Birkhoff–von Neumann.
In a joint work with Murty (https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.21882), we provided a complete description of planar K 4 -free graphs as well as planar C_6 -free graphs. The corresponding decision problems are in P.
Finally, I will briefly mention my conjectures relating K_4 -free graphs to Pfaffian graphs.
Speaker's Profile:
Nishad Kothari, as a researcher, studies mathematical objects called Graphs, and specializes in the study of Perfect Matchings (aka, Matching Theory). In this sense, he is a structural graph theorist whose work has connections with complexity theory, polyhedral combinatorics as well as statistical mechanics.
After completing his Bachelor's degree in Computer Science (CS) from BIT Mesra (Ranchi),he went on to obtain his Master's degree in CS from Georgia Tech (Atlanta, USA). It was during his time at Georgia Tech that he discovered his interest in the theoretical aspects of CS. Consequently, he took a few courses from the School of Mathematics, and was introduced to Graph Theory by Robin Thomas. This memorable encounter with the subject ultimately led him to pursue his PhD in Combinatorics and Optimization (C&O) at the Faculty of Mathematics at the University of Waterloo (Canada) under the supervision of Joseph Cheriyan and U. S. R. Murty. During his time at C&O Waterloo, not only did Professor Murty train him in Matching Theory, but he also ignited his enthusiasm for the subject.
Since completing his PhD in 2016, Nishad has held postdoc positions at C&O Waterloo and at the Faculty of Mathematics at the University of Vienna (Austria). Currently, he is a postdoc at the Institute of Computing at the University of Campinas (Brazil), and his principal collaborators are Marcelo H. de Carvalho and Claudio L. Lucchesi. He has a diverse network of coauthors who live in Brazil, Canada, China, New Zealand and USA.
Nishad, as an educator, is especially passionate about teaching courses in Combinatorics (aka, Discrete Mathematics), and is also interested in lecturing about related subjects in theoretical CS and mathematics. During his time at C&O Waterloo, he taught introductory courses in both Combinatorics and Optimization..