**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

Room:MA 541Questions:email to schrezen [at] math.tu-berlin.de

**Next Talk: **Friday, Jul. 20, 12:00 noon (MA 541)

Speaker:Martin Balko

Title:On Erdős-Szekeres-type problems for $k$-convex point sets

Abstract:We study Erdős-Szekeres-type problems for so-called $k$-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set $S$ of points in the plane is $k$-convex if $S$ is a vertex set of a simple polygon that is intersected by every line in at most $k$ connected components.

We address several open problems about $k$-convex point sets. In particular, we extend the famous Erdős-Szekeres Theorem by showing that, for every fixed $k \in \mathbb{N}$, every set of $n$ points in the plane in general position (with no three collinear points) contains a $k$-convex subset of size at least $\Omega(\log^k{n})$. We also show that there are arbitrarily large $3$-convex sets of $n$ points in the plane in general position with no ($1$-)convex subset of size larger than $c\cdot \log{n}$ for some constant $c$. This gives a solution to a problem posed by Aichholzer et al.

This is joint work with Sujoy Bhore, Leonardo Martínez-Sandoval, and Pavel Valtr.

**Talks in 2018: **

July 10, 2018: Stephen Kobourov, "Multi-Level Steiner Tree"

June 29, 2018: Stefan Felsner, "Variationen über "Crossing Families""

June 22, 2018: Linda Kleist, "Convexity increasing morphs of planar graphs"

June 15, 2018: Felix Schröder, "Stand der Wissenschaft zur Borsuk-Vermutung und Max-Distance-Graphen"

May 25, 2018: Uwe Schauz, "The Combinatorial Nullstellensatz and List Edge Colorings of Graphs"

May 18, 2018: Kaja Wille, "Zerlegungen des Hyperwürfels in symmetrische Ketten"

May 11, 2018: Felix Schröder, "Zerlegungsgleichheit und die Dehn'sche Invariante"

May 04, 2018: Manfred Scheucher, "Arrangements of Pseudocircles: Triangles, Drawings, and Circularizability"

Apr 27, 2018: Patricia Franz, "Zur Komplexität von Sechseckskontaktdarstellungen"

Apr 20, 2018: Stefan Felsner, "A routing problem in arrangements with applications"

Apr 13, 2018: Felix Schröder, "On a crossing lemma for multigraphs"

Apr 06, 2018: Manfred Scheucher, "Partial Least-Squares Point Matching under Translations"

Mar 29, 2018: Hendrik Schrezenmaier, "Faster Algorithms for some Optimization Problems on Collinear Points"

Mar 15, 2018: Manfred Scheucher, "Minimal Geometric Graph Representations of Order Types"

Mar 01, 2018: Nadine Raasch, "Kontaktdarstellungen planarer Graphen mit Fünfecken"

Feb 23, 2018: Stefan Felsner, "Alternating permutations, Euler numbers and some bijections"

Feb 16, 2018: Linda Kleist, "Area-universality of triangulations"

Feb 09, 2018: Hendrik Schrezenmaier, "Universal slope sets for 1-bend planar drawings"

Jan 26, 2018: Bartosz Walczak, "Discrepancy of axis-parallel boxes"

Jan 19, 2018: Henning Heinrich, "Approaching area-universality"

Jan 12, 2018: Stefan Felsner, "Introduction to Placements of Rooks"

**Talks in 2017: **

Dec 08, 2017: Patrick Schnider, "Measures of depth for multiple points"

Dec 01, 2017: Hendrik Schrezenmaier, "Planar graphs as L-intersection graphs"

Nov 24, 2017: Hendrik Schrezenmaier, "Planar graphs as L-contact graphs"

Nov 17, 2017: Raphael Steiner, "Neumann-Lara-flows and the Two-Colour-Conjecture"

Nov 10, 2017: Bartosz Walczak, "Extending Partial Representations of Trapezoid Graphs"

Nov 03, 2017: Stefan Felsner, "More about Circle- and Pseudocirclearrangements"

