Εύρεση του cycle isolation number για τυχαίο γράφημα του μοντέλου Erdős-Rényi

Ορέστης Λιγνός

Περίληψη: Στην ομιλία αυτή, θα ασχοληθούμε με μία συγκεκριμένη περίπτωση (p_n → ∞) ενός γενικότερου προβλήματος, αυτού της εύρεσης του cycle isolation number ενός τυχαίου γραφήματος G(n,p) στο μοντέλο Erdős-Rényi. Το cycle isolation number για ένα γράφημα ορίζεται γενικά ως ο ελάχιστος αριθμός κορυφών που πρέπει κανείς να αφαιρέσει από αυτό, μαζί με γειτονικές κορυφές αυτών ώστε το εναπομείναν γράφημα να μην έχει κύκλο. Για την επίλυση του προβλήματος θα αναπτύξουμε και θα αξιοποιήσουμε κάποιες χρήσιμες πιθανοτικές τεχνικές και εργαλεία. Η ομιλία αυτή σχετίζεται με την ομιλία του Κωστή Θεοτοκάτου στις 30/10 και βασίζεται σε κοινή δουλειά με τον καθηγητή Δημήτρη Χριστοφίδη.

Abstract: In this talk, we will work on a specific case (p_n → ∞) of a more general problem, that of determining the cycle isolation number of a random graph in the Erdős-Rényi model. The cycle isolation number for a graph is generally defined as the least number of vertices one should remove, along with neighboring vertices, such that the graph remaining has no cycles. For the solution of the problem we will develop and use some useful probabilistic techniques and tools. This talk is conceptually connected with Kostis Theotokatos's talk in 30th of October and is based in joint work with professor Demetres Christofides.