Basic Information
Erdos-renyi Model. Evolution of Random Graph. Connectivity. Appearance of Subgraphs. Clique Number and Chromatic Number. Planted Clique Problem. Random Regular Graph. Expander Graphs. Learning Outcomes# By The End of The Course The Student Will# 1) Be Familiar With The Two Main Models of Random Graphs# Erdos-renyi Random Graphs, and Random Regular Graphs. 2) Be Able to Analyze The Behavior of Random Graphs in Both Models. 3) Know and Be Able to Apply Relevant Probabilistic Techniques, Such As Markov's Inequality, Chebyshev's Inequality, Chernoff's Inequality, Azuma's Inequality, Janson's Inequality, and The Poisson Approximation Method.
Faculty: Computer Science
|Undergraduate Studies
|Graduate Studies
Pre-required courses
(94412 - Probability (advanced) and 104166 - Algebra Am) or (94412 - Probability (advanced) and 104016 - Algebra 1/extended) or (104016 - Algebra 1/extended and 104222 - Probability Theory) or (104166 - Algebra Am and 104222 - Probability Theory)