There are several distinct settings in theoretical computer science where we have an unknown underlying graph, we gain limited access to it in some form by means of an induced subgraph, and we try to conclude something about the structure of the entire graph. This question of learning a structure from partial information is the cornerstone of many active areas of research. In this thesis, we study two basic and very different models for learning graph properties. We will show some surprising results as well as some fundamental common principles in these two settings.
In the first, probabilistic setting, we ask: suppose we have a fixed, unknown, underlying graph G, which is passed through a deletion channel, that keeps each vertex with some uniform fixed probability p (typically a constant), deletes the rest, and returns the resulting induced subgraph. How many such samples (or "traces") would we need to reconstruct the original graph with high probability? We show several results in this setting, including separations between random and arbitrary graphs, and vertex and edge deletions.
In the second, deterministic setting, we ask: what is the most efficient way to distinguish between two graphs using logical characterizations? It turns out that this question is tied fundamentally with complexity theory. A technique we have for showing lower bounds in these realms is by means of two-player logical games, where two perfect players (called "Spoiler" and "Duplicator") play pebble games on a pair of graphs without having access to the whole graph. We define a generalization of known games that can be provably used as a complete characterization of any syntactic measure; in particular, this generalizes all known games and unifies them under a single flexible framework.
Despite being from quite distinct areas of research, the two problems show a remarkable set of similarities. They both ask about the fundamental structures of graphs, while having access only to partial "views" of the graph. They both rely on distinguishing a given pair of graphs as the main subroutine, and thereafter draw conclusions about identifying entire classes of graphs. They both exploit isomorphism testing as an intermediate subroutine. The main conclusion in both is impacted heavily by isomorphic subgraphs that are not automorphisms. And finally, they both show a notable phenomenon in which there being an inherent "ordering" in the underlying universe makes the question provably easier than there being no such ordering.
Advisors: Neil Immerman & Andrew McGregor