The Friday Seminar is an informal weekly seminar for

members of discrete mathematics group
students in the group
everybody else that is interested

Every week there is one speaker that gives a talk of one of the following kind

presentation of original research
introduction into an open problem that he/she currently works on
presentation of proposed plan for bachelor, master, diploma or PhD thesis
presentation of results from bachelor, master, diploma or PhD thesis
presentation of research paper that might be of interest for the group

Schedule
Seminar:	Friday 14:00-15:30	SR 2.58

Lecturers
Lecturer	Torsten Ueckerdt
	Office hours:
	Room Kollegiengebäude Mathematik (20.30)
	Email: torsten.ueckerdt@kit.edu
Lecturer	Prof. Dr. Maria Axenovich
	Office hours: Fr. 10:00-11:00
	Room 1.043 Kollegiengebäude Mathematik (20.30)
	Email: maria.aksenovich@kit.edu

UPCOMING TALK

Important: This seminar takes place in SR 3.068!

Friday March 10, 14:00

Stefan Walzer

Orientability of Random Hypergraphs

You are given $n$ objects and $m$ buckets. Each bucket has the capacity for a small number $\ell \geq 1$ of objects. Clearly, you could fit all objects into the buckets if $n \leq m\cdot\ell$ , were it not for an additonal requirement: Each object is associated with $k \geq 2$ buckets, chosen independently and uniformly at random. Each object must go into one of its associated buckets. Now, there may not be a valid assignment, even if $n \leq m\cdot \ell$ . Indeed there may be some "unpopular" buckets that are not associated with any object (making those buckets useless) while other "popular" buckets are overcrowded. Interestingly, whether or not a valid assignment exists, is well predicted by the density $c = \frac{n}{m\cdot\ell}$ . More precisely, there is a threshold density $c^* = c_{k,\ell}^* \in (0,1)$ such that for $c > c^*$ there is no valid assignment and for $c < c^*$ there is a valid assignment, both with probability approaching $1$ as $n$ and $m$ go to infinity.

In my talk, I will showcase several methods that have been used to prove the likely existence or likely non-existence of such assignments above and below the threshold, respectively. Afterwards I will present my research problem related to overlapping buckets on which I am currently stuck, looking forward for your input.

What I called "valid assignment" above is formally an $\ell$ -orientation of a $k$ -uniform random hypergraph. A computer scientist would say we are concerned with cuckoo hashing and $c$ is the maximum load factor of a corresponding retrieval data structure for the $n$ objects.

Talk History

2017/02/10 -- Christian Ortlieb -- Generalized Ramsey Numbers
2017/02/03 -- Tamar Mirbach -- Ramsey Turnaround Numbers - A Variation of Online Ramsey Numbers
2017/01/27 -- Yen Hoang Le -- Minimum Saturated Graphs

2017/01/20 -- Robert Slomian -- Graphs without 4-Chromatic Ivies
2017/01/13 -- Jonathan Rollin -- Ramsey Theory for Ordered Graphs
2016/12/16 -- Philip Dörr -- Induced Arboricity on Planar Graphs
2016/12/09 -- Mónika Csikós -- $\epsilon$ -nets and $k$ -union VC dimension
2016/12/02 -- Christian Kouekam -- On Ordered Ramsey Numbers

2016/11/18 -- Maria Axenovich -- Improper Colorings of Planar Graphs
2016/11/11 -- Dominik Dürrschnabel -- Disjoint Homometric Sets in Graphs
2016/11/04 -- Lasse Wulf -- Stacked Treewidth and the Colin de Verdiére Number
2016/10/28 -- Peter Stumpf -- More on Different Graph Covering Numbers
2016/10/21 -- Torsten Ueckerdt -- Inclusion Orders in the Plane

2016/07/22 -- Fabian Stroh -- How To Share Trees Optimally
2016/07/08 -- Torsten Ueckerdt -- Unit Distances in a Convex Polygon
2016/07/01 -- Jonathan Klawitter -- Combinatorial Aspects of Contact Graphs
2016/06/24 -- Dominik Dürrschnabel -- Disjoint Homometric Sets in Graphs
2016/06/17 -- Sascha Stoll -- On Conflict-Free Colorings of Planar Graphs

