Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Algebraic and topological methods in combinatorics
 
doctoral thesis

Algebraic and topological methods in combinatorics

Vâlculescu, Adrian Claudiu  
2017

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

  • Files
  • Details
  • Metrics
Type
doctoral thesis
DOI
10.5075/epfl-thesis-7855
Author(s)
Vâlculescu, Adrian Claudiu  
Advisors
Pach, János  
Jury

Prof. Kathryn Hess Bellwald (présidente) ; Prof. János Pach (directeur de thèse) ; Prof. Thomas Liebling, Prof. Jozsef Solymosi, Prof. Nabil Mustafa (rapporteurs)

Date Issued

2017

Publisher

EPFL

Publisher place

Lausanne

Public defense year

2017-09-29

Thesis number

7855

Total of pages

121

Subjects

Erdős distance problems

•

distinct values

•

algebraic curves

•

Sylvester-Gallai

•

ordinary curves

•

point sets

•

convex sets

•

equipartitions

•

ham-sandwich theorem.

EPFL units
DCG  
Faculty
SB  
School
MATHGEOM  
Doctoral School
EDMA  
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/140742
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés