Monday, April 16, 2012
Technische Universität Berlin
Institut für Mathematik Str. des 17. Juni 136
room MA 041
Lecture - 14:15
How much information about the structure of a graph G can we retrieve knowing some partial information about induced subgraphs? The reconstruction conjecture of Ulam states that we can determine the graph up to isomorphism knowing all the unlabeled induced subgraphs obtained from the original graph by deleting a vertex. However, even knowing just the sizes of induced subgraphs could provide a lot of information about the graph. The result of Bosak et. al. says that if all k-vertex subgraphs have the same size then a graph can be determined almost uniquely. What if the number of sizes of the k-vertex subgraph of G is two, or three, or ten? In this work, we are able to answer this question by showing an existence of a large homogeneous subset in G, which allows to "almost" reconstruct the structure of G, with the exception of the subgraph induced by a small number of vertices. This is a joint work with Jozsef Balogh.
Due to a meeting of the MDS faculty, there is no colloquium after the lecture.