Kobon triangle problem

Last updated November 04, 2024

Kobon triangles generated with 3, 4 and 5 straight line segments. Kobon triangles.gif — Kobon triangles generated with 3, 4 and 5 straight line segments.

Unsolved problem in mathematics:

How many non-overlapping triangles can be formed in an arrangement of

k

lines?

(more unsolved problems in mathematics)

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.^[1]

Known upper bounds

Saburo Tamura proved that the number of nonoverlapping triangles realizable by $k$ lines is at most $\lfloor k(k-2)/3\rfloor$ . G. Clément and J. Bader proved more strongly that this bound cannot be achieved when $k$ is congruent to 0 or 2 (mod 6).^[2] The maximum number of triangles is therefore at most one less in these cases. The same bounds can be equivalently stated, without use of the floor function, as: ${\begin{cases}{\frac {1}{3}}k(k-2)&{\text{when }}k\equiv 3,5{\pmod {6}};\\{\frac {1}{3}}(k+1)(k-3)&{\text{when }}k\equiv 0,2{\pmod {6}};\\{\frac {1}{3}}(k^{2}-2k-2)&{\text{when }}k\equiv 1,4{\pmod {6}}.\end{cases}}$

Solutions yielding this number of triangles are known when $k$ is 3, 4, 5, 6, 7, 8, 9, 13, 15, 17, 19, 21, 25 or 29.^[3]^[4]^[5] For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than this upper bound.

Furthermore, the upper bound for even values $k$ can be improved: $\lfloor k(k-7/3)/3\rfloor$ .^[4] This bound can be reached for 10, 12 and 16.^[3]

Known constructions

The following bounds are known:

k	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	...	25	...	29	OEIS
Tamura's upper bound on N(k)	1	2	5	8	11	16	21	26	33	40	47	56	65	74	85	96	107	120	133	...	191	...	261	A032765
Improvements on Tamura's ^[2]^[4]	1	2	5	7	11	15	21	25	33	38	47	54	65	72	85	94	107	117	133	...	191	...	261	-
best known solution	1	2	5	7	11	15	21	25	32	38	47	53	65	72	85	93	107	115	133	...	191	...	261	A006066

In the projective plane

The version of the problem in the projective plane allows more triangles. In this version, it is convenient to include the line at infinity as one of the given lines, after which the triangles appear in three forms:

ordinary triangles among the remaining lines, bounded by three finite line segments,
triangles bounded by two rays that meet at a common apex and by a segment of the line at infinity, and
triangles bounded by a finite line segment and by two parallel rays that meet at a vertex on the line at infinity.

For instance, an arrangement of five finite lines forming a pentagram, together with a sixth line at infinity, has ten triangles: five in the pentagram, and five more bounded by pairs of rays.

D. Forge and J. L. Ramirez Alfonsin provided a method for going from an arrangement in the projective plane with $k>3$ lines and ${\tfrac {1}{3}}k(k-1)$ triangles (the maximum possible for $k>3$ ), with certain additional properties, to another solution with $K=2k-1$ lines and ${\tfrac {1}{3}}K(K-1)$ triangles (again maximum), with the same additional properties. As they observe, it is possible to start this method with the projective arrangement of six lines and ten triangles described above, producing optimal projective arrangements whose numbers of lines are

6, 11, 21, 41, 81, ... .

Thus, in the projective case, there are infinitely many different numbers of lines for which an optimal solution is known.^[1]

Examples

3 lines, 1 triangle
4 lines, 2 triangles
5 lines, 5 triangles
6 lines, 7 triangles
7 lines, 11 triangles

Related Research Articles

The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integers in which each term is obtained from the previous term as follows: if a term is even, the next term is one half of it. If a term is odd, the next term is 3 times the previous term plus 1. The conjecture is that these sequences always reach 1, no matter which positive integer is chosen to start the sequence. The conjecture has been shown to hold for all positive integers up to 2.95×10²⁰, but no general proof has been found.

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction without special information, called the "trapdoor". Trapdoor functions are a special case of one-way functions and are widely used in public-key cryptography.