Oct 27, 2017: Paul Wancura, "Rechteckszerlegungen auf Punktmengen"

Oct 20, 2017: Christoph Standke, "Zu Kodierung und Kreisbarkeit von Pseudokreisarrangements"

Oct 13, 2017: Linda Kleist, "On the Monge-Kontorovich transportation problem and Voronoi diagrams"

Oct 06, 2017: Hendrik Schrezenmaier, "Applications of a topological lemma in combinatorial geometry (circle packing, floorplans)"

Sep 22, 2017: Torsten Mütze, "A short proof of the middle levels theorem"

July 28, 2017: Stefan Felsner, "The chip firing game"

July 21, 2017: Linda Kleist, "Towards the Harary Hill conjecture"

June 16, 2017: Hendrik Schrezenmaier, "Maximum-area triangle in a convex polygon"

June 02, 2017: Stefan Felsner, "Maximum crossing number of cycles and bipartite graphs"

May 24, 2017: Linda Kleist, "Area-universal rectangular layouts"

May 19, 2017: Manfred Scheucher, "SageMath - Eine Kurzeinführung"

May 05, 2017: Hendrik Schrezenmaier, "Optimal Coding and Sampling of Triangulations"

April 27, 2017: Stefan Felsner, "Flipping Edges of Triangulations"

April 21, 2017: Till Miltzow, "The Art Gallery Problem is $\exists \mathbb{R}$-complete"

April 21, 2017: Michael Dobbins, "Stretching weighted pseudoline arrangements"

Mar 31, 2017: Linda Kleist, "Area-universality and $\forall\exists\mathbb R$ (\FER)-hardness"

Mar 24, 2017: Hendrik Schrezenmaier, "Morphing Schnyder drawings of plane triangulations"

Mar 03, 2017: Manfred Scheucher, "A superlinear lower bound on the number of 5-holes"

Feb 24, 2017: Janine Felten, "Sortieren mit partieller Information"

Feb 17, 2017: Kolja Knauer, "On lattice path matroid polytopes: integer points and Ehrhart polynomial"

Feb 10, 2017: Veit Wiechert, "Orthogonal tree decompositions and chromatic number"

Feb 03, 2017: Stefan Felsner, "Triangles in Arrangements"

Jan 27, 2017: Nikolai Kalischek, "Topologische Zeichnungen bipartiter Graphen"

Jan 20, 2017: Tom Trotter, "Trees and Circle Orders"

**Talks in 2016: **

Dec 15, 2016: Linda Kleist, "Equidissections of polygons"

Dec 9, 2016: Hendrik Schrezenmaier, "Squarability of rectangle arrangements"

Nov 30, 2016: Alexander Pilz, "Deciding monotonicity of complete topological graphs"

Nov 25, 2016: Veit Wiechert, "On the boxicity of graphs with no K_t minor"

Nov 18, 2016: Stefan Felsner, "Circle- and Pseudocirclearrangements"

Nov 3, 2016: Darius Wuttke, "Efficient algorithm for computing middle level Gray codes"

Oct 14, 2016: Linda Kleist, "Popular matchings"

Oct 7, 2016: Veit Wiechert, "Coloring, sparseness, and girth"

Aug 11, 2016: Hendrik Schrezenmaier, "Maximizing the Sum of Radii of Disjoint Balls or Disks"

Aug 5, 2016: Stefan Felsner, "Coloring Segments in Space"

July 22, 2016: Markus von der Heyde, "Rechtecks-Duale mit vorgegebenen Flächen"

July 8, 2016: Raman Sanyal, "Two double poset polytopes"

June 24, 2016: Franz Brandenburg, "Visibility Graphs of Geometric Objects"

June 20, 2016: Veit Wiechert, "Dominating Sets in Sparse Graphs"

June 10, 2016: Linda Kleist, "Union-closed set conjecture"

June 3, 2016: Hendrik Schrezenmaier, "How to morph planar graph drawings"

