Few distinct distances implies no heavy lines or circles

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set of n points determines o(n) distinct distances, then no line contains Omega(n (7/8)) points of and no circle contains Omega(n (5/6)) points of . We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang [20]. A significant difference between our approach and that of [19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that any set of

e(n)

points in general position in the plane contains

n

points in convex position. In 1935, Erd\H{o}s and Szekeres proved that

e(n) \le {2n-4 \choose n-2}+1

and later in 1961, they obtained the lower bound

2^{n-2}+1 \le e(n)

, which they conjectured to be optimal. We prove that

e(n) \le {2n-5 \choose n-2}-{2n-8 \choose n-3}+2

. In a recent breakthrough, Suk proved that

e(n) \le 2^{n+O\left(n^{2/3}\log n\right)}

. We strengthen this result by extending it to pseudo-configurations and also improving the error term. Combining our results with a theorem of Dobbins et al., we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes T'{o}th and by Pach and T'{o}th, respectively. Let

c(n)

(and

c'(n)

) denote the smallest positive integer

N

such that any family of

N

pairwise disjoint convex bodies in general position (resp.,

N

convex bodies in general position, any pair of which share at most two boundary points) has an

n

members in convex position. We show that

c(n)\le c'(n)\le 2^{n+O\left(\sqrt{n\log n}\right)}

. Given a point set

P

in the plane, an ordinary circle for

P

is defined as a circle containing exactly three points of

P

. We prove that any set of

n

points in the plane, not all on a line or a circle, determines at least

\frac{1}{4}n^2-O(n)

ordinary circles. We determine the exact minimum number of ordinary circles for all sufficiently large

n

, and characterize all point sets that come close to this minimum. We also consider the orchard problem for circles, where we determine the maximum number of circles containing four points of a given set and describe the extremal configurations. A special case of the Schwartz-Zippel lemma states that given an algebraic curve

C\subset \mathbb{C}^2

of degree

d

and two finite sets

A,B\subset \mathbb{C}

, we have

|C\cap (A\times B)|=O_d(|A|+|B|)

. We establish a two-dimensional version of this result, and prove upper bounds on the size of the intersection

|X\cap (P\times Q)|

for a variety

X\subset \mathbb{C}^4

and finite sets

P,Q\subset \mathbb{C}^2

. A key ingredient in our proofs is a two-dimensional version of a special case of Alon's combinatorial Nullstellensatz. As corollaries, we generalize the Szemer'edi-Trotter point-line incidence theorem and several known bounds on repeated and distinct Euclidean distances. We use incidence geometry to prove some sum-product bounds over arbitrary fields. First, we give an explicit exponent and improve a recent result of Bukh and Tsimerman by proving that

\max \{ |A+A|, |f(A, A)|\}\gg |A|^{6/5}

for any small set

A\subset \mathbb{F}_p

and quadratic non-degenerate polynomial

f(x, y)\in \mathbb{F}_p[x, y]

. This generalizes the result of Roche-Newton et al. giving the best known lower bound for the term

\max \{ |A+A|, |A \cdot A |\}

. Secondly, we improve and generalize the sum-product results of Hegyv'{a}ri and Hennecart on

\max\{ |A+B|, |f(B,C)|\}

, for a specific type of function

f

. Finally, we prove that the number of distinct cubic distances generated by any small set

A\times A\subset \mathbb{F}_p^2

\Omega(|A|^{8/7})

, which improves a result of Yazici et al.

EPFL2017

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

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

\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

\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

EPFL2017

Constructing reparameterization invariant metrics on spaces of plane curves

Martin Bauer, Martins Bruveris

Metrics on shape spaces are used to describe deformations that take one shape to another, and to define a distance between shapes. We study a family of metrics on the space of curves, which includes several recently proposed metrics, for which the metrics are characterised by mappings into vector spaces where geodesics can be easily computed. This family consists of Sobolev-type Riemannian metrics of order one on the space Imm(S-1, R-2) of parameterized plane curves and the quotient space Imm(S-1,R-2)/Diff (S-1) of unparameterized curves. For the space of open parameterized curves we find an explicit formula for the geodesic distance and show that the sectional curvatures vanish on the space of parameterized open curves and are non-negative on the space of unparameterized open curves. For one particular metric we provide a numerical algorithm that computes geodesics between unparameterized, closed curves, making use of a constrained formulation that is implemented numerically using the RATTLE algorithm. We illustrate the algorithm with some numerical tests between shapes. (C) 2014 Elsevier B.V. All rights reserved.

Elsevier2014

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that any set of

e(n)

points in general position in the plane contains

n

points in convex position. In 1935, Erd\H{o}s and Szekeres proved that

e(n) \le {2n-4 \choose n-2}+1

and later in 1961, they obtained the lower bound

2^{n-2}+1 \le e(n)

, which they conjectured to be optimal. We prove that

e(n) \le {2n-5 \choose n-2}-{2n-8 \choose n-3}+2

. In a recent breakthrough, Suk proved that

e(n) \le 2^{n+O\left(n^{2/3}\log n\right)}

c(n)

(and

c'(n)

) denote the smallest positive integer

N

such that any family of

N

pairwise disjoint convex bodies in general position (resp.,

N

convex bodies in general position, any pair of which share at most two boundary points) has an

n

members in convex position. We show that

c(n)\le c'(n)\le 2^{n+O\left(\sqrt{n\log n}\right)}

. Given a point set

P

in the plane, an ordinary circle for

P

is defined as a circle containing exactly three points of

P

. We prove that any set of

n

points in the plane, not all on a line or a circle, determines at least

\frac{1}{4}n^2-O(n)

ordinary circles. We determine the exact minimum number of ordinary circles for all sufficiently large

n

C\subset \mathbb{C}^2

of degree

d

and two finite sets

A,B\subset \mathbb{C}

, we have

|C\cap (A\times B)|=O_d(|A|+|B|)

. We establish a two-dimensional version of this result, and prove upper bounds on the size of the intersection

|X\cap (P\times Q)|

for a variety

X\subset \mathbb{C}^4

and finite sets

P,Q\subset \mathbb{C}^2

\max \{ |A+A|, |f(A, A)|\}\gg |A|^{6/5}

for any small set

A\subset \mathbb{F}_p

and quadratic non-degenerate polynomial

f(x, y)\in \mathbb{F}_p[x, y]

. This generalizes the result of Roche-Newton et al. giving the best known lower bound for the term

\max \{ |A+A|, |A \cdot A |\}

. Secondly, we improve and generalize the sum-product results of Hegyv'{a}ri and Hennecart on

\max\{ |A+B|, |f(B,C)|\}

, for a specific type of function

f

. Finally, we prove that the number of distinct cubic distances generated by any small set

A\times A\subset \mathbb{F}_p^2

\Omega(|A|^{8/7})

, which improves a result of Yazici et al.

EPFL2017

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

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

\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

\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

EPFL2017