Tata Institute of Fundamental Research

Are Three Petersens Enough?

STCS Student Seminar
Speaker: Varun Ramanathan (TIFR)
Organiser: Hari Krishnan P A
Date: Friday, 6 Jun 2025, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

The Petersen graph is perhaps the most well-known 3-regular graph on 10 vertices. Donald Knuth states (in one of his many many books) that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general." In this talk, we will ignore all of that and instead consider the following problem: can three isomorphic copies of the Petersen graph cover the complete graph on 10 vertices? While a brute-force approach should reveal the answer, we will take a spectral approach to solve this problem. The talk will be based on a chapter from Jiří Matoušek's book "Thirty-three miniatures."