Kobon triangle problem

Saburo Tamura proved that the number of nonoverlapping triangles realizable by ${\displaystyle k}$ lines is at most ${\displaystyle \lfloor k(k-2)/3\rfloor }$. G. Clément and J. Bader proved more strongly that this bound cannot be achieved when ${\displaystyle k}$ is congruent to 0 or 2 modulo 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: $${\displaystyle {\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 ${\displaystyle k}$ is 3, 4, 5, 6, 7, 8, 9, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 or 33.^[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 ${\displaystyle k}$ can be improved: ${\displaystyle \lfloor k(k-7/3)/3\rfloor }$.^[4] This bound can be reached for 10, 12 and 16.^[3]

The upper bound for k = 11 has long been thought not to be reachable, which was shown to be correct in 2025 by Pavlo Savchuk with the use of a SAT solver.^[6]

Lower bounds have been established using an iterative construction derived from previous bounds. For any given integer ${\displaystyle k}$, the value follows the recurrence relation ${\displaystyle {\text{Kobon}}(k-1)+k/2-1}$, where ${\displaystyle {\text{Kobon}}(k-1)}$ represents the number of non-overlapping triangles formed by ${\displaystyle k-1}$ lines. While this construction is applicable to any ${\displaystyle k}$, it is particularly significant for even values; starting from a known odd solution yields a tight lower bound that may be optimal as presented by Alejandro Zarzuelo Urdiales in 2026.^[7]

The following bounds are known:

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 ${\displaystyle k>3}$ lines and ${\displaystyle {\tfrac {1}{3}}k(k-1)}$ triangles (the maximum possible for ${\displaystyle k>3}$), with certain additional properties, to another solution with ${\displaystyle K=2k-1}$ lines and ${\displaystyle {\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

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

The traditional problem of triangles in the Euclidean plane is often broken down into two parts: the equivalent problem but with an arrangement of pseudolines, and the problem of the stretchability of the pseudoline arrangements that have an optimal triangle count. When working with pseudolines, pure combinatorics and group theory may be leveraged without needing to worry about violating rules like the theorem of Pappus or Desargues's theorem.^[4][8]

A pseudoline arrangement is said to be stretchable if it is combinatorially equivalent to a line arrangement, meaning that you can straighten each one while maintaining the order in which each crosses each other, but it is complete for the existential theory of the reals to distinguish stretchable arrangements from non-stretchable ones.^[9][10]

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

19 lines, 107 triangles	21 lines, 133 triangles

• Roberts's triangle theorem, on the minimum number of triangles that ${\displaystyle n}$ lines can form