报告题目: Separators in Graphs

报告时间：9月6号（周五）下午3:30

报告地点: 理学院206

报 告 人: Thomas Bohme

报告摘要: 

A well-known theorem of Lipton and Tarjan [1] from the 1970s states that every planar graph on n vertices can be split into subgraphs each of which contains at most n vertices by removing a set of at most nvertices. Over the years this theorem has been extended to various classes of graphs, most notably to graphs not containing a specifific graph as a minor [2], string graphs [3], and graphs that can be embedded into the d-dimensional euclidean space with bounded distortion [4]. In the talk I will give a short overview of the field and present some so far unpublished improvements and refined proof techniques.

References

[1] Lipton, Richard J.; Tarjan, Robert E., ”A separator theorem for planar graphs”, SIAM Journal on Applied Mathematics, 36 (2): 177 - 189.

[2] Alon, Noga; Seymour, Paul; Thomas, Robin, ”A separator theorem for nonplanar graphs”, J. Amer. Math. Soc., 3 (4): 801–808.

[3] Fox, Jacob; Pach, J´anos, ”A separator theorem for string graphs and its applications”, Combin. Probab. Comput. 19 (2010), 371–390.

[4] Linial, Nathan; London, Eran; Rabinovich, Yuri, ”The Geometry of Graphs and Some of its Algorithmic Applications”, Combinatorica 15(2): 215–245 (1995).

报告人简介:

Education:

Diplom in Mathematics, TH Ilmenau, 1982.

Dr.rer.nat. in Mathematics, TH Ilmenau, 1988.

Dr.rer.nat.habil.(Habilitation) in Mathematics, TU Ilmenau, 1999.

Positions:

1982 - present: TU Ilmenau, Scientifific Staffff Member.

2013 - present: TU Ilmenau, Unscheduled Professor (außerplanm¨aßiger Professor).

2014 - 2017: TU Ilmenau, Vice Dean, Department of Mathematics and Natural Science (Fakult¨at f¨ur Mathematik und Naturwissenschaften).

2017 - present: TU Ilmenau, Dean, Department of Mathematics and Natural Science (Fakult¨at f¨ur Mathematik und Naturwissenschaften).

Visiting Positions:

10/1987-05/1988: Research Fellow, E˝otv˝os-Lorand-University, Budapest (Hungary).

02/1990 - 04/1990: Research Fellow, PH Kiel (Germany).

12/1994 -05/1995: Research Fellow, Department of Applied Mathematics, Twente University, Enschede (The Netherlands).

04/1996: Guest Lecturer, Moscow Power Engineering Institute (Russia).

09/2001 - 05/2002: Visiting Assistant Professor, Department of Computer Science University of North Texas, Denton TX (U.S.A.).

09/2003 Guest Lecturer, University of Guadalajara (Mexico)

Research: Discrete mathematics (mostly in graph theory), game theory.

欢迎有兴趣的师生参加！