In geometry, inversive geometry is the study of inversion, a transformation of the Euclidean plane that maps circles or lines to other circles or lines and that preserves the angles between crossing curves. Many difficult problems in geometry become much more tractable when an inversion is applied. Inversion seems to have been discovered by a number of people contemporaneously, including Steiner (1824), Quetelet (1825), Bellavitis (1836), Stubbs and Ingram (1842–3) and Kelvin (1845).

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

<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.

In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in a given area, the smallest triangle area will be at most inversely proportional to the square of the number of points. His conjecture was proven false, but the asymptotic growth rate of the minimum triangle area remains unknown.

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.

The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher Elgamal in 1985.

<span class="mw-page-title-main">No-three-in-line problem</span> Geometry problem on grid points

The no-three-in-line problem in discrete geometry asks how many points can be placed in the $grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".$

<span class="mw-page-title-main">Hadwiger–Nelson problem</span> Mathematical problem

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for set theory.

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<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 .$

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

In discrete geometry, the original orchard-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 $where n is the number of points and t k is the number of k -point lines. Their construction contains some m -point lines, where m > k . One can also ask the question if these are not allowed.$

In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.

In the mathematical field of graph theory, the pancake graphP_n or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations transitive by prefix reversals.

Roberts's triangle theorem, a result in discrete geometry, states that every simple arrangement of $lines has at least triangular faces. Thus, three lines form a triangle, four lines form at least two triangles, five lines form at least three triangles, etc. It is named after Samuel Roberts, a British mathematician who published it in 1889.$

References

1 2 Forge, D.; Ramírez Alfonsín, J. L. (1998), "Straight line arrangements in the real projective plane", Discrete and Computational Geometry , 20 (2): 155–161, doi: 10.1007/PL00009373 .
1 2 "G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007" (PDF). Archived from the original (PDF) on 2017-11-11. Retrieved 2008-03-03.
1 2 Ed Pegg Jr. on Math Games
1 2 3 Bartholdi, Nicolas; Blanc, Jérémy; Loisel, Sébastien (2008), "On simple arrangements of lines and pseudo-lines in $\mathbb {P} ^{2}$ and $\mathbb {R} ^{2}$ with the maximum number of triangles" (PDF), in Goodman, Jacob E.; Pach, János; Pollack, Richard (eds.), Surveys on Discrete and Computational Geometry: Proceedings of the 3rd AMS–IMS–SIAM Joint Summer Research Conference "Discrete and Computational Geometry—Twenty Years Later" held in Snowbird, UT, June 18–22, 2006, Contemporary Mathematics, vol. 453, Providence, Rhode Island: American Mathematical Society, pp. 105–116, arXiv: 0706.0723 , doi:10.1090/conm/453/08797, ISBN 978-0-8218-4239-3, MR 2405679
↑ A006066

External links

Johannes Bader, "Kobon Triangles"

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[forge-1] 1 2 Forge, D.; Ramírez Alfonsín, J. L. (1998), "Straight line arrangements in the real projective plane", Discrete and Computational Geometry , 20 (2): 155–161, doi: 10.1007/PL00009373 .

[bacl-2] 1 2 "G. Clément and J. Bader. Tighter Upper Bound for the Number of Kobon Triangles. Draft Version, 2007" (PDF). Archived from the original (PDF) on 2017-11-11. Retrieved 2008-03-03.

[games-3] 1 2 Ed Pegg Jr. on Math Games

[Bartholdi-4] 1 2 3 Bartholdi, Nicolas; Blanc, Jérémy; Loisel, Sébastien (2008), "On simple arrangements of lines and pseudo-lines in $\mathbb {P} ^{2}$ and $\mathbb {R} ^{2}$ with the maximum number of triangles" (PDF), in Goodman, Jacob E.; Pach, János; Pollack, Richard (eds.), Surveys on Discrete and Computational Geometry: Proceedings of the 3rd AMS–IMS–SIAM Joint Summer Research Conference "Discrete and Computational Geometry—Twenty Years Later" held in Snowbird, UT, June 18–22, 2006, Contemporary Mathematics, vol. 453, Providence, Rhode Island: American Mathematical Society, pp. 105–116, arXiv: 0706.0723 , doi:10.1090/conm/453/08797, ISBN 978-0-8218-4239-3, MR 2405679

[5] A006066

[1]

[2]

[3]

[4]

[5]