On the number of similar instances of a pattern in a finite set

MaRDI QIDQ504974zbMATH OpenFDO

Authors B. M. Ábrego, Silvia Fernández-Merchant, Daniel J. Katz, Levon Kolesnikov

Publication date 18 January 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.00076, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p39

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

arithmetic progressionequilateral trianglepatternsimilar copysimilar triangle

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Combinatorial aspects of finite geometries (05B25) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: New bounds on the number of similar or directly similar copies of a pattern within a finite subset of the line or the plane are proved. The number of equilateral triangles whose vertices all lie within an $n$-point subset of the plane is shown to be no more than $lfloor(4n-1)(n-1)/18floor$. The number of $k$-term arithmetic progressions that lie within an $n$-point subset of the line is shown to be at most $(n-r)(n+r-k+1)/(2k-2)$, where $r$ is the remainder when $n$ is divided by $k-1$. This upper bound is achieved when the $n$ points themselves form an arithmetic progression, but for some values of $k$ and $n$, it can also be achieved for other configurations of the $n$ points, and a full classification of such optimal configurations is given. These results are achieved using a new general method based on ordering relations.

Recommendations

• On the maximum number of translates in a point set
• On the maximum number of isosceles right triangles in a finite point set
• Almost similar configurations
• scientific article; zbMATH DE number 739015
• The maximal number of 3-term arithmetic progressions in finite sets in different geometries

Cites work

• scientific article; zbMATH DE number 1670651 (Why is no real title available?)
• scientific article; zbMATH DE number 3513795 (Why is no real title available?)
• scientific article; zbMATH DE number 3538432 (Why is no real title available?)
• scientific article; zbMATH DE number 739015 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 970812 (Why is no real title available?)
• scientific article; zbMATH DE number 2246588 (Why is no real title available?)
• A note on maximally repeated sub-patterns of a point set
• Centerpoint theorems for wedges
• Combinatorial geometry and its algorithmic applications. The Alcalá lectures
• Combinatorial geometry problems in pattern recognition
• Convex polyhedra in \(\mathbb{R}^3\) spanning \(\Omega(n^{4/3})\) congruent triangles
• Drawing Hamiltonian cycles with no large angles
• Finding squares and rectangles in sets of points
• How many unit equilateral triangles can be generated by \(N\) points in convex position?
• On Sets of Distances of n Points
• On minimum stars and maximum matchings.
• On the maximum number of equilateral triangles. I
• On the maximum number of translates in a point set
• On the structure of sets with many k-term arithmetic progressions
• Repeated Angles in Three and Four Dimensions
• Repeated angles in the plane and related problems
• Research Problems in Discrete Geometry
• Similar simplices in a \(d\)-dimensional point set
• Some extremal problems in geometry
• Structural results for planar sets with many similar subsets
• The Directions Determined by n Points in the Plane
• The number of isosceles right triangles determined by n points in convex position in the plane
• Unsolved problems in geometry

Cited in

(7)

• Multiple Recurrence and Finding Patterns in Dense Sets
• Geometric pattern matching reduces to \(k\)-SUM
• Structural results for planar sets with many similar subsets
• Geometric Pattern Matching Reduces to k-SUM.
• Patterns without a popular difference
• The maximal number of 3-term arithmetic progressions in finite sets in different geometries
• On the maximum number of translates in a point set

This page was built for publication: On the number of similar instances of a pattern in a finite set

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