May 20, 2016: Raphael Steiner, "Existenz und Konstruktion von Dreiecks- und Fünfeckskontaktdarstellungen"

May 19, 2016: Julia Kraus, "Magische Eigenschaften von Graphen"

May 13, 2016: Stefan Felsner, "On the Erdős-Szekeres convex polygon problem"

May, 4, 2016: Veit Wiechert, "Centered colorings and order dimension"

April 29, 2016: Stefanie Wendisch, "q-Catalan Zahlen"

April 22, 2016: Stefan Felsner, "A Geometric Approach to Acyclic Orientations"

April 18, 2016: Linda Kleist, "Decomposing graphs into trees"

March 18, 2016: Veit Wiechert, "On Graphs that have the Erdos-Posa Property"

March 4, 2016: Lena Krauss, "De Bruijn Graphen mit Eulerkreisen als Ansatz für DNA Fragment Assembly"

February 26, 2016: Stefan Felsner, "Embedding Graphs on Wheel Point Sets."

February 19, 2016: Katharina Hoffmann, "k-lokal planare Graphen."

February 5, 2016: Hendrik Schrezenmaier, "Ein neuer Existenzbeweis für Kontaktdarstellungen mit homothetischen gleichseitigen Dreiecken."

January 28, 2016: Veit Wiechert, "Improved bounds for the dimension of posets whose cover graphs have bounded treewidth."

January 22, 2016: Tom Trotter, "Posets and Dimension"

January 8, 2016: Linda Kleist, "Coloring Graphs on Surfaces."

**Talks in 2015: **

December 18, 2015: Tillmann Miltzow, "An Approximation Algorithm and Parameterized Hardness of the Art Gallery Problem."

December 11, 2015: Felix Seibert, "Square Dissections and Transversal Structures."

December 4, 2015: Franz Brandenburg, "Semi-bar 1-visibility graphs."

November 27, 2015: Udo Hoffmann, "Polygon obstacle representations of graphs."

November 20, 2015: Björn Kapelle, "Kontakt- und Schnittdarstellungen planarer Graphen."

November 13, 2015: Stefan Felsner, "Drawings of K_{r,n}."

October 30, 2015: Linda Kleist, "Drawing planar graphs with prescribed face areas."

October 23, 2015: Veit Wiechert, "Graphs with locally bounded treewidth."

October 16, 2015: Udo Hoffmann, "The slope number of graphs."

October 8, 2015: Stefan Felsner, "Strongly monotone drawings of planar graphs."

October 2, 2015: Torsten Mütze, "Bipartite Kneser graphs are Hamiltonian."

September 25, 2015: Felix Seibert, "An algorithm for square contact representations."

September 18, 2015: Linda Kleist, "Points in the plane and depth."

September 8, 2015: Veit Wiechert, "The dimension of planar posets."

August 28, 2015: Udo Hoffmann, "Illumination of polygons with vertex lights."

August 21, 2015: Stefan Felsner, "Arrangements of Pseudolines on Dual Arrangements"

August 13, 2015: Linda Kleist, "Counting annular non-crossing matchings."

July 17, 2015: Veit Wiechert, "Queue layouts of graphs with bounded treewidth."

July 10, 2015: Udo Hoffmann, "Slope minimization of segment intersection graphs."

July 3, 2015: Stefan Felsner, "Drawings of K_{2,n}."

June 19, 2015: Steve Chaplick, "Partial Bar Visibility Representation Extension."

June 12, 2015: Linda Kleist, "Rainbow Connectivity."

June 5, 2015: Udo Hoffmann, "Visibility graphs of pseudo-polygons."

May 28, 2015: Kolja Knauer, "Drawing graphs with vertices and edges in convex position"

May 13, 2015: Piotr Micek, "Sparsity and dimension."

May 8, 2015: Veit Wiechert, "Classes of graphs with bounded expansion: examples and characterizations."

April 24, 2015: Kolja Junginger: "1:d-Graphen: Eine Verallgemeinerung planarer Triangulierungen."

