Point-sets in general position with many similar copies of a pattern

MaRDI QIDQ5881919zbMATH OpenFDO

Authors Silvia Fernández-Merchant, B. M. Ábrego

Publication date 13 March 2023

Full work available at URL https://arxiv.org/abs/0905.0298

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: For every pattern $P$, consisting of a finite set of points in the plane, $S_P(n,m)$ is defined as the largest number of similar copies of $P$ among sets of $n$ points in the plane without $m$ points on a line. A general construction, based on iterated Minkovski sums, is used to obtain new lower bounds for $S_P(n,m)$ when $P$ is an arbitrary pattern. Improved bounds are obtained when $P$ is a triangle or a regular polygon with few sides. It is also shown that $S_P(n,m)geq{n}^{2-epsilon}$ whenever $m(n)oinfty$ as $noinfty$. Finite sets with no collinear triples and not containing the 4 vertices of any parallelogram are called emph{parallelogram-free}. The more restricted function $S_P^{parallel}(n)$, defined as the maximum number of similar copies of $P$ among parallelogram-free sets of $n$ points, is also studied. It is proved that $Omega(nlogn)leq{S}_P^{parallel}(n)leqO(n^{3/2})$.

This page was built for publication: Point-sets in general position with many similar copies of a pattern

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5881919)