Ο φοιτητής του προγράμματος Αντρέας Παναγή θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Faster Even-Cycle Listing via Unbalanced Supersaturation
την Πέμπτη 28 Μαΐου 2026 και ώρα 12:00, στην αίθουσα Ζ στο τμ. Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Σύνοψη Διπλωματικής:
This thesis studies the fundamental problem of listing even-length cycles through the lens of extremal graph theory. A central theme is that structural information on the number of even-length cycles in bipartite graphs can be converted into running-time bounds for cycle-listing algorithms.
The main result is a weak form of the Unbalanced Supersaturation Conjecture for even cycles. We prove that a bipartite graph (G=(A\cup B,E)) with sufficiently many edges relative to the threshold ( \max{|A|,|B|}\cdot\min{|A|,|B|}^{1/k} ) must contain many copies of (C_{2k}). Although this result constitutes a step toward the full conjecture, it already provides sufficient information for the algorithmic applications considered in this work.
Using this extremal bound, we revisit the analysis framework of Williams and Westover for listing even cycles. This yields a refined running-time analysis that matches the state of the art for listing (C_6), while avoiding the computer-assisted analysis used in their work. Moreover, it improves the previously known state-of-the-art bound for listing (C_{2k}) for every (k\ge 4), due to Alon, Yuster, and Zwick.
We also extend the discussion to hypergraphs. The incidence graph gives a global reduction from listing Berge cycles of fixed length (\ell) to listing graph cycles of length (2\ell). In addition, a direct labelled-(2)-shadow reduction lists all Berge cycles of length (\ell) passing through a prescribed vertex.
Η επιτροπή,
Αρχοντία Χ. Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Ε.Κ.Π.Α.
Βασίλειος Νάκος (Επιβλέπων),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Ε.Κ.Π.Α.
Δημήτριος Φωτάκης,
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Ε.Μ.Π.