Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Maria Axenovich - Karlsruhe

On induced subgraphs of a graph

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.

Letzte Aktualisierung: 02.04.2012