Seminar coordinates:
This is a Discrete Mathematics Seminar with weekly talks followed by discussion and lunch. The sessions are informal, talks last about 30 minutes and treat discrete topics the speakers like or have been working on. Everybody is welcome to participate. If you would like to give a talk, let us know.Time: Fridays, 12.00-12.45
Questions: email to knauer [at] math.tu-berlin.de
Room: MA-645
Next Talk:
Speaker: Kolja Knauer
Title: "tba"
Date: May 25
Talks in 2012:
May 11, 2011: Daniel Heldt, "Conductance, congestion and canonical paths of Markov chains"
May 4, 2011: Stefan Felsner, "A note on proportional contact representations"
May 2, 2011: Udo Hoffmann, "Recognition of Simple Triangle Graphs"
April 27, 2011: Irina Mustata, "Unit grid intersection graphs: Properties and relationships to other graph classes"
April 13, 2011: Viola Mészáros, "Graph Sharing Games"
March 30, 2012: Thomas Hixon, "Cyclic segment graphs and diagonal hook graphs"
March 28, 2012: Kristian Dannowski, "Chromatic Invariants of Shift Graphs and Kneser Graphs"
March 16, 2012: Bartosz Walczak, "The chromatic number of geometric intersection graphs"
February 17, 2012: Torsten Ueckerdt, "How many bends for one additional direction?"
February 10, 2012: Hao Chen, "The distance geometry for the kissing balls"
January 27, 2012: Veit Wiechert, "The dimension of posets with outerplanar cover or planar comparability graphs"
January 20, 2012: Marie Albenque, "Constellations and multicontinued fractions: application to Eulerian triangulations"
January 13, 2012: Stefan Felsner, "The graphs that can be drawn with one bend per edge"
January 6, 2012: Nieke Aerts, "Matchings that yield "good" triangle representations"
Talks in 2011:
December 16, 2011: Irina Mustata, "2-Directional Orthogonal Ray Graphs"
December 2, 2011: Timo Strunk, "Labellings and decompositions of planar and toroidal quadrangulations"
November 25, 2011: Viola Mészáros, "The upper bound for separated matchings"
November 18, 2011: Daniel Heldt, "Three families of graphs with bad conductance for the face-flip Markov chain on α-orientations"
Ocotber 28, 2011: Marie Albenque, "Computing numbers with balls and urns"
Ocotber 21, 2011: Thomas Hixon, "Weak conflict free colourings"
October 14, 2011: Kolja Knauer, "The hull number of partial cubes"
October 7, 2011: Torsten Ueckerdt, "Crossing-free curves within pseudodiscs"
September 28, 2011: Bartłomiej Bosek & Grzegorz Matecki, "Generalization of Dilworth's Theorem and Semiantichain Conjecture"
September 23, 2011: Stefan Felsner, "Squaring the Torus"
September 16, 2011: Alex Sheive, "The Group Theory of Spinpossible"
September 14, 2011: Irina Mustata, "Jump number(s) of partially ordered sets"
September 7, 2011: Maximilian Werk, "Rhombische Pflasterungen von Dreiecken"
August 24, 2011: Daniel Heldt, "Sampling Schnyder-woods of planar triangulations with max degree ≤6"-- presentation of a result of Miracle, Randall, Streib & Tetali
August 23, 2011: Nieke Aerts, "Graphs that yield safe communication schemes"
August 17, 2011: Thomas Hixon, "The Tron Problem"
August 10, 2011: Marie Albenque, "Planar maps and continued fractions"
July 20, 2011: Kolja Knauer, "Cayley graphs of semigroups"
July 13, 2011: Thomas Picchetti, "How to compute a squaring?"
July 6, 2011: Stefan Felsner, "Trapezoidal dissections and Markov chains"
June 29, 2011: Jawaherul Alam, "Proportional Contact Representations with Rectilinear Polygons"
June 22, 2011: Raphael Traut, "Zeichnen von Ordnungen; Eine Experimentalstudie"
June 8, 2011: Torsten Ueckerdt, "Introducing the bar visibility number of a graph"
May 18, 2011: Irina Mustata, "Tolerance graphs as trapezoid graphs and NP-completeness"
May 11, 2011: Marie Albenque, "On the enumeration of simple symmetric quadrangulations"
May 4, 2011: Daniel Heldt, "Groebner bases for order theorists"
April 27, 2011: Veit Wiechert, "Planar Posets and Dimension 2"
April 20, 2011: Thomas Hixon, "Crossing a bridge at night"
April 13, 2011: Kolja Knauer, "A graph-theoretical axiomatization of oriented matroids"
March 16, 2011: Julia Rucker, "On Rectangle Contact Representations"
March 9, 2011: Kai Lawonn, "The Colin de Verdiere Graph Parameter"
March 2, 2011: Verena Richter, "Pflasterung orthogonaler Polygone mit Rechtecken"
February 23, 2011: Stefan Felsner, "Contact Representations of Planar Graphs with Weights"
February 16, 2011: Torsten Ueckerdt, "The Isometric Dimension of Median Graphs via a Generalization of Birkhoff's Representation Theorem"
February 9, 2011: Marie Albenque, "A bijection between fractional trees and pentagulations of girth 5"
January 26, 2011: Richard Sieg, "Dissections of polygons and the cylinder into triangles of equal areas"
January 19, 2011: Irina Mustata, "Grid Intersection Graphs"
January 12, 2011: Stefan Felsner, "Contact representations of planar graphs with cubes"
January 5, 2011: Torsten Ueckerdt, "Online Coloring of Bounded-Tolerance Graphs"
Talks in 2010:
December 15, 2010: Thomas Hixon, "On the crossing number of complete and complete bipartite graphs"
December 8, 2010: Daniel Heldt, "Some remarks on the behavior of a local operating Markov chain on the set of k-heights"
November 24, 2010: Veit Wiechert, "Planar posets and dimension"
November 10, 2010: Tobias Mueller, "Line arrangements and geometric graph classes"
November 3, 2010: Mathew C. Francis, "The class of segment graphs"
September 22, 2010: Stefan Felsner, "d-Schnyder structures"
August 25, 2010: Torsten Ueckerdt, "CAT-Enumeration of the Ideals of a Planar Poset"
July 21, 2010: Stefan Felsner, "Square Tilings and Extremal Length"
July 14, 2010: Daniel Heldt, "A glimpse at the kernel method and Knuth's approach to the ballot problem"
June 23, 2010: Petr Gregor, "Linear extension diameter of subposets of Boolean lattice induced by two levels"
June 9, 2010: Osmanbey Uzunkol, "Konstruktion elliptischer Kurven mit vorgegebener Ordnung"
May 19, 2010: Kolja Knauer, "Lattices and Set Systems"
May 12, 2010: Stefan Felsner, "Transitive orientation and vertex partitioning"
May 5, 2010: Daniel Heldt, "Walking on a path (with loops) II"
April 28, 2010: Till Miltzow, "Punkte mit grosser Quadrantentiefe"
April 21, 2010: Torsten Ueckerdt, "Coroutines and Hamiltonian Paths in Lattices"
April 14, 2010: Hendrik Lüthen, "Abzählprobleme für Pfade im Gitterstreifen"
March 31, 2010: Torsten Ueckerdt, "Enumerating all Ideals of a Poset - Some Special Cases"
March 24, 2010: Torsten Ueckerdt, "How far is a graph from being an interval graph?"
March 17, 2010: Kolja Knauer, "Edge-intersection graphs of grid paths"
March 10, 2010: Julia Rucker, "Triangle contact representations of plane graphs"
March 3, 2010: Agelos Georgakopoulos, "Hyperbolic graphs, fractal boundaries, and graph limits"
February 24, 2010: Stefan Felsner, "Antichains of (k+k)-free posets"
February 17, 2010: Tomasz Krawczyk, "On-line dimension of orders"
February 10, 2010: Bartosz Walczak, "Parity in graph sharing games"
February 3, 2010: Tom Trotter, "On the Size of Maximal Antichains and the Number of Pairwise Disjoint Maximal Chains"
January 27, 2010: Torsten Ueckerdt, "One way to generalize interval graphs: edge-intersection graphs of elbows in the plane grid"
January 20, 2010: Kolja Knauer, "Generalizing the order polytope"
January 13, 2010: Daniel Heldt, "Walking on a path (with loops) I"
January 6, 2010: Cornelia Dangelmayr, "Neues zum Satz von Hanani und Tutte"
Talks in 2009:
December 18, 2009: Andrea Hoffkamp, "Funktionales Denken im propädeutischen Analysisunterricht - Ansätze und empirische Befunde zu einem qualitativen Zugang durch Computereinsatz II"
December 16, 2009: Andrea Hoffkamp, "Funktionales Denken im propädeutischen Analysisunterricht - Ansätze und empirische Befunde zu einem qualitativen Zugang durch Computereinsatz I"
December 9, 2009: Stefan Felsner, "Lower bounds for on-line chain partitioning"
December 2, 2009: Bartłomiej Bosek & Tomasz Krawczyk, "A subexponential upper bound for the on-line chain partitioning problem"
November 25, 2009: Stefan Felsner, "Coding and Counting Arrangements of Pseudolines"
November 18, 2009: Torsten Ueckerdt, "The Balloon Popping Problem"
November 11, 2009: Stefan Felsner, "Planar Bipartite Posets"
November 4, 2009: Daniel Heldt, "Sensitivity of 3-heights on a path"
Ocotober 21, 2009: Till Miltzow, "Points with Some Quadrant Depth"
Ocotober 14, 2009: Kolja Knauer, "Polynomial Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids"
Ocotober 7, 2009: Torsten Ueckerdt, "Enumerating all Ideals of a Poset"
September 30, 2009: Stefan Felsner, "Squarings of Quadrangulations"
September 16, 2009: Vincent Pilaud, "A failed construction of the multiassociahedron"
September 2, 2009: Mareike Massow, "Swap Colors in Linear Extension Graphs"
August 5, 2009: Daniel Heldt, "Layer decomposition of planar graphs"
July 22, 2009: Balchandra Thatte, "Reconstruction of Pedigrees"
July 15, 2009: Julia Pap, "Kernels and Sperner's Lemma"
July 8, 2009: Daniel Heldt, "Computational aspects of mixing heights"
June 31, 2009: Matjaz Kovse, "Topological representations of planar partial cubes"
June 24, 2009: Kolja Knauer, "Antimatroids, Polytopes and ULDs"
June 17, 2009: Torsten Ueckerdt, "(Linear) Induced Forests in Planar Graphs"
June 10, 2009: Stefan Felsner, "Condorcet Domains and Arrangements of Pseudolines"
June 3, 2009: Pavel Valtr, "On Triconnected and Cubic Plane Graphs on Given Point Sets"
May 27, 2009: Stefan Felsner, "Rectangular layouts: associated graphs and constructions."
May 13, 2009: Florent Becker, "Curry-Hähnchen zu Mittag (An Introduction to Curry-Howard and the Coq Proof-Assistant)"
May 6, 2009: Tobias Friedel, "Root Systems and Generalized Associahedra"
April 29, 2009: Sarah Li, "Adjacency Posets"
April 22, 2009: Mareike Massow, "Convex Partitions of the Permutahedron"
April 15, 2009: Jan Foniok, "Constraint Satisfaction and Category Theory: Constructing Tractable Templates"
March 25, 2009: Daniel Heldt, "A Short Introduction to Block Cipher Algorithms"
March 18, 2009: Anton Dochtermann, "Graph Homomorphisms and Reflection Positivity"
March 11, 2009: Torsten Ueckerdt, "On Quadrant-Depth - Closing the Gap"
March 4, 2009: Melanie Win Myint, "Compactness proofs for infinite graphs"
February 25, 2009: Stefan Felsner, "On Quadrant-Depth"
February 18, 2009: Kolja Knauer, "Generalized Chip Firing"
February 11, 2009: Mareike Massow, "Linear Extension Diameter of Boolean Lattices"
January 28, 2009: Stefan Felsner, "Sorting Pairs in Bins, aka 'Das Krawattenraetsel'"
January 21, 2009: Torsten Ueckerdt, "On the number of non-decreasing paths in grid graphs"
January 14, 2009: Mihyun Kang, "Yet Another Way of Counting Planar Graphs"
January 7, 2009: Paul Bonsma, "Avaloqix is strongly PSPACE-hard"
Talks in 2008:
December 17, 2008: Florent Becker, "Self-Assembling Tilings, Orders and Signal Systems"
December 10, 2008: Britta Peis, "Covering Graphs by Colored Stable Sets"
December 3, 2008: Bruno Benedetti, "Bipartite Graphs and Basic k-Covers"
November 26, 2008: Daniel Heldt, "A Reason Why Avaloqix Could Be 'Interesting' (i.e. NP-hard)"
November 19, 2008: Melanie Win Myint, "An Algebraic Characterization of Planar Graphs"
November 12, 2008: Mareike Massow, "The Boolean Lattice and its Linear Extension Diameter"
November 5, 2008: Sarah Li, "Characterization of Maps with Order Dimension at most 2"
October 29, 2008: Stefan Felsner, "Partitioning Boolean Lattices into Intervals"
October 22, 2008: Hal Kierstead, "Efficient packing via game coloring"
October 15, 2008: Torsten Ueckerdt, "How to Eat 4/9 of a Pizza"
October 8, 2008: Daniel Heldt, Jannik Matuschke and Madeleine Theile, "Avaloqix - A Max Flow Game"
September 10, 2008: Bartłomiej Bosek and Kamil Kloch, "Online Dimension of Semi-Orders with Representation"
September 3, 2008: Kamil Kloch and Piotr Micek, "Some Open Problems We Like"
July 30, 2008: Uwe Schauz, "Tutte's Flow Conjectures and Berlekamp's Switching Game"
July 16, 2008: Bernd Sturmfels, "Evolution on distributive lattices"
July 9, 2008: Torsten Ueckerdt, "Distributive polyhedra and related problems on weighted parameterized graphs"
July 2, 2008: Melanie Win Myint, "Cycles and Bicycles in Locally Finite Graphs II"
June 25, 2008: Felix Fischer, "Voting Caterpillars"
June 18, 2008: Melanie Win Myint, "Cycles and Bicycles in Locally Finite Graphs I"
June 11, 2008: Peter Allen, "A connection between Ramsey number and chromatic number"
June 4, 2008: Mareike Massow, "LINEAR EXTENSION DIAMETER is NP-complete"
May 28, 2008: Sarah Li, "Random Walks and Search Problems"
May 21, 2008: Ludmila Scharf, "Inducing Polygons of Line Arrangements"
May 14, 2008: Mareike Massow, "Linear Extensions in Diametral Pairs Don't Have to Be Reversing"
April 30, 2008: Paul Bonsma, "A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs"
April 23, 2008: Uwe Schauz, "Mr. Paint and Mrs. Sandpaper"
April 16, 2008: Axel Werner, "Linkages in Polytope Graphs"
April 9, 2008: Bernd Sturmfels, "Permutohedra, Semigraphoids, and Mice"
March 19, 2008: Stefan Felsner, "Hamiltonicity Properties of Arrangement Graphs"
March 12, 2008: Kolja Knauer, "On Frankl's Conjecture"
March 5, 2008: Cornelia Dangelmayr, "k-Segments in Arrangements of Pseudolines"
February 27, 2008: Patrick Baier, "Distributed Computation of Virtual Coordinates"
February 20, 2008: Stefan Felsner, "Markov Chains and the Second Eigenvalue"
February 13, 2008: Moritz Schmitt, "The Spectrum of a Graph"
February 6, 2008: Anton Dochtermann, "Foldings and the Topology of Graph Homomorphisms"
January 30, 2008: Mareike Massow, "Reconstructing Posets from Linear Extension Graphs"
January 23, 2008: Kolja Knauer, "A Distributive Lattice on Pseudo-Flows"
January 16, 2008: Gesine Koch, "Counting Paths in Cube Configurations"
January 9, 2008: Paul Bonsma, "A Polynomial Time Algorithm for Finding Fullerene Patches"
Talks in 2007:
December 21, 2007: Graham Brightwell, "Polyhedral Methods for Linear Extensions of Partial Orders"
December 12, 2007: Sarah Li, "The Dictator Paradox"
December 5, 2007: Stefan Felsner, "Sorting Using Networks of Stacks and Queues"
November 28, 2007: Florian Zickfeld, "Leafy Trees in Planar Graphs"
November 21, 2007: Nina Siebold, "How to Draw an Order"
November 14, 2007: Leonid Ioffe, "Dimension Of Orders via Constraint Programming"
November 7, 2007: Patrick Baier, "Greedy Drawings of Planar Triangulations"
October 31, 2007: Cornelia Dangelmayr, "k-Level Complexity of Arrangements of (Pseudo-)Segments"
October 24, 2007: Kolja Knauer, "Construction of Steiner Triple Systems"
October 17, 2007: Martin Pergel, "Recognition and Optimization Problems on Geometric Intersection Graphs"
October 10, 2007: Balazs Keszegh, "Weak Conflict-Free Colorings of Point Sets and Simple Regions"
September 28, 2007: Florian Pfender, "Turan's Theorem for Multipartite Graphs"
September 19, 2007: Stefan Felsner, "Compact Drawings with Bends"
September 5, 2007: Mareike Massow, "Partitioning Posets"
August 29, 2007: Stefan Felsner, "Matchings and Edge Colorings in Regular Graphs"
August 8, 2007: Carolyn Chun, "Unavoidable Minors of c-connected Graphs"
August 1, 2007: Bertrand Marc, "2-Arrangements of Pseudolines"
July 25, 2007: Florian Zickfeld, "Leafy Trees"
July 18, 2007: Eric Fusy, "A bijection between loopless maps and triangulations"
July 11, 2007: Patrick Baier, "Digital Geometry"
July 4, 2007: Stefan Felsner, "Infeasibility of Arrangements"
June 27, 2007: Kamil Kloch, Tomasz Krawczyk and Piotr Micek "On-line Dimension of Intervals"
June 20, 2007: Kamil Kloch, "On-line Colouring of Intervals"
June 13, 2007: Olivier Bernardi, "Bijective Countings of Tree-Rooted Maps"
June 6, 2007: Cornelia Dangelmayr, "Planar Graphs are in 1-STRING"
May 23, 2007: Stefan Felsner, "On-line chain partitions of up-growing 2-dimensional orders"
May 16, 2007: Felix Breuer, "Perlenketten mit Quoten"
May 9, 2007: Mareike Massow, "Diametral Pairs of Linear Extensions of a Poset"
May 2, 2007: Florian Zickfeld, "Hardness of Counting Orientations with Fixed Out-Degrees"
April 25, 2007: Sarah Kappes, "Was ist ein semidefinites Programm?"
April 18, 2007: Patrick Baier, "Compass Routing"
April 11, 2007: Cornelia Dangelmayr, "Pseudo-Connections in the Plane"
April 4, 2007: Stefan Felsner, "Triangle Contact Representations of Graphs"
March 21, 2007: Andreas Hoffmeister, "Random sampling in distributive lattices"
March 7, 2007: Stefan Felsner, "Online Ramsey Theory"
January 31, 2007: Mareike Massow, "2-Dimensional Partial Orders Revisited"
January 24, 2007: Florian Zickfeld, "Counting Planar Eulerian Orientations is #P-complete" (Recent result by Paid�Creed)
January 17, 2007: Cornelia Dangelmayr, "How Many 3-Pseudosegments can a Pseudoline Arrangements have?"
January 10, 2007: Patrick Baier, "The Crossing Number of Geometric Complete Graphs"
Talks in 2006:
December 20, 2006: Stefan Felsner, "Arrangements of pseudolines; news, problems, and goodies."
December 13, 2006: Kolja Knauer, "α-Orientations and Regular Oriented Matroids"
December 6, 2006: Kolja Knauer, "α-Orientations and FlipFlops"
November 29, 2006: Sarah Kappes, "Kombinatorik orthogonaler Flächen"
November 22, 2006: Florian Zickfeld, "α-Orientations and Bipartite Perfect Matchings"
November 15, 2006: Leonid Ioffe, "Constraint Programming"
November 1, 2006: Martin Pergel, "On Complicacy of Graphs Representable by Polygons"
October 25, 2006: Dominik Piesker, "Spezialfälle der 'list edge coloring conjecture'"
October 18, 2006: Stefan Felsner, "Baxter and Schröder Families"
August 23, 2006: Patrick Baier, "Adaptive colouring of upgrowing posets"
July 19, 2006: Cornelia Dangelmayr, "Dominating pairs in AT-free graphs"
July 5, 2006: Stefan Felsner, "Counting Bipolar Orientations on the Grid"
June 28, 2006: Sarah Kappes, "Convex-Pseudo Decompositions"
June 20, 2006: Maria del Pilar Sabariego Arenas, "3-Loop Networks with many Minimum Distance Diagrams"
June 14, 2006:Eric Fusy, "Enumeration of Bipolar Orientations"
June 7, 2006: Johan Nilsson, "The Gupta-Newman-Rabinovich-Sinclair Conjecture"
May 31, 2006: Florian Zickfeld, "Integer Realizations of 3-Polytopes"
May 24, 2006: Stefan Felsner, "Proofs of Untileability"
May 17, 2006: Cornelia Dangelmayr, "Cocomparability graphs of posets with (interval) dimension at most two"
May 10, 2006: Patrick Baier, "Online Chain Partitioning of Upgrowing Interval Posets - The Upper Bound"
May 3, 2006: Mareike Massow, "Semi Bar 1-Visibility Graphs"
April 26, 2006: Harald Schülzke, "The Normal Graph Conjecture for line graphs"
April 19, 2006: Steffen Melang, "Bipolar Orientations"
April 5, 2006: Maria del Pilar Sabariego Arenas, "Circulant Graphs and Binomial Ideals"
March15, 2006: Florian Zickfeld, "On the Number of 3-Orientations of a Triangulation"
March 8, 2006: Sarah Kappes, "A binary labeling for the angles of a plane quadrangulation"
March 1, 2006: Johan Nilsson, "Reachability substitutes"
February 22, 2006: Stefan Felsner, "Two Algorithms for Bipartite Cardinality Matching"
February 8, 2006: Mareike Massow, "Bar 1-Visibility Graphs - Introduction and First Results"
February 1, 2006: Stefan Felsner, "Counting Linear Extensions"
January 25, 2006: Georg Melamed, "Skelette 3-dimensionaler Ordnungen"
January 18, 2006: Cornelia Dangelmayr, "A Representation of the Subset "VPT" of Chordal Graphs as Intersection Graphs of Pseudosegments"
January 11, 2006: Patrick Baier, "The Upper Bound for Online Chain Covering of Upgrowing Interval Posets"
Talks in 2005:
December 14, 2005: Florian Zickfeld, "Schnyder Woods and Pairs of Non-Crossing Dyck Paths"
December 7, 2005: Stefan Felsner, "Box Graphs and Graph Dimension"
November 23, 2005: Viktor Blåsjö, "On the Braid Page of Gauss' Handbook 7"
November 23, 2005: Sarah Kappes, "Realizers for d-polytopes with d+2 vertices"
November 16, 2005: Cornelia Dangelmayr, "Relations within the class of intersection graphs"
November 9, 2005: Patrick Baier, "A special case of online chain covering of posets"
November 2, 2005: Stefan Felsner, "Dualization in Products of Chains"
October 26, 2005: Florian Pfender, "Visibility Graphs on Point Sets"
October 5, 2005: Mareike Massow, "What makes the treewidth large?"
September 21, 2005: Viktor Blåsjö, "Enumeration of Reduced Words in Combinatorial Group Theory "
September 14, 2005: Krisztián Tichler, "Lies and Hypercubes "
August 31, 2005: Florian Zickfeld, "A Schnyder Wood with no rigid AND coplanar embedding"
August 24, 2005: Sarah Kappes, "Orthogonal Surfaces - A combinatorial definition for characteristic points"
August 17, 2005: Eric Fusy, "Enumeration of d-polytopes with d+3 vertices"
August 10, 2005: Stefan Felsner, "Poset Polytopes and Linear Extensions"
July 13, 2005: Cornelia Dangelmayr, "Intersection Graphs"
July 6, 2005: Patrick Baier, "An upper bound for online chain covering"
June 29, 2005: Florian Pfender, "Closure and Hamiltonian Properties in Claw-free Graphs"
June 22, 2005: Kamil Kloch, "Partial Orders - fooling Alice"
June 15, 2005: Sarah Kappes, "What is an orthogonal complex?"
June 8, 2005: Krisztián Tichler, "A Combinatorial Property of Databases"
May 25, 2005: Dan Kral, "Claws and Paws"