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

zbMATH Open1353.05030arXiv1501.00076MaRDI QIDQ504974FDOQ504974

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)

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.

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

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

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

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)

Cites Work

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

Cited In (7)

• 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
• Multiple Recurrence and Finding Patterns in Dense Sets

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)