TUM – TUM – 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
Vortrag 2. Mai 2013 Anusch Taraz Density and Ramsey results for graphs with sublinear bandwidth Donnerstag, 12.00 am, MI 02.06.020
Vortrag 16. Mai 2013 Julia Ehrenmüller, Carl Georg Heise On the Gallai-property of series-parallel graphs Donnerstag, 12.00 am, MI 02.06.020
Vortrag 6. Juni 2013 Julia Böttcher How many edges are needed to force k vertex disjoint triangles? Donnerstag, 12.00 am, MI 02.06.020
Vortrag 20. Juni 2013 Tobias Müller Line arrangements and geometric representations of graphs Donnerstag, 12.00 am, MI 02.06.020
Vortrag 27. Juni 2013 Peter Heinig Lattice-point-avoiding affine subspaces and the question of torsion in the integral homology of random simplicial complexes Donnerstag, 12.00 am, MI 02.06.020
Vortrag 04. Juli 2013 Jakob Schnitzer Die Sonnenblumen-Vermutung Donnerstag, 12.00 am, MI 02.06.020
Vortrag 11. Juli 2013 Evan Decorte Independence numbers and ratios of Cayley graphs on compact groups Donnerstag, 12.00 am, MI 02.06.020
Vortrag 18. Juli 2013 Oleg Pikhurko Minimising the Number of Cliques Donnerstag, 12.00 am, MI 02.06.020
Vortrag 13. August 2013 Humberto Naves Discrepancy of random graphs and hypergraphs Mittwoch, 12.00 am, MI 02.06.020

Abstracts

Density and Ramsey results for graphs with sublinear bandwidth

The existence of Hamilton paths and cycles in host graphs satisfying certain conditions is one of the central questions in extremal graph theory. We survey recent results that generalize these questions from Hamilton paths to spanning target graphs with low bandwidth, i.e. graphs that 'look like thickened paths'. Moreover, we will show that the answers to these questions often only depend on the chromatic number of the target graph.

On the Gallai-property of series-parallel graphs

In 1966 Gallai asked whether all longest paths in a connected graph intersect in a common vertex.This is not true in general and various counterexamples have been found. However, many well-known classes of graphs have the so-called Gallai's property, e.g. trees, outerplanar graphs, splitgraphs, and cacti. Recently, de Rezende et al. proved that 2-trees, which are maximal series-parallel graphs, also have this property. We extend this result, showing that all series-parallel graphs also have Gallai's property. First, we prove that there exists a virtual triangle such that every longest path contains at least one of its vertices. Then, we show that actually one edge of this triangle fulfils this property. The next step would be to iteratively find such virtual edges until we are left with a single vertex.

How many edges are needed to force k vertex disjoint triangles?

A well-known theorem of Erdős and Gallai answers the following question: How many edges does a graph need in order to guarantee a matching of a certain size? More precisely, for all values of n and k, what is the smallest number e(n,k) such that any graph G on n vertices and with e(n,k) edges contains a matching with k edges?

We consider the analogous question for vertex disjoint triangles in G (instead of matching edges), extending work of of Erdős (1962) and of Moon (1968). We show that, surprisingly, there are 4 different types of extremal graphs for this problem, each of them dominating for a specific range of k=k(n). Our proofs rely on rotation techniques, and are relatively elementary, though technically demanding.

Joint work with Peter Allen, Jan Hladký, and Diana Piguet.

Line arrangements and geometric representations of graphs

A dot product representation of a graph assigns to each vertex s a vector v(s) in R^k in such a way that v(s)^T v(t) > 1 if and only st is an edge. Similarly, in a distance representation |v(s)-v(t)| < 1 if and only if st is an edge. I will discuss the solution of some open problems by Spinrad, Breu & Kirkpatrick and others on these and related geometric representations of graphs. The proofs make use of a connection to oriented pseudoline arrangements, some results from algebraic geometry and the Colin de Verdière parameter.

(Based on joint works with Ross Kang, Colin McDiarmid, Erik Jan van Leeuwen and Jan van Leeuwen)

Lattice-point-avoiding affine subspaces and the question of torsion in the integral homology of random simplicial complexes

