Monday, April 16, 2012
Technische Universität Berlin
Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
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.