The ACO Seminar (2016–2017)

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 G_{n, p} and G_{n, n, p} with random exponential edge costs with mean 1 contain minimum-cost matchings of expected cost π²/(12p) + o(p^-1)$ and π²/(6p) + o(p^-1), respectively. We will also show that in the complete graph K_n 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 G_t we form G_t+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 G_t. With probability 1-p we remove the m edges which were first added in this process. Starting with a small graph G₀, we study G_n 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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.