2016/06/10 -- Torsten Ueckerdt -- A Beginner's Guide to Tree-Width
2016/06/03 -- Agnes Grünewald -- On the Induced Ramsey Number
2016/05/27 -- Lasse Wulf -- An Introduction to the Colin de Verdière Number of a Graph
2016/05/20 -- Jonathan Rollin -- The k-Strong Induced Arboricity of Tree-Depth d Graphs
2016/05/13 -- Torsten Ueckerdt -- The Induced Arboricity of a Graph

2016/05/06 -- Annette Karrer -- Non-Colorable Uniform Bihypergraphs with High Girth
2016/04/29 -- Hanno Lefmann -- Edge Colorings of Graphs Without Fixed Colored Subgraphs
2016/04/22 -- Pacsal Schmitt -- Disjoint Induced Subgraphs of the Same Order and Size
2016/03/15 -- Daniel Goncalves -- Entropy Compression Method Applied to Graph Coloring
2016/02/12 -- Jonathan Rollin -- Conflicts in Ordered Graphs

2016/02/05 -- Torsten Ueckerdt -- Blossoming Trees and Planar Graphs
2016/01/29 -- Yassine Marrakchi -- Approximation Scheme for Maximum Independent Set of Rectangles
2016/01/22 -- Maria Axenovich -- Transversal Families for Edge-colored Complete Graphs
2016/01/15 -- Gregor Lagodzinski -- Combinatorics of 2-connected Series-parallel Graphs
2015/12/18 -- Torsten Ueckerdt -- Schnyder's Theorem -- continued

2015/12/11 -- Fabian Stroh -- Sharing Even Spiders
2015/12/04 -- Jonathan Rollin -- Ramsey Multiplicities
2015/11/27 -- Torsten Ueckerdt -- The Interval Number of Planar Graphs
2015/11/20 -- Annette Karrer -- Uncolorable Bihypergraphs with Few Edges
2015/11/13 -- Julia Heller -- Noncrossing Partitions in Geometric Group Theory

2015/11/06 -- Jonathan Rollin -- The Chromatic Number of Ordered Graphs
2015/10/30 -- Kolja Knauer -- Drawing Graphs with Vertices and Edges in Convex Position
2015/10/23 -- Torsten Ueckerdt -- Schnyder's Theorem
2015/09/11 -- Mujiangshan Wang -- The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM∗ Model
2015/07/17 -- Maria Axenovich -- Report from Ron Graham's Birthday Conference

2015/07/10 -- Stefan Walzer -- Finding Monochromatic Cubes in Coloured Cubes
2015/07/03 -- Jonathan Rollin -- Degrees and Factors in Graphs
2015/06/26 -- Stefan Walzer -- Secure Card-Based Computation
2015/06/19 -- Jonathan Klawitter -- Crossing Minimisation in Book Embeddings
2015/06/12 -- Stephen G. Kobourov -- 1-Planar Graphs

2015/06/05 -- Maria Axenovich -- Hales-Jewett Theorem and Ramsey Classes
2015/05/29 -- Peter Stumpf -- On Covering Numbers of Different Kinds
2015/05/22 -- Sebastian Ziesche -- A Short Introduction to Percolation
2015/05/15 -- Torsten Ueckerdt -- The Etiquette of Sharing a Cake
2015/05/08 -- Alexander Koch and Stefan Walzer -- TikZ vs. Ipe

2015/04/24 -- Felix Joos -- An Approximation of the Packing-Covering Duality
2015/04/17 -- Torsten Ueckerdt -- Combinatorial Graph Sharing Games
2015/02/06 -- Stefan Walzer -- 2-Dimension and Ramsey Lattices
2015/01/30 -- Maria Axenovich -- Size Anti-Ramsey Numbers
2015/01/23 -- Jonathan Rollin -- Ramsey Equivalent Graphs

2015/01/16 -- Torsten Ueckerdt -- Contact Representations of Sparse Planar Graphs
2015/01/09 -- Dirk Tröndle -- Convex Distance Function Delaunay Triangulations
2014/12/19 -- Valentin Braun -- On-line Graph Colorings
2014/12/12 -- Anika Kaufmann -- On Clumsy Packing of Complete Graphs
2014/12/05 -- Jennifer Weidelich -- Adjacent Vertex Distinguishing Colorings of Bipartite Graphs

