2021 CMS Winter Meeting

Ottawa, June 7 - 11, 2021   AARMS-CMS Student Poster Session
Org: Amar Venga
[PDF]

BENOIT CORSINI, McGill University
Local minimum spanning tree optimization  [PDF]

Consider the following procedure on the complete weighted graph. Start with an initial spanning subgraph $H_0$ and, at each step, replace a connected subgraph of $H_i$ with its corresponding minimum-weight spanning tree to obtain $H_{i+1}$. By repeating this procedure, the weight of the graphs $H_0,H_1,\ldots$ decreases and, under the assumption that we do not always choose the same subgraphs, it eventually reaches the global minimum-weight spanning tree on the complete graph.

Given an instance of this procedure, say that its weight is the maximal weight of any connected subgraph we replaced at any step. In a sense, the weight of a procedure describes how local'' the changes are, where locality is measured with respect to the current graph at each step. We pose the question: what is the smallest achievable weight, optimized over all possible replacement sequences which terminate at the minimum-weight spanning tree?

We show that, for iid $\mathrm{Uniform}([0,1])$ edge weights on the complete graph $K_n$, this optimal weight converges to $1$ as $n\rightarrow\infty$, no matter what the initial graph $H_0$ is. Our proof reduces the general problem to three important special cases: when the initial graph $H_0$ is a complete graph, a star graph, or a Hamiltonian path.

Based on joint work with Louigi Addario-Berry and Jordan Barrett.

Let $E/\mathbb{Q}$ be an elliptic curve without complex multiplication. By Serre's open image theorem, the mod $\ell$ Galois representation of $E$ is surjective for each prime number $\ell$ that is sufficiently large. Under GRH, we obtain the best explicit upper bound on the largest non-surjective prime in terms of the conductor of $E$. This makes effective a bound of the same asymptotic quality due to Larson and Vaintrob. We also illustrate the efficiency of the bound using an elliptic curve with large conductor in LMFDB. This is a joint work with Jacob Mayle.