# List of articles to refer at Doctoral seminar

This page is administrated by Robert Šámal. If you want to refer some unreserved article, write me an e-mail.

## Available articles

It is well-known that every set of $n$ points in the plane in general position determines at least $\Omega(\sqrt{n})$ pairwise crossing line segments. It is widely conjectured that one should be always able to find linearly many such line segments, but the $\Omega(\sqrt{n})$-bound remained the best known bound for decades. In this paper, the authors almost solve this problem by showing that we always have at least $\Omega(n^{1-o(1)})$ pairwise crossing segments. The method they use is not very complicated, so this should be fairly simple to present.

The author proves a first improvement on the bound for the weak $\epsilon$-nets in the plane, which addresses one of the truly improtant problems in combinaotrial geometry and gives a first improvement for this problem since 1992. More specifically, for a positive $\varepsilon$, let $f_2(\varepsilon)$ be the smallest positive number $f$ such that, for any finite underlying set $P$ of points in the plane, one can pierce any convex set containing at least $\varepsilon |P|$ points from $P$ using only $f$ points from the plane. The main result in this paper shows that $f_2(\varepsilon) = O(1/\varepsilon^{3/2+\gamma})$ for any positive $\gamma$.

This paper is a collection of results from extremal combinatorics, for which the authors give short and elegant proofs. The topics considered include independent arithmetic progressions, concentration for Ramsey numbers of random graphs, and Ramsey multiplicity. Some of the proofs yield full or partial solutions to open problems. It would be nice to present in detail a selection of the problems from the paper.

The authors study a parameter $r_k(s,t;n)$, which generalizes Ramsey numbers $r_k(s,n)$ of coplete $k$-uniform hypergraphs $K^k_s$ and $K^k_n$ and which was introduced by Erdos to shed more light on the growth rate of Ramsey numbers. The authors almost prove a old conjecture by Erdos and Hajnal, for which Erdos offered 500 dollars, about the growth rate of $r_k(s,t;n)$.

A graph is k-universal if it contains every graph on k vertices as an induced subgraph. The problems that have received the most interest in this area are to find a k-universal graph with as few vertices as possible and to understand for which n a typical n-vertex graph is k-universal. In this paper both of these problems are effectively resolved, which essentially closes the book on the study of k-universal graphs.

Call a collection of photographs `consistent' if there is a same scene that these are photographs of (from different points of view). For the case when the `scene' is just a set of points, we construct a collection of 101 photographs such that every 100 of them are consistent, but all of them together are inconsistent. Preliminary version appeared in SoCG'18.

The authors propose an algorithm to find maximum cliques in $c$-closed graphs: graphs where if two vertices have at least $c$ common neighbors, then they are adjacent. Such property tends to be true for graphs of social networks.

An interesting graph coloring problem is solved by probabilistic tools well worth the study. Working knowledge of probabilistic method required.

A variant of a well-known hat guessing game. And a collection of great techniques used to analyze it: probabilistic method, Lovász Local Lemma and the Combinatorial Nullstellensatz. Great place to learn the technique from one of the grand masters.

An interesting algebraic construction of triangle-free graphs that tends to appear in many different contexts (extremal graph theory, coding theory, geometry).

The original Kakeya problem asks for a minimum area shape which allows for a unit segment to be rotated within itself by 360 degrees. This classical problem has some surprising answers which deserves a short discussion of its own. This paper discusses the "inverse" problem. Given convex shapes $P$ and $Q$, how large can $P$ be made so that it can be rotated by 360 degrees inside $Q$ and prove an old conjecture for this problem.

This paper discusses three basic geometric optimization problems over $n$ points related to covering things by disks. Two of these problems are known to be NP-hard. The interesting thing is that they consider what some might dismiss as trivial case: the input set of points are collinear. They present fast algorithms for this case.

Planar point location is one of the classic problems in Computational Geometry that one studies in introductory courses on CG/Algorithms. This paper presents improved algorithms for orthogonal case of the problem. A nice paper for data-structures enthusiasts!

This paper presents examples of some problems that can be solved in polynomial time in the worst case and are hard even in average case for slightly smaller polynomial times. A nice paper related to fine-grained complexity that has been becoming very popular recently and which roughly aims to prove lower bounds for polynomial-time solvable problems assuming that some famous problems have no better solutions than what is known.