April 17, 2015: Stefan Felsner, "Hook-formulae"

April 10, 2015: Steve Chaplick, "Intersection Graphs of Non-Crossing Paths."

March 26, 2015: Linda Kleist, "Chromatic Art Gallery Problem"

March 13, 2015: Udo Hoffmann, "Catching light rays with mirrors"

March 6, 2015: Veit Wiechert, "A new proof for the Aztec diamond theorem."

February 27, 2015: Piotr Micek, "Computing dimension of bounded width posets"

February 20, 2015: Stefan Felsner, "Crossing Numbers and Rotation Systems"

February 13, 2015: Nieke Aerts, "Power line route optimization."

February 6, 2015: Steve Chaplick, "Drawing the Complete Graph with a Planar Subgraph"

January 30, 2015: Udo Hoffmann, "Obstacle Representations of Graphs"

January 16, 2015: Linda Kleist, "Long Paths in Line Arrangements."

January 9, 2015: Piotr Micek, "Posets and minors."

**Talks in 2014: **

December 12, 2014: Veit Wiechert, "Dimension and Standard Examples"

December 5, 2014: Alexander Hopp, "Topologische Bucheinbettungen planarer Graphen."

December 5, 2014: Christoph Standke, "The list chromatic index of 1-factorable graphs."

November 28, 2014: Stefan Felsner, "Independent and hitting sets of some classes of rectangle intersection graphs."

November 21, 2014: Steve Chaplick, "Overlap Representations of Planar Graphs"

November 14, 2014: Udo Hoffmann, "Point visibility graphs and the existential theory of the reals."

October 31, 2014: Kolja Knauer, "Orienting Triangulations."

October 24, 2014: Jonatan Krolikowski, "Refined counting of linear extensions of posets."

October 23, 2014: Benjamin Rahman, "Würfelkonstaktdarstellungen von Graphen."

September 19, 2014: Torsten Ueckerdt, "On-line coloring between two lines."

August 22, 2014: Udo Hoffmann, "Representations of point visibility graphs."

August 15, 2014: Tillmann Miltzow, "Token Swapping"

August 8, 2014: Veit Wiechert, "Large dimensional posets with planar cover graphs"

August 1, 2014: Linda Kleist, "On the complexity of recognizing unit proper contact graphs of unit regular polygons."

July 25, 2014: Steve Chaplick, "Clique Separators in Neighbourhood Subtree Intersection Graphs"

July 11, 2014: Nieke Aerts, "Touching Triangle Representations of Biconnected Outerplanar Graphs"

June 27, 2014: Piotr Micek, "Pathwidth and nonrepetitive colorings of graphs "

June 20, 2014: Stefan Felsner, "Abstract Ham-Sandwich Cuts and Selection in Arrangements"

June 6, 2014: Sarah Spoenemann, "Kombinatorische Eigenschaften von bichromatischen Punktmengen und Arrangements."

May 28, 2014: Udo Hoffmann, "(Pseudo) Vertex-Edge Visibility Graphs in Polygons."

May 23, 2014: Irina Mustaţă, "Intersection graphs of unit squares and partial grid graphs"

May 22, 2014: Mirjam Plietzsch: "Durchmesser von höheren symmetrischen Shift-Graphen"

May 19, 2014: Veit Wiechert, "Balanced Pairs in Sets of Orderings with many initial Elements "

May 2, 2014: Stefan Felsner, "Generating and counting perfect matchings in bipartite regular graphs "

April 25, 2014: Yannik Stein, "The Complexity Class 'Polynomial-Time Local Search' (PLS)"

April 17, 2014: Steve Chaplick, "On (K_{1,3},even-hole)-free graphs."

April 11, 2014: Linda Kleist, "On Area-Universal Contact Representations with Orthogonal Polygons."

April 4, 2014: Nieke Aerts, "Grid-Path Contact Representations."

March 28, 2014: Udo Hoffmann, "Slopes of bipartite segment intersection graphs."

