Orchard-planting problem

Last updated
An arrangement of nine points (related to the Pappus configuration) forming ten 3-point lines. Orchard-planting problem.svg
An arrangement of nine points (related to the Pappus configuration) forming ten 3-point lines.

In discrete geometry, the original orchard-planting problem (or the tree-planting problem) asks for the maximum number of 3-point lines attainable by a configuration of a specific number of points in the plane. There are also investigations into how many k-point lines there can be. Hallard T. Croft and Paul Erdős proved

Contents

where n is the number of points and tk is the number of k-point lines. [1] Their construction contains some m-point lines, where m > k. One can also ask the question if these are not allowed.

Integer sequence

Define to be the maximum number of 3-point lines attainable with a configuration of n points. For an arbitrary number of n points, was shown to be in 1974.

The first few values of are given in the following table (sequence A003035 in the OEIS ).

n4567891011121314
12467101216192226

Upper and lower bounds

Since no two lines may share two distinct points, a trivial upper-bound for the number of 3-point lines determined by n points is

Using the fact that the number of 2-point lines is at least ( Csima & Sawyer 1993 ), this upper bound can be lowered to

Lower bounds for are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of was given by Sylvester, who placed n points on the cubic curve y = x3. This was improved to in 1974 by Burr , Grünbaum ,and Sloane  ( 1974 ), using a construction based on Weierstrass's elliptic functions. An elementary construction using hypocycloids was found by Füredi & Palásti (1984) achieving the same lower bound.

In September 2013, Ben Green and Terence Tao published a paper in which they prove that for all point sets of sufficient size, n>n0, there are at most

3-point lines which matches the lower bound established by Burr, Grünbaum and Sloane. [2] Thus, for sufficiently large n, the exact value of is known.

This is slightly better than the bound that would directly follow from their tight lower bound of for the number of 2-point lines: proved in the same paper and solving a 1951 problem posed independently by Gabriel Andrew Dirac and Theodore Motzkin.

Orchard-planting problem has also been considered over finite fields. In this version of the problem, the n points lie in a projective plane defined over a finite field.( Padmanabhan & Shukla 2020 ).

Notes

  1. The Handbook of Combinatorics, edited by László Lovász, Ron Graham, et al, in the chapter titled Extremal Problems in Combinatorial Geometry by Paul Erdős and George B. Purdy.
  2. Green & Tao (2013)

Related Research Articles

<span class="mw-page-title-main">Binomial distribution</span> Probability distribution

In probability theory and statistics, the binomial distribution with parameters n and p is the discrete probability distribution of the number of successes in a sequence of n independent experiments, each asking a yes–no question, and each with its own Boolean-valued outcome: success or failure. A single success/failure experiment is also called a Bernoulli trial or Bernoulli experiment, and a sequence of outcomes is called a Bernoulli process; for a single trial, i.e., n = 1, the binomial distribution is a Bernoulli distribution. The binomial distribution is the basis for the popular binomial test of statistical significance.

<span class="mw-page-title-main">Pigeonhole principle</span> If there are more items than boxes holding them, one box must contain at least two items

In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item. For example, if one has three gloves, then there must be at least two right-handed gloves, or at least two left-handed gloves, because there are three objects, but only two categories of handedness to put them into. This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population of London is greater than the maximum number of hairs that can be present on a human's head, then the pigeonhole principle requires that there must be at least two people in London who have the same number of hairs on their heads.

<span class="mw-page-title-main">Floor and ceiling functions</span> Nearest integers from a number

In mathematics and computer science, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x, denoted x or floor(x). Similarly, the ceiling function maps x to the least integer greater than or equal to x, denoted x or ceil(x).

In mathematics, Bertrand's postulate states that for each there is a prime such that . First conjectured in 1845 by Joseph Bertrand, it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.

In Euclidean geometry, a regular polygon is a polygon that is direct equiangular and equilateral. Regular polygons may be either convex, star or skew. In the limit, a sequence of regular polygons with an increasing number of sides approximates a circle, if the perimeter or area is fixed, or a regular apeirogon, if the edge length is fixed.

<span class="mw-page-title-main">Diagonal</span> In geometry a line segment joining two nonconsecutive vertices of a polygon or polyhedron

In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word diagonal derives from the ancient Greek διαγώνιος diagonios, "from angle to angle" ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a rhombus or cuboid, and later adopted into Latin as diagonus.

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In mathematics, the nth Motzkin number is the number of different ways of drawing non-intersecting chords between n points on a circle. The Motzkin numbers are named after Theodore Motzkin and have diverse applications in geometry, combinatorics and number theory.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given n points and m lines in the Euclidean plane, the number of incidences is

<span class="mw-page-title-main">Sylvester–Gallai theorem</span> Existence of a line through two points

The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. It is named after James Joseph Sylvester, who posed it as a problem in 1893, and Tibor Gallai, who published one of the first proofs of this theorem in 1944.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, they are piecewise-linear Jordan curves consisting of finitely many line segments. They include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

<span class="mw-page-title-main">Heawood conjecture</span> Theorem on graph coloring on surfaces

In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS: A000934, the chromatic number or Heawood number.

<span class="mw-page-title-main">Discrete uniform distribution</span> Probability distribution on equally likely outcomes

In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution wherein a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n. Another way of saying "discrete uniform distribution" would be "a known, finite number of outcomes equally likely to happen".

In mathematics, the Cheeger constant of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold.

<span class="mw-page-title-main">K-set (geometry)</span> Points separated from others by a line

In discrete geometry, a -set of a finite point set in the Euclidean plane is a subset of elements of that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a -set of a finite point set is a subset of elements that can be separated from the remaining points by a hyperplane. In particular, when , the line or hyperplane that separates a -set from the rest of is a halving line or halving plane.

<span class="mw-page-title-main">Kobon triangle problem</span>

The Kobon triangle problem is an unsolved problem in combinatorial geometry first stated by Kobon Fujimura (1903-1983). The problem asks for the largest number N(k) of nonoverlapping triangles whose sides lie on an arrangement of k lines. Variations of the problem consider the projective plane rather than the Euclidean plane, and require that the triangles not be crossed by any other lines of the arrangement.

<span class="mw-page-title-main">Crossing number (graph theory)</span> Fewest edge crossings in drawing of a graph

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

<span class="mw-page-title-main">Turán's brick factory problem</span> On minimizing crossings in bicliques

In the mathematics of graph drawing, Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. The problem is named after Pál Turán, who formulated it while being forced to work in a brick factory during World War II.

In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson. It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by Stanisław Trybuła and Czen Ping.

References