Algebraic and topological methods in combinatorics

The present thesis deals with problems arising from discrete mathematics, whose proofs make use of tools from algebraic geometry and topology. The thesis is based on four papers that I have co-authored, three of which have been published in journals, and one has been submitted for publication (and also appeared as a preprint on the arxiv, and as an extendend abstract in a conference). Specifically, we deal with the following four problems: \begin{enumerate} \item We prove that if $M\in \mathbb{C}^{2\times2}$ is an invertible matrix, and $B_M:\mathbb{C}^2\times\mathbb{C}^2\to\mathbb{C}$ is a bilinear form $B_M(p,q)=p^TMq$, then any finite set $S$ contained in an irreducible algebraic curve $C$ of degree $d$ in $\mathbb{C}^2$ determines $\Omega_d(|S|^{4/3})$ distinct values of $B_M$, unless $C$ is a line, or is linearly equivalent to a curve defined by an equation of the form $x^k=y^l$, with $k,l\in\mathbb{Z}\backslash\\{0\\}$, and $\gcd(k,l)=1$. \item We show that if we are given $m$ points and $n$ lines in the plane, then the number of distinct distances between the points and the lines is $\Omega(m^{1/5}n^{3/5})$, as long as $m^{1/2}\le n\le m^2$. Also, we show that if we are given $m$ points in the plane, not all collinear, then the number of distances between these points and the lines that they determine is $\Omega(m^{4/3})$. We also study three-dimensional versions of the distinct point-line distances problem. \item We prove the lower bound $\Omega(|S|^4)$ on the number of ordinary conics determined by a finite point set $S$ in $\mathbb{R}^2$, assuming that $S$ is not contained in a conic, and at most $c|S|$ points of $S$ lie on the same line (for some $0<c<1$). We say that a conic is \emph{ordinary} for $S\subset \mathbb{R}^2$ if it is determined by five points of $S$, and contains no other points of $S$. We also provide constructions, showing that our bound is the best possible. \item Given $nk$ points in general position in the plane, colored with two colors, with at least $n$ points of each color, we prove that one can find $n$ pairwise disjoint convex sets, each set containing precisely $k$ of the points, not all of the same color. Also, we show that if $P$ is a set of $n(d+1)$ points in general position in $\mathbb{R}^d$, colored by $d$ colors, with at least $n$ points of each color, then one can always find $n$ pairwise disjoint $d$-dimensional simplices with vertices from $P$, each simplex containing points of every color. \end{enumerate}

Pach, János
Lausanne, EPFL
Other identifiers:
urn: urn:nbn:ch:bel-epfl-thesis7855-2

Note: The status of this file is: EPFL only

 Record created 2017-09-20, last modified 2020-10-28

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)