Sparse Graphs Coalition

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.

Torsten Ueckerdt and Lena Yuditsky

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

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 :)

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 (organiser)
• 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

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)

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).

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.

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.

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)$.

• 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