March 21, 2014: Katinka Becker, "Counting triangulations and related structures."

March 14, 2014: Piotr Micek, "Lower bounds for on-line graph colorings"

March 7, 2014: Irina Mustaţă "Opaque forests"

February 28, 2014: Stefan Felsner, "Bookembeddings and topological bookembeddings"

February 14, 2014: Veit Wiechert, "On the Dimension of Posets that do not have a large Standard Example as a subposet."

February 7, 2014: Steve Chaplick, "Graph Traversals and Restricted Families of Graphs"

January 31, 2014: Jean-Philippe Labbé, "Counting singletons and related structures "

January 24, 2014: Linda Kleist, "On unit distance graphs. "

January 17, 2014: Nieke Aerts, "Triangle contact representation of a planar graph and its dual. "

January 10, 2014: Piotr Micek, "On the number of edges in families of pseudo-discs "

**Talks in 2013: **

December 20, 2013: Udo Hoffmann, "Slopes of k-dir graphs."

December 13, 2013: Irina Mustaţă, "Graceful labelings of graphs"

December 6, 2013: Veit Wiechert, "On the Dimension of Posets that have a Cover Graph of bounded Treewidth"

November 29, 2013: Kolja Knauer, "Connected Covering Numbers."

November 22, 2013: Stefan Felsner, "Basics of Multitriangulations."

November 22, 2013: Christoph Hansknecht, "Methoden zur Berechnung von Tabellenkartogrammen"

November 15, 2013: Piotr Micek, "Making Octants Colorful."

November 1, 2013: Michael Kaufmann, "Slanted Orthogonal Drawings."

October 25, 2013: Daniel Heldt, "A (q-analogon)^2 for the number of bounded Motzkin paths."

October 17, 2013: Björn Kapelle, "Anwendungen der Entladungsmethode"

October 17, 2013: Manuel Hensel, "Layer Aware Codes"

October 11, 2013: Linda Kleist, "Plane Cubic Graphs and the Air-Pressure Method"

October 4, 2013: Stefan Felsner, "Evaluating Determinants Combinatorially"

September 20, 2013: Udo Hoffmann, "Extending partial representations of circle graphs"

September 12, 2013: Laura Gellert, "Gradsequenzen von gerichteten Graphen."

September 6, 2013: Nieke Aerts,"Henneberg Steps for Triangle Representations"

August 30, 2013: Katharina Jochemko, "An order-theoretic generalization of Polya's enumeration theorem"

August 23, 2013: Irina Mustaţă, "Untangling two systems of non-crossing curves"

July 26, 2013: Daniel Heldt, "For some $\alpha$ the face flip markov chain on the set of $alpha$-orientations is not rapidly mixing on planar triangulations of degree \leq 7"

July 19, 2013: Veit Wiechert, "Unit Interval Graphs and Balanced Pairs"

July 12, 2013: Nieke Aerts, "Decompositions of optimal 1-planar graphs"

July 3, 2013: Stefan Felsner, "Generalized Schnyder woods and box contact graphs in higher dimensions"

June 28, 2013: Linda Kleist, "On the queue and track number of planar graphs"

June 26, 2013: Debajyoti Mondal, "Acyclic Coloring with Few Division Vertices"

June 21, 2013: Thibault Manneville, "Counting edges of linear extension graphs"

June 14, 2013: Irina Mustaţă, "On visibility and k-visibility graphs"

June 7, 2013: Udo Hoffmann, "Interval Dimension and Bipartite Graphs."

May 31, 2013: Stefan Felsner, "GIGs and Dimension"

May 28, 2013: Lydia Scheel, "Die Max-Algebra und ihre Anwendung in der Graphentheorie und Optimierung"

May 17, 2013: Nieke Aerts, "Not all (2,2)-tight graphs have an L-Contact representation, nor an L-Contact representation allowing degenerate L-shapes."

