Home | deutsch | Impressum | Sitemap | Intranet | KIT
Research Group on Discrete Mathematics

Secretariat
Kollegiengebäude Mathematik (20.30)
Room 1.044

Address
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.
Classes: Seminar (0121350)
Weekly hours: 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
Schedule
Seminar: Friday 14:00-15:30 SR 2.58
Lecturers
Lecturer Torsten Ueckerdt
Office hours: Mondays 2pm-3pm
Room 1.045 Kollegiengebäude Mathematik (20.30)
Email: torsten.ueckerdt@kit.edu
Lecturer Prof. Maria Axenovich Ph.D.
Office hours: Thursdays 15:40-16:40
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