Kobon triangle problem
How many non-overlapping triangles can be formed in an arrangement of lines?
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.
Known upper bounds
Saburo Tamura proved that the number of nonoverlapping triangles realizable by lines is at most . G. Clément and J. Bader proved more strongly that this bound cannot be achieved when is congruent to 0 or 2 (mod 6). 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:
Solutions yielding this number of triangles are known when is 3, 4, 5, 6, 7, 8, 9, 13, 15 or 17. For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than the upper bound.
Given an optimal solution with k0 > 3 lines, other Kobon triangle solution numbers can be found for all ki-values where
|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||A032765|
|Clément and Bader's upper bound||1||2||5||7||11||15||21||26||33||39||47||55||65||74||85||95||107||119||133||-|
|best known solution||1||2||5||7||11||15||21||25||32||38||47||53||65||72||85||93||104||115||130||A006066|
- Roberts's triangle theorem, on the minimum number of triangles that lines can form
- ^ a b 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.
- ^ "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.
- ^ Ed Pegg Jr. on Math Games
- Johannes Bader, "Kobon Triangles"