May 16, 2013: Henrik Schrezenmaier, "Ein Luftdruckparadigma zur Optimierung von Zerlegungen"

May 7, 2013: Thomas Hixon, "Hook Graphs and More"

May 3, 2013: Linda Kleist, "On a Geometric Partitioning Problem."

April 26, 2013: Irina Mustaţă, "On the Recognition of Orthogonal Ray Graphs"

April 19, 2013: Isabel Beckenbach, "Hall Bedingung für Hypergraphen"

April 19, 2013: Maurice Liebner, "Von perfekten Matchings zu stabilen Hochzeiten"

April 12, 2013: Veit Wiechert, "The Balanced Pair Conjecture for Antimatroids"

April 5, 2013: Udo Hoffmann, "Clique Minimal Separator Decomposition and Intersection Graphs of Trees in a Cactus."

March 28, 2013: Ariadne Bolz, "Algebraische obere Schranken für Codes"

March 22, 2013: Daniel Heldt, "The face flip markov chain is rapidly mixing on 2-orientations of plane quadrangulations of maximum degree 4"

March 15, 2013: Nieke Aerts, "Straight Line Triangle Representations"

March 8, 2013: Irina Mustaţă, "Orthogonal Ray Graphs and Trees"

March 1, 2013: Tobias Buchwald, "Domino Tilings auf dem Torus."

February 22, 2013: Nieke Aerts, "Extremal Graphs Having No Independent Cutsets"

February 15, 2013: Stefan Felsner, "Table Cartograms"

January 18, 2013: Udo Hoffmann, "Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(log log n) colors."

January 11, 2013: Daniel Heldt, "The Shannon capacity of C_5"

**Talks in 2012:**

December 14, 2012: Nieke Aerts, "A characterisation of Generic Circuits."

December 7, 2012: Irina Mustata, "Efficient representations of unit grid intersection graphs"

November 30, 2012: Viola Mészáros, "Geometric graphs with few disjoint edges"

November 23, 2012: Stefan Felsner, "Exploiting Air-Pressure to Map Floorplans on Point Sets"

November 9, 2012: Matjaz Kovse, "Betweenness"

November 2, 2012: Kolja Knauer, "Partial Cubes: Lattices and Topology"

October 26, 2012: Udo Hoffmann, "Recognition of Simple-Triangle Graphs and Linear-Interval Orders is Easy"

October 19, 2012: Andrei Asinowski, "Orders induced by segments in floorplans, and (2-14-3, 3-41-2)-avoiding permutations"

October 12, 2012: Katharina Jochemko, "Arithmetic of marked order polytopes and monotone triangle reciprocity"

September 28, 2012: Tillmann Miltzow, "Unique Bichromatic Matchings"

September 21, 2012: Stefan Felsner, "Coloring rectangle intersection graphs"

August 31, 2012: Joachim Schröder, "Eigensequences; Kirchhoff and Graphs"

August 30, 2012: George B. Mertzios, "An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy"

August 28, 2012: George B. Mertzios, "The Intersection of Tolerance and Cocomparability Graphs"

August 24, 2012: Viola Mészáros, "Compatible matchings and planar straight line graphs"

August 10, 2012: Irina Mustata, "The jump number of 2-directional orthogonal ray graphs"

June 22, 2012: Nieke Aerts, "Straight Line Triangle Representation of a Graph"

June 8, 2012: Stefan Felsner, "Covering partial cubes with cuts"

June 1, 2012: Torsten Ueckerdt, "L-Contact and Segment-Contact is the same"

May 25, 2012: Kolja Knauer, "Drawing outerplanar graphs with few slopes"

May 11, 2012: Daniel Heldt, "Conductance, congestion and canonical paths of Markov chains"

May 4, 2012: Stefan Felsner, "A note on proportional contact representations"

May 2, 2012: Udo Hoffmann, "Recognition of Simple Triangle Graphs"

April 27, 2012: Irina Mustata, "Unit grid intersection graphs: Properties and relationships to other graph classes"

April 13, 2012: 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"