Simplicial homology is a technique pioneered by Poincaré which synthesizes, rather noise-tolerantly, lots of local incidence information about the parts of a discretized structure into a few numbers with global significance. It is a time-honoured tool to tell whether two structures are substantially different, and has both practical (classifying 'clouds' of measured points) and theoretical (classifying mathematically defined spaces) interest. Roughly a decade ago Linial and Meshulam discovered yet another use of homology: if used as higher-dimensional substitute for connectedness, it results in a clean 2-dimensional analogue of the phase transition for connectedness of a binomial random graph. They worked with mod 2 homology and asked whether their theorem remains true for integral homology. Despite strong evidence that the answer is affirmative, there still seems to be no finished proof. This talk will present some of my ongoing attempts to get some quantitative control on the integral homology of a random 2-dimensional simplicial complex. My approach tries to stay away from the usual characterizations via determinants and gcd, but rather associates with the random complex an affine subspace whose containing or not containing a lattice point decides about whether the 1-dimensional homology H_1 contains torsion. This approach seems more amenable to calculations, and seems to lead to inclusion-exclusion formulas (still to be analysed and simplified) for the probability of the event that H_1 is torsion-free.

Die Sonnenblumen-Vermutung

Als Sonnenblume wird eine Familie von Mengen bezeichnet, die paarweise den gleichen Schnitt haben. Es wird gezeigt, dass in ausreichend großen Mengenfamilien immer eine Sonnenblume gewünschter Größe vorhanden ist. Die unbewiesene Sonnenblumen-Vermutung würde eine besonders gute Schranke liefern, wie groß diese Familien sein müssen um die Existenz einer Sonnenblume zu erzwingen. Es werden die besten heute bekannten Annäherungen an die Vermutung vorgestellt und ausgewählte werden exemplarisch bewiesen. In zwei Spezialfällen, in Graphen und in unendlichen Mengenfamilien, werden noch bessere Ergebnisse gezeigt.

Independence numbers and ratios of Cayley graphs on compact groups

Given a Cayley graph on a compact group (CCG for short), one can ask two interesting questions about the sizes of independent sets: What is the maximum cardinality of an independent set? and What is the maximum Haar measure of an independent set? The answers to these questions define, respectively, the independence number and the independence ratio of the CCG. In this talk we mention a few problems (some of them open), each of which reduces to the computation of the independence number or ratio of some CCG. We also present preliminary work on two generalizations of the Lovasz theta-function to CCG's; one of them gives upper bounds for the independence number, and the other gives upper bounds for the independence ratio.

Minimising the Number of Cliques

Motivated by Ramsey's theorem, Erdős asked in 1962 about the value of f(n,k,l), the minimum number of k-cliques in a graph with order n and independence number less than l. The case (k,l)=(3,3) was solved by Lorden.

By applying flag algebras, we solve the problem (for all large n) for (3,l) with 4 <= l <= 7 and (k,3) with 4 <= k <= 7. Independently, Das, Huang, Ma, Naves, and Sudakov resolved the cases (k,l)=(3,4) and (4,3).

Joint work with E.R.Vaughan.

Discrepancy of random graphs and hypergraphs

Let H be a graph with edge density p. For each subset S of V(H), let d(S) denote the difference between the number of edges induced by S in H and the expected number of edges induced by a (uniformly chosen) random set of vertices having the same size as S. The discrepancy of H is the maximum of |d(S)| over all possible S (the maximum norm of d(S)), and it is denoted by disc(H).

This important concept appears naturally in various branches of combinatorics and was studied by many researchers in recent years. The discrepancy can be viewed as a measure of how uniformly the edges of H are distributed among the vertices, and it is closely related to the theory of quasi-random graphs, since small discrepancy implies quasi-randomness. A natural generalization is the relative discrepancy of two hypergraphs. Let G and H be two hypergraphs over the same vertex set V. For each permutation q of V, let q(G) be the hypergraph obtained from G by permuting its vertices according to q. The overlap between G and H with respect to q, denoted by e(G,H,q), counts the number of edges which belong to both q(G) and H. The discrepancy of G with respect to H is defined as the maximum norm of the difference between e(G,H,q) and its average over all permutations q.

Bollobás and Scott introduced and studied this notion, and they asked the following question. For two random n-vertex graphs G and H with constant edge probability p, what is the expected value of disc(G,H)? In this talk we answer this question in a strong form by determining the discrepancy between two random k-uniform hypergraphs, up to a constant factor depending only on k. Moreover, we will also discuss other related results and problems.

(Joint work with Benny Sudakov and Jie Ma)

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.