Pach, JánosVâlculescu, Adrian Claudiu2017-09-202017-09-20201710.5075/epfl-thesis-7855https://infoscience.epfl.ch/handle/20.500.14299/140742urn:nbn:ch:bel-epfl-thesis7855-2The 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}enErdős distance problemsdistinct valuesalgebraic curvesSylvester-Gallaiordinary curvespoint setsconvex setsequipartitionsham-sandwich theorem.thesis::doctoral thesis