===== 2021 Session 5 : Geometric graphs and hypergraphs =====

In combinatorial geometry we study combinatorial questions in usually discrete geometric settings. Particularly important are **geometrically defined graphs**, e.g. intersection graphs of objects in d-dimensional space, **and hypergraphs**, e.g. whose vertices are points in the plane and whose hyperedges are those subsets that can be enclosed in a circle (or generally homothet of a fixed shape).

Understanding the structure and combinatorial properties of those graphs and hypergraphs, beyond being purely of mathematical interest, is crucial for applications in numerous fields, like physics and computer science.

There are a variety of questions to be investigated: **coloring, covering, decomposing or hitting problems**; questions about VC-dimension, epsilon-nets, and realizabilities; as well as **structural properties** like sparsity, or product structures. Hence we seek to gather experts together with mid-career and younger researchers from generally similar but specifically different backgrounds in combinatorial geometry. 

==== Organisers ====

[[https://i11www.iti.kit.edu/en/members/torsten_ueckerdt/index|Torsten Ueckerdt]] and [[https://sites.google.com/view/yuditsky/home|Lena Yuditsky]]


==== Workshop dates ====

**30 August (Monday) - 3 September (Friday) 2021**

==== Workshop Format ====

This is an **online workshop** with a focus on **problem solving in groups**. The workshop is scheduled for Monday (August 30) till Friday (September 3). We shall have some **experts giving a few talks** on Monday and Tuesday morning. There will be an open problem session on Monday, too, followed by an informal voting to split us into groups. The group assignment is neither strict nor final, and also the organization of the work within each group is handled loosely and left to the group members themselves. We meet in the afternoons for quick progress reports, and a wrap-up session on Friday. For the workshop to be productive and enjoyable, we suggest that you reserve at least 4 hours per day for the workshop.

We also hope to see you at the **socializing events**, maybe playing games, chatting or just enjoying ourselves :) 

==== Registration ====

The deadline for registration is August 18. In case that more people are interested to attend than we can handle, we might need to decline some. So we would be grateful for a timely registration, ideally as soon as possible.

Registration details: Please use the form sent in the invitation email. 

Registration deadline: **August 18** (Wednesday) (closed)

Confirmed participants:

  * [[torsten.ueckerdt@kit.edu|Torsten Ueckerdt]] (organiser)
  * [[yuditskyl@gmail.com|Lena Yuditsky]] (organiser)
  * Piotr Micek
  * Nora Frankl
  * David Wood
  * Dömötör Pálvölgyi
  * Zdeněk Dvořák
  * Balazs Keszegh
  * Tamara Mtsentlintze
  * Stefan Felsner
  * Bartosz Walczak
  * Linda Kleist
  * Daniel Gonçalves
  * Lena Schlipf
  * Fabian Klute
  * James Davies
  * Chaya Keller
  * Bruno Jartoux
  * Laura Merker
  * Paul Jungeblut
  * Nicolas Bousquet
  * Robert Hickingbotham
  * Vera Chekan
  * Jane Tan
  * Justin Dallant
  * Piotr Mikołajczyk
  * Shakhar Smorodinsky 


==== Open problems ====

For a smooth beginning of the workshop and an interesting set of open problems, we would like to ask all participants to submit any open problem they want to contribute to us beforehand. Please provide a brief description using the template sent in the invitation email. We will then prepare a small pdf booklet with all open problems and share it with the participants prior to the workshop. Please note that this list of problems is intended for the workshop participants only and problems shall not be distributed further without contacting its respective author(s).

Submission details: Please use the template sent in the invitation email. 

Submission deadline: **August 25** (Wednesday before the workshop) (closed)

==== Schedule ====

The workshop will have 3-4 talks about recent breakthroughs in the field (2 talks on Monday, 1 talk on Tuesday and possibly 1 talk on Wednesday) and the rest of the time dedicated to problem solving in groups and socializing.
  
  1. Monday, 30 August
    9.45am Welcome and Introduction
    10.15am Talk -- Zdeněk Dvořák
      “Product structure and related geometric representations”
    11.15am Coffee break
    11.30am Talk -- Dömötör Pálvölgyi
      “Coloring Geometric Hypergraphs”
    1.30pm Open problem session
    3pm Partitioning into groups
    4pm Coffee break
  2. Tuesday, 31 August
    10am Coffee break
    2pm Coffee break
    2.15pm Talk -- James Davies
      "Colouring circle graphs"
    3.15pm Progress report
  3. Wednesday, 1 September
    10am Coffee break
    2pm Coffee break
    3pm Progress report
    8pm Socializing
  4. Thursday, 2 September
    10am Coffee break
    2pm Coffee break
    3pm Progress report
  5. Friday, 3 September
    10am Coffee break
    2pm Coffee break
    2.30pm Wrap up meeting


(All the times should be read Central European Summer Time, i.e. UTC+2).

==== Talks ====

===Talk Monday 10.15am, Zdeněk Dvořák, "Product structure and related geometric representations"===

Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood recently proved that, rather
surprisingly, every planar graph is a subgraph of the product of a path and a
graph of treewidth at most 8.  Graphs with such a product structure can be
geometrically represented as touching graphs of axis-aligned boxes which are
the product of a unit interval with a hypercube.  We survey topics motivated by
these results, especially from the perspective of the graph sparsity theory.

===Talk Monday 11.30am, Dömötör Pálvölgyi, "Coloring Geometric Hypergraphs"===

I will survey results related to coloring geometric hypergraphs that arise from range spaces. We will be interested only in the big/fat hyperedges, i.e., in the ones that contain many vertices. For example, recently we have shown (joint work with Damasdi) that any finite set of planar points can be 3-colored such that any unit disk containing at least 666 points contains two differently colored points, but the same does not hold for disks of arbitrary radius. In my talk I'll highlight some questions left open, for a complete list, see https://coge.elte.hu/cogezoo.html.

===Talk Tuesday 2.15pm, James Davies, "Colouring circle graphs"===

We give a sketch of the proof that the maximum chromatic number of a circle graph with clique number at most $\omega$ is equal to $\Theta ( \omega \log \omega)$.

==== Research results ====

  * Davies, Keller, Kleist, Smorodinsky, Walczak. A solution to Ringel’s circle problem. https://arxiv.org/abs/2112.05042
  * Hickingbotham, Jungeblut, Merker, Wood. The product structure of squaregraphs. https://arxiv.org/abs/2203.03772
  * Dvorák, Daniel Gonçalves, Lahiri, Tan, Torsten Ueckerdt. On Comparable Box Dimension. https://arxiv.org/abs/2203.07686