Georgia Institute of Technology College of Sciences

From networks to genomics, large amounts of data are abundant and play critical roles in helping us understand complex systems. In many such settings, these data take the form of large discrete structures with important combinatorial properties. The interplay between structure and randomness in these systems presents unique mathematical and statistical challenges. In this talk I will highlight these through two vignettes: (1) inference problems on networks, and (2) DNA data storage.

First, I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Furthermore, we obtain the precise threshold for exact community recovery using multiple correlated graphs, which captures the interplay between the community recovery and graph matching tasks. 

Next, I will give an overview of DNA data storage. Storing data in synthetic DNA is an exciting emerging technology which has the potential to revolutionize data storage. Realizing this goal requires innovation across a multidisciplinary pipeline. I will explain this pipeline, focusing on our work on statistical error correction algorithms and optimizing DNA synthesis, highlighting the intimate interplay between statistical foundations and practice.

Graphs are central objects of study in Discrete Mathematics. A graph consists of a set of vertices, some of which are connected by edges. Their elementary structure makes graphs widely applicable, but the theoretical understanding of graphs is far from complete. Extremal graph theory aims to find connections between global parameters and substructure. A key topic is how a large average or minimum degree of a graph can force certain subgraphs (where the degree is the number of edges at a vertex). For instance, Erdős and Gallai proved in the 1960's that any graph of average degree at least $k$ contains a path of length $k$. Some of the most intriguing open questions in this area concern trees (connected graphs without cycles) as subgraphs. For instance, can one substitute the path from the previous paragraph with a tree? We will give an overview of open problems and recent results in this area, as well as their possible extensions to hypergraphs.

Link: https://bluejeans.com/398474745/0225

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t \ge 1$. Hadwiger's Conjecture is a vast generalization of the Four Color Theorem and one of the most important open problems in graph theory. Only the cases when $t$ is at most 6 are known. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t (\log t)^{0.5})$ and hence is $O(t (\log t)^{0.5})$-colorable.  In a recent breakthrough, Norin, Song, and I proved that every graph with no $K_t$ minor is $O(t (\log t)^c)$-colorable for every $c > 0.25$,  Subsequently I showed that every graph with no $K_t$ minor is $O(t (\log \log t)^6)$-colorable.  Delcourt and I improved upon this further by showing that every graph with no $K_t$ minor is $O(t \log \log t)$-colorable. Our main technical result yields this as well as a number of other interesting corollaries.  A natural weakening of Hadwiger's Conjecture is the so-called Linear Hadwiger's Conjecture that every graph with no $K_t$ minor is $O(t)$-colorable.  We prove that Linear Hadwiger's Conjecture reduces to small graphs. In 2005, Kühn and Osthus proved that Hadwiger's Conjecture for the class of $K_{s,s}$-free graphs for any fixed positive integer $s \ge 2$. Along this line, we show that Linear Hadwiger's Conjecture holds for the class of $K_r$-free graphs for every fixed $r$.