Menü

Forschungsseminar Diskrete Mathematik

Angewandte Geometrie und Diskrete Mathematik

Auf dieser Seite werden die Vortragstermine im Forschungsseminar der Arbeitsgruppe Diskrete Mathematik verwaltet.

Standardtermin

 Seminar: MI 02.06.020

Vorträge

 Datum Vortragende(r) Titel Zeit, Raum Do, 8. Nov. 2012 Andreas Würfl Homogeneous sets in cographs 12:00 Uhr,   MI 02.06.020 Do, 22. Nov. 2012 Guilherme Mota On an anti-Ramsey threshold for Random Graphs 12:00 Uhr,   MI 02.06.020 Mi, 28. Nov. 2012 Peter Heinig, Susanne Nieß Towards an explanatory proof of the maximum density of five-cycles in a triangle-free graph 9:00 Uhr,   MI 02.06.020 Do, 6. Dez. 2012 (Kein Vortrag wegen Dies Academicus) Mi, 12. Dez. 2012 Julia Ehrenmüller Embedding certain spanning trees in random graphs 9:00 Uhr,   MI 02.06.020 Mi, 19. Dez. 2012 Armin Krupp Basic concepts of additive combinatorics via Roth's Theorem 9:00 Uhr,   MI 02.06.020 Do, 10. Jan. 2013 Peter Allen Embedding in sparse graphs 12:00 Uhr,   MI 02.06.020 Do, 24. Jan. 2013 Cristina Gomes Fernandes Intersecting Longest Paths 12:00 Uhr,   MI 02.06.020 Mi, 30. Jan. 2013 Mathias Schacht Minimum degree conditions for homomorphisms into odd cycles 9:15 Uhr,   MI 02.06.020 Do, 7. Feb. 2013 Alexander Boldeanu Das Planarspiel auf dem K_n 12:00 Uhr,   MI 02.06.020

Abstracts

Homogeneous sets in cographs

Erdös and Hajnal conjectured that for every graph F there exists a constant eps(F)>0 such that every graph G that does not have F as an induced subgraph contains a clique or a stable set of order Ω(|V(G)|^eps(F)). Loebl et. al. ask for which graphs F it is true that there is a constant c(F)>0 such that almost all graphs G that do not have F as an induced subgraph contain a clique or a stable set of order c(F)|V(G)|. In this talk we prove that for any eps>0 almost all cograph (which is the case F=P_4 ) do not have a clique or a stable set of order Θ(n/log^(1−eps) n).

On an anti-Ramsey threshold for Random Graphs

For graphs G and H, let G--->H denote the property that for every proper edge-colouring of G (with an arbitrary number of colours) there is a totally multicoloured, or rainbow, copy of H in G, that is a copy of H with no two edges of the same colour. We consider the problem of establishing the threshold p_H=p_H(n) of this property for the binomial random graph G(n,p). More specifically, we give an upper bound to p_H and we extend our results to colourings that generalize proper colourings. Our proofs are based on the regularity method on characterizations of sparse quasi-randomness given by Chung and Graham [Quasi-random graphs with given degree sequences, Random Structures and Algorithms, 32 (2008), no. 1, 1--19].

Towards an explanatory proof of the maximum density of five-cycles in a triangle-free graph

In two recent breakthroughs, Grzesik, and independently Hatami--Hladký--Král--Norine--Razborov, answered an old open question of Erdős as to whether the density of isomorphic copies of circuits of length five in a triangle-free graph can be larger than what it is for the lexicographic product of a five-circuit with a coclique. Both proofs employ the method of flag-algebras introduced by Razborov and are partly computer-assisted. Our talk will be a progress report on a project aiming at constructing a flag-algebra-free and humanly-checkable proof of this theorem. In particular, our proof-strategy rests on an idea which refines the statement into substatements. This promises to result in a more explanatory and modular proof.

Embedding certain spanning trees in random graphs

In 1988 Bender and Wormald proved that for any constant c > 2e^2 the random graph G(n, c log n / n) a.a.s. contains almost every tree on n vertices. In this talk we will discuss the results of Hefetz, Krivelevich and Szabó, who were able to improve the former upper bound of the edge probability for certain spanning trees with bounded maximum degree, whereas they could no longer guarantee almost universality type statements. More precisely, they proved that a given tree T on n vertices with bounded maximum degree is contained a.a.s. in the binomial random graph G(n, (1+eps)log n / n) provided that T has linearly many leaves or contains a bare path of linear length. Since the connectivity threshold is p(n)=log n / n and no spanning tree can appear as long as the graph is disconnected, their results are optimal.

Basic concepts of additive combinatorics via Roth's Theorem

Let $\alpha > 0$ and suppose that $A \subset {1,...,N}$ is a set with at least $\alpha N$ elements, which does not contain an arithmetic progression of length 3. Then $\alpha < C*(log(log(N)))^-1$.

In this talk, we will sketch the original proof of this classical result of Roth (1953) and use it to get an idea of several key themes in additive combinatorics.

Intersecting Longest Paths

In 1966, Gallai asked whether every connected graph has a vertex that is common to all longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs and 2-trees. Another related question was raised by Zamfirescu in the 1980s: Do any three longest paths in a connected graph have a vertex in common? The answer to this question is unknown. We prove that for connected graphs in which all nontrivial blocks are Hamiltonian the answer is affirmative.

Minimum degree conditions for homomorphisms into odd cycles

We study minimum degree conditions under which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erdős and Sós implies that n-vertex graphs with odd girth 2k+1 and minimum degree 2n/2k+1 must be bipartite. We investigate the structure of graphs with given odd girth and a more relaxed minimum degree condition. Generalizing a result from Häggkvist and Jin for the case k = 3, we show that every n-vertex graph with odd girth 2k + 1 and minimum degree 3n/4k is homomorphic to a cycle of length 2k+1. Similar results were obtained by Brandt and Ribe-Baumann. This is joint work with Silvia Messuti.

Das Planarspiel auf dem K_n

Beim Planarspiel auf dem vollständigen Graphen K_n wählen zwei Spieler, Avoider und Enforcer, abwechselnd eine Kante eines K_n und bauen damit eigene Subgraphen. Ziel von Avoider ist es, die Einbettung seines Graphen planar zu halten, während Enforcer versucht, dies zu verhindern (ob der Graph von Enforcer planar ist oder nicht spielt keine Rolle). Offensichtlich wird Avoider das Spiel verlieren, die interessante Frage ist, wieviele Züge lang er seinen Graphen planar halten kann. Mit dem vorgestellten Algorithmus von Avoider wird gezeigt, dass die Differenz der oberen und unteren Schranke der Spieldauer nur eine Konstante, also unabhängig von n ist.

Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.