BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20220603T120000Z
UID:4295a0a9dc9ce5f6a8ee57f8dad565cc-285
DTSTAMP:19700101T120011Z
DESCRIPTION:Perfect matchings and Quantum Physics
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/285/perfect-matchings-and-quantum-physics/
SUMMARY:In 2017, Krenn reported that certain problems related to the perfect matchings and colourings of graphs emerge out of studying the constructability of general quantum states using modern photonic technologies. He realized that if we can prove that the weighted matching index of a graph, a parameter defined in terms of perfect matchings and colourings of the graph is at most 2, that could lead to exciting insights on the potential of resources of quantum inference.

Motivated by this, he conjectured that the weighted matching index of any graph is at most 2. The first result on this conjecture was by Bogdanov, who proved that the (unweighted) matching index of graphs (non-isomorphic to K_4) is at most 2, thus classifying graphs non-isomorphic to K_4 into Type 0, Type 1 and Type 2. By definition, the weighted matching index of Type 0 graphs is 0. We give a structural characterization for Type 2 graphs, using which we settle Krenns conjecture for Type 2 graphs. Using this characterization, we provide a simple O(|V||E|) time algorithm to find the unweighted matching index of any graph. In view of our work, Krenns conjecture remains to be proved only for Type 1 graphs. We give upper bounds for the weighted matching index in terms of connectivity parameters for such graphs. Using these bounds, for a slightly simplified version, we settle Krenns conjecture for the class of graphs with vertex connectivity at most 2 and the class of graphs with maximum degree at most 4.


For our full paper, see paper link (https://arxiv.org/abs/2202.05562).
---------

For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/?talk=20220603_RishikeshGajjala
DTSTART:20220603T120000Z
END:VEVENT
END:VCALENDAR