Sparse Graphs Coalition

User Tools

Site Tools

Trace:
sessions:2021sessions:2021session5

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
sessions:2021sessions:2021session5 [2021/07/27 14:21] – [Registration] lenasessions:2021sessions:2021session5 [2022/03/18 10:02] (current) – [Research results] ross.kang
Line 6: Line 6:
  
 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.  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 ==== ==== Workshop dates ====
  
-**30 August-3 September 2021**+**30 August (Monday) - 3 September (Friday) 2021**
  
 ==== Workshop Format ==== ==== Workshop Format ====
Line 23: Line 28:
 Registration details: Please use the form sent in the invitation email.  Registration details: Please use the form sent in the invitation email. 
  
-Registration deadline: Wednesday, **August 18**+Registration deadline: **August 18** (Wednesday) (closed)
  
 Confirmed participants: Confirmed participants:
Line 29: Line 34:
   * [[torsten.ueckerdt@kit.edu|Torsten Ueckerdt]] (organiser)   * [[torsten.ueckerdt@kit.edu|Torsten Ueckerdt]] (organiser)
   * [[yuditskyl@gmail.com|Lena Yuditsky]] (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 ==== ==== 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 following template: _____________. 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).+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** _____________+Submission details: Please use the template sent in the invitation email. 
  
-Submission deadline: **August 25** (Wednesday before the workshop)+Submission deadline: **August 25** (Wednesday before the workshop) (closed)
  
-==== Schedule (tbc) ====+==== 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. 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   1. Monday, 30 August
-    9h45 - Introduction+    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   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   3. Wednesday, 1 September
 +    10am Coffee break
 +    2pm Coffee break
 +    3pm Progress report
 +    8pm Socializing
   4. Thursday, 2 September   4. Thursday, 2 September
 +    10am Coffee break
 +    2pm Coffee break
 +    3pm Progress report
   5. Friday, 3 September   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). (All the times should be read Central European Summer Time, i.e. UTC+2).
  
-==== Talks (tbc) ====+==== 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
  
sessions/2021sessions/2021session5.1627395670.txt.gz · Last modified: 2021/07/27 14:21 by lena