Τυχαίες συνδυαστικές δομές

Abstract

This thesis can be partitioned into 2 parts regarding the subject: In the first part we study the following problem. For given n,m,p we investigate if an instance of random intersection graph G (n,m,p) contains or not a Hamilton cycle. We assume that the parameter p of the model is such that p=p (n,m). We show that for the range of n,m,p which the model is not trivial or equivalent to other models the graph property contains a Hamilton cycle, exhibits sharp threshold. In the second part of the thesis we deal with the problem of algorithmically estimating the size the set of proper k-colourings of an instance of sparse random graph G (n,p). We present a polynomial time algorithm which has the following properties. It has input an instance of sparse G (n,p) and an integer k. If k is greater than some quantity which depends on the average degree of the graph, then with high probability it returns a k-colouring of the input graph which is asymptotically equal to the uniform over the set of all k-colouring of the input graph. Trivially, the above algorithm we present allows to estimate the size of the set of all colouring of the input graph. This algorithm improves a previous one of Dyer et.al.

Η παρούσα διατριβή μπορεί να διαμερίζεται σε θεματικές ενότητες: Στην πρώτη ενότητα της διατριβής μελετούμε το έξης πρόβλημα. Για δοσμένες τιμές των n m p διερευνούμε εάν ένα στιγμιότυπο τυχαίου γραφήματος τομής G (n,m,p) περιέχει ή μη κύκλο Hamilton. θεωρούμε ότι η παράμετρος του μοντέλου p είναι τέτοια ώστε p=p (n,m). Δείχνουμε ότι για τις τιμές των n,m,p όπου το μοντέλο δεν είναι τετριμμένο ή έχει συμπεριφορά παρόμοια με άλλα μοντέλα γραφημάτων η ιδιότητα γραφημάτων περιέχει κύκλο Hamilton παρουσιάζει οξύ κατώφλι. Στο δεύτερο μέρος της διατριβής ασχολούμαστε με την εκτίμηση με αλγοριθμικό τρόπο του μεγέθους του συνόλου των k-χρωματισμών ενός στιγμιότυπου αραιού τυχαίου γραφημάτων G (n,p). Παρουσιάζουμε έναν πολυωνυμικού χρόνου αλγόριθμο ο οποίος θα έχει τα παρακάτω χαρακτηριστικά. Παίρνει ως είσοδο ένα στιγμιότυπο G (n,d/n) για πραγματικό d>0 και έναν ακέραιο k>0. Όταν το k είναι μεγαλύτερο από μια συνάρτηση του d τότε ο αλγόριθμος θα επιστρέψει με μεγάλη πιθανότητα ένα χρωματισμό του στιγμιότυπου με κατανομή ασυμπτωτικά ίση με την ομοιόμορφη στο σύνολο όλων των k χρωματισμών του στιγμιότυπου. Με συνήθη επιχειρήματα ο παραπάνω αλγόριθμος δειγματοληψίας μας επιτρέπει να έχουμε μια προσέγγιση του μεγέθους του συνόλου όλων των k-χρωματισμών του γραφήματος εισόδου. Ο αλγόριθμος δειγματοληψίας που παρουσιάζουμε βελτιώνει αντίστοιχο αλγόριθμο των Dyer et.al.