CoGe Seminar

Besides the CoGe Seminar you may also be interested in the Geometry Seminar of the Rényi Institute.

2020 Spring Semester - every Tuesday at 14:00 in room 3-607, ELTE

2019 March 17
Spring break

2020 March 10
Géza Tóth: Crossing numbers, drawings

Abstract: The (usual) crossing number of a graph is the minimum number of edge crossings over all drawings. We compare some different versions of this parameter and show some results about their relationships.

Removing even crossings, pdf
Thirteen Problems on Crossing Numbers, pdf
On the Pair-Crossing Number, pdf
Note on the Pair-crossing Number and the Odd-crossing Number, pdf
A better bound for the pair-crossing number, pdf
Decidability of string graphs, pdf

2020 March 3
Narmada Varadarajan: Nearly linear monotone paths in edge-ordered graphs

Abstract: How long a monotone path can one always find in any edge-ordering of the complete graph \(K_n\)? This question was first asked by Chvátal and Komlós in 1971. It seems to have interesting applications to geometry - for instance, it can be translated into a problem about non-crossing paths in certain geometric graphs. The prevailing conjecture is that one can always find a monotone path of linear length, but the best known lower bound is \(n^{1 - o(1)}\).

Matija Bucic, Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, Adam Zsolt Wagner: Nearly-linear monotone paths in edge-ordered graphs, arXiv.

2020 February 25
Dömötör Pálvölgyi: Hasse diagrams with large chromatic number

Abstract: For every positive integer n, we construct a Hasse diagram with n vertices and chromatic number \(\Omega(n^{1/4})\), which significantly improves on the previously known best constructions of Hasse diagrams having chromatic number \(\Theta(\log n)\), but still leaves a significant gap, as the best upper bound is \(\tilde\Omega(n^{1/2})\). The proof uses a simple statement from the theory of forbidden matrix patterns. Is it possible to extend the lower bound for 2-dimensional posets, i.e., for Delaunay graphs of rectangles?

Andrew Suk, István Tomon: Hasse diagrams with large chromatic number, arXiv.

2020 February 18
Sameer Desai: Uniformity of Point Samples in Metric Spaces Using Gap Ratio

Abstract: Teramoto et al. [Inserting points uniformly at every instance. IEICE Transactions, 2006.] defined a spatial uniformity measure of a finite point set in a unit square in \(\mathbb{R}^2\) called gap ratio. We generalize the definition of this measure over all metric spaces. The generalized definition is basically a ratio between the covering radius and the packing radius of points in the given metric space. A uniform distribution of points according to this measure gives a thin covering and a tight packing i.e., low gap ratio. This gives rise to the question of sampling points while minimising the gap ratio. We solve optimization related questions about selecting uniform point samples from metric spaces, which may be continuous or discrete. In the optimization framework, we study
- lower bounds on gap ratio for different metric spaces;
- hardness results;
- approximation algorithms and hardness of approximation results;
- existence of core sets for both the static and streaming point set.

Arijit Bishnu, Sameer Desai, Arijit Ghosh, Mayank Goswami, Subhabrata Paul: Uniformity of point samples in metric spaces using gap ratio, arXiv.