This paper discusses a fast way to find a minor H in bounded degree graphs assuming that a linear number of edges must be removed from the input graph to make it H-minor-free. Sublinear times appear surprising since one apparently doesn't even need to read the whole input, but that is the usual deal in results dealing with things such as property testing. A good choice of a paper if you have never seen sublinear algorithms.

Lower bounds in complexity theory look abysmal and various explanatory results exist as to why we don't have better lower bounds. This paper falls in this regime and proves that even some very weak improvements in lower bounds for a certain complexity class ($TC^0$ to be precise) can give very strong separation from other classes.

A graph without a triangle and with maximal degree D has chromatic number at most $(1+o(1)) \frac{D}{\log D}$. This was proved by Johansson but never published. Reed and Molloy basically wrote a book about this proof. Here this result is proved in a few pages by a beautiful probabilistic argument (called entropy compression). It is possible to just present Section 2, if time allows we can see generalization for graphs with bounded clique size.

This paper proposes a new algorithmic framework called "partial rejection sampling" to draw samples exactly from a product distribution conditioned on none of a number of bad events occurring. This is due to a new connection with the Lovász local lemma.

This paper provides a randomized data structure maintaining minimum spanning forest in a dynamic graph. Updates take expected worst-case time of $O(n^{1/2-\varepsilon})$. This bound is first improvement over a 25 year old bound of $O(\sqrt{n})$.

This rather long paper describes the geodesic walk for sampling Riemannian manifolds and application to generating random points from the interior of polytopes specified by m inequalities. The problem of generating random samples from polytopes is an important problem with applications to volume estimation among others.

The main result is an algorithm to approximately count the number of solutions to a CNF formula under some restrictions closing an exponential gap between the upper and lower bounds. They also show that under Lovász Local Lemma-like conditions one can also generate approximately uniformly at random from the set of all satisfying assigments. The length of the paper should be ideal for the PhD seminar.

The authors discuss local algorithms - algorithms that at each step take into account only a bounded neighborhood of the input graph - and discuss their power to solve Semidefinite programs. A nice paper.

Graph limit approach to a new version of random graphs: we first choose random vertices from an interval [0,1] and then assign the edges at random -- but with probability depending on the distance of the vertices. An opportunity to study a recent technique (graphons, etc.) in a new setting.

Again, a paper in learning theory about minimizing regret in prediction based on expert advised when experts can be chosen in some optimal way at any point.

Problem vysetrovany v clanku spada vpodstate do linearni algebry. Autori uvadeji nekolik motivaci a souvislosti (testovani polynomialnich identit, rekonstrukce matic maleh hodnosti, teorie kodu a dalsi), z nichz staci zminit jen nektere podle vyberu. K prezentaci vybrat jenom cast, napr. je mozne se zamerit na rekonstrukci matic maleh hodnosti - tim by se z tohoto dlouhatanskeho clanku mohl vybrat rozumne dlouhy kus.

Jak generovat nahodny rovinny graf, a to rychle. Kombinuje zname vysledky o vytvorujicich funkcich pro rovinne grafy s nedavnou myslenkou Boltzmannovych nahodnych generatoru (Duchon, Flajolet, Louchard, Schaeffer). Oboji je potreba pekne objasnit, asi i s pouzitim puvodnich clanku. Tezsi clanek, mozna vhodny i pro 2 lidi.

Shows parameterized hardness results for counting perfect matchings under a counting variant of Strong Exponential Time Hypothesis.

Improved bounds for a decentralized, local algorithm to transform any regular graph (with degree \(\Omega(\log{n}))\) into an expander.

A better derandomization of Clark's LP algorithm to give improved runtime dependence on the dimension.

Exploring a graph with memory less than \(O(\log{n})\) when the memory units can be dropped off and picked up by agents like pebbles used to mark nodes.

Shows that there exists a "small" partial order representing strongly stable matchings of a graph. Also gives algorithms to compute such a representation.

Uses LP duality to give lower bound on the competitiveness of online algorithms.

Multiarmed bandit is a well-studied subject where we need to make decisions with uncertain outcomes (unknown probabilities), we want to (eventually) learn what decisions are good, but not to pay too much for making bad decisions along the way. In this paper theorems about the situation are proved using tools from information theory (relative entropy, etc.).