Mardi 28 Mars

Heure:	14:00 - 17:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints
Description:	Sergey Dovgal We show that by restricting the degrees of the vertices of a graph to an arbitrary set ?, the threshold ?(?) of the phase transition for a random graph with n vertices and m = ?(?).n edges can be either accelerated (e.g.,?(?) approx 0.38 for ? = {0,1,4,5}) or postponed (e.g., ?(?) approx 0.95 for ?={1,2,50}) compared to a classical Erd?s?Rényi random graph where ?(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path...).We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literalis incident to belongs to the set ?. We prove a lower bound for the probability that a formula with n variables and m=2.?(?) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.?.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson.This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals.Joint work with Vlady Ravelomanana.