|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Carnegie Melllon University Title: Random graphs and algorithms (thesis defense) Abstract: In this thesis defence I will cover five related topics, summarizing the research I have been conducting during my graduate program. Four topics will be presented in short before going deeply into the final topic. Firstly, connectivity results in k-out random subgraphs of general graphs with large minimum degree will be presented. In particular, conditions under which a random k-out subgraph of a graph G will contain a Hamilton cycle with high probability will be presented. Secondly, the topic of online bipartite matching will be presented, focusing on proving that the cucko hashing algorithm with random walk insertion has constant expected insertion time. Two separate random optimization problems will be presented. We will show that the random graphs Gn, p and Gn, n, p with random exponential edge costs with mean 1 contain minimum-cost matchings of expected cost $\pi$2/(12p) + o(p-1) and $\pi$2/(6p) + o(p-1), respectively. We will also show that in the complete graph Kn with uniform independent [0,1] edge costs, the expected minimum cost of two disjoint spanning trees converges to a constant approximately equal to 4.17. The majority of the talk will be concerned with a preferential attachment graph with online deletion of oldest edges. We fix parameters m≥ 1 and 1/2 < p < 1. Given a graph Gt we form Gt+1 by adding a vertex with probability p. This vertex is added along with m incident edges, each of whose other endpoint is chosen with probability proportional to degrees in Gt. With probability 1-p we remove the m edges which were first added in this process. Starting with a small graph G0, we study Gn for a large n, determining the degree sequence and conditions under which a unique giant component exists. This makes use of the probabilistic tool of Crump-Mode-Jagers processes. |
