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
partners


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

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.



Letzte Aktualisierung: 02.04.2012