Research Group on Discrete Mathematics

Secretariat
Kollegiengebäude Mathematik (20.30)
Room 1.044

Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Office hours:
Tu, Th, F 8:30-12:00

Tel.: +49 721 608 47412

Fax.: +49 721 608 46968

# AG Diskrete Mathematik (Winter Semester 2016/17)

 Lecturer: Torsten Ueckerdt, Prof. Maria Axenovich Ph.D. Seminar (0121350) 2

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
 Seminar: Friday 14:00-15:30 SR 2.58
 Lecturer Torsten Ueckerdt Office hours: Room Kollegiengebäude Mathematik (20.30) Email: torsten.ueckerdt@kit.edu Prof. Maria Axenovich Ph.D. Office hours: by appointment 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 objects and buckets. Each bucket has the capacity for a small number of objects. Clearly, you could fit all objects into the buckets if , were it not for an additonal requirement: Each object is associated with 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 . 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 . More precisely, there is a threshold density such that for there is no valid assignment and for there is a valid assignment, both with probability approaching as and 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 -orientation of a -uniform random hypergraph. A computer scientist would say we are concerned with cuckoo hashing and is the maximum load factor of a corresponding retrieval data structure for the 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 -- -nets and -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 -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