2014/11/28 -- Pascal Weiner -- H-free Colourings of Planar Graphs
2014/11/21 -- Stefan Walzer -- On the Size of Sumsets
2014/11/14 -- Jonathan Klawitter -- Transforming Rectangles Into Squares
2014/10/31 -- Jonathan Rollin -- Brooks Type Results for Conflict-Free Colorings and $\{a,b\}$ -Factors
2014/10/24 -- Torsten Ueckerdt -- Online Coloring Between Two Lines

2014/07/25 -- Kunal Dutta -- On the Discrepancy of Certain Point-Capturing Hypergraphs
2014/07/18 -- Jonathan Rollin -- Conflict-Free Colorings and Factors of Regular Graphs
2014/07/11 -- Georg Osang -- The Local Chromatic Number
2014/07/04 -- Andre Kündgen -- Spanning Quadrangulations of Triangulated Surfaces
2014/06/27 -- Sarah Lutteropp -- On Layered Drawings of Planar Graphs

2014/06/13 -- Jennifer Weidelich -- Adjacent Vertex Distinguishing Colorings
2014/06/06 -- Jonathan Klawitter -- Transforming Rectangles Into Squares
2014/05/30 -- Stefan Walzer -- Disjoint Induced Subgraphs of the Same Order and Size
2014/05/23 -- Pascal Weiner -- Improper Colourings of Graphs
2014/05/16 -- Open Discussion -- Sympossium Diskrete Mathematik 2014

2014/05/02 -- Peter Stumpf -- Covering Numbers of Different Kinds
2014/04/25 -- Anika Kaufmann -- Clumsy Packings of Regular Graphs Into a Complete Graph
2014/04/11 -- Piotr Micek -- Lower Bounds for On-Line Graph Colorings
2014/02/13 -- Yury Person -- Powers of Hamilton Cycles in Pseudorandom Graphs
2014/02/07 -- Sarah Lutteropp -- On Layered Drawings of Planar Graphs

2014/01/31 -- Stefan Walzer -- Tron : A Two Player Game on Graphs
2014/01/24 -- Annette Karrer -- Simultaneous Embeddings of Outerplanar Graphs
2014/01/17 -- Torsten Ueckerdt -- The Density of Fan-Planar Graphs
2014/01/10 -- Maria Axenovich -- On Distinguishing Colorings
2013/12/20 -- Dirk Tröndle -- Convex Distance Funtion Delaunay Triangulations

2013/12/13 -- Fabian Stroh -- Coloring Graphs Using Topological Lemmas
2013/12/06 -- Enrica Cherubini -- Coloring Mixed Hypergraphs
2013/11/29 -- Jonathan Rollin -- Hamiltonicity in Sparse Graphs With High Chromatic Number
2013/11/18 -- Torsten Ueckerdt -- Scattered Sets in Cocomparability Graphs
2013/07/19 -- André Kündgen -- Central digraphs

2013/02/12 -- Maria Axenovich -- On Ramsey Numbers and Size Ramsey Numbers
2013/02/05 -- Torsten Ueckerdt and Maria Axenovich -- Non-crossing Connectors in the Plane and Twins
2013/01/29 -- Maria Axenovich -- On a Reconstruction Problem for Sequences
2013/01/22 -- Torsten Ueckerdt -- Combinatorial and Geometric Properties of Planar Laman Graphs
2013/01/15 -- Jonathan Rollin -- Unique Edge Colorings

2012/12/18 -- Fabian Stroh -- Coloring Kneser Graphs
2012/12/11 -- Ignaz Rutter -- Research on Stack- and Queue-number of Graphs
2012/12/04 -- Torsten Ueckerdt -- Research on Coloring Geometric Hypergraphs
2012/11/27 -- Alexander Koch -- Representations of Graphs by Outside Obstacles
2012/11/20 -- Daniel Hoske -- Book Embedding with Fixed Page Assignments

2012/11/13 -- Maria Axenovich -- On Bar-Visibility Representations of Graphs
2012/11/06 -- Judith Stumpp -- Online Size Anti-Ramsey Numbers
2012/10/30 -- Stefan Walzer -- Clumsy Packings - Wasting Space in Geometric Puzzles
2012/10/23 -- Jonathan Rollin -- Report from 4 PCC, Poznan
2012/10/16 -- Torsten Ueckerdt -- The Twin Problem

AG Diskrete Mathematik (Winter Semester 2016/17)

UPCOMING TALK

Important: This seminar takes place in SR 3.068!

Orientability of Random Hypergraphs

Talk History