Seminars

View all Seminars  |  Download ICal for this event

Perfect matchings and Quantum Physics

Series: Theory Seminar

Speaker: Rishikesh Gajjala Ph.D (Engg.) student Dept. of C.S.A IISc, Bangalore

Date/Time: Jun 03 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor:

Abstract:
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

Speaker Bio:

Host Faculty: Sruthi Gorantla and Rahul Madhavan