Urbana Campus Research Calendar (OVCRI)

Title: Recognizability of bipartite graphs with small cards

Abstract:  The reconstruction conjecture by Kelly and Ulam state that it is possible to reconstruct a graph given the multiset of $(n-1)$ vertex induced subgraphs. This multiset is called the $(n-1)$-deck of the graph. 

One can aim for a less ambitious goal, with less information. Recognition is the problem of using a deck to determine if a hidden graph is in a class. 

In this talk, we show that using the multiset of $(n-c_1\sqrt{n})$ vertex induced subgraphs ($c_1 > 0$), one can determine whether or not a graph is bipartite. We will also discuss the ideas which improve the result to using a linear sized deck, that is, the multiset of $c_2 n$ vertex induced subgraphs ($c_2 < 1$) suffices. 

Joint work with Douglas B. West.