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/09/13 07:43] – ross.kangsessions: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 ====
Line 33: Line 38:
   * David Wood   * David Wood
   * Dömötör Pálvölgyi   * Dömötör Pálvölgyi
 +  * Zdeněk Dvořák
   * Balazs Keszegh   * Balazs Keszegh
   * Tamara Mtsentlintze   * Tamara Mtsentlintze
Line 102: Line 108:
 ==== Talks ==== ==== Talks ====
  
-Talk Monday 10.15am +===Talk Monday 10.15am, Zdeněk Dvořák, "Product structure and related geometric representations"===
- +
-Zdeněk Dvořák +
-  "Product structure and related geometric representations"+
  
 Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood recently proved that, rather Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood recently proved that, rather
Line 114: Line 117:
 these results, especially from the perspective of the graph sparsity theory. these results, especially from the perspective of the graph sparsity theory.
  
-Talk Monday 11.30am +===Talk Monday 11.30am, Dömötör Pálvölgyi, "Coloring Geometric Hypergraphs"===
- +
-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. 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 +===Talk Tuesday 2.15pm, James Davies, "Colouring circle graphs"===
- +
-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)$. 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.1631519012.txt.gz · Last modified: 2021/09/13 07:43 by ross.kang