Kobon triangle problem


The Kobon triangle problem is an unsolved problem in combinatorial geometry first stated by Kobon Fujimura. The problem asks for the largest number N 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.
Saburo Tamura proved that the largest integer not exceeding k/3 provides an upper bound on the maximal number of nonoverlapping triangles realizable by k lines. In 2007, a tighter upper bound was found by Johannes Bader and Gilles Clément, by proving that Tamura's upper bound couldn't be reached for any k congruent to 0 or 2. The maximum number of triangles is therefore at most one less than Tamura's bound in these cases. Perfect solutions are known for k = 3, 4, 5, 6, 7, 8, 9, 13, 15 and 17. For k = 10, 11 and 12, the best solutions known reach a number of triangles one less than the upper bound.
As proved by G. Clément and J. Bader, the solutions for k > 2 are bounded above by
Given a perfect solution with k0>3 lines, other Kobon triangle solution numbers can be found for all ki-values where
by using the procedure by D. Forge and J. L. Ramirez Alfonsin. For example, the solution for k0 = 5 leads to the maximal number of nonoverlapping triangles for k = 5,9,17,33,65,...
k3456789101112131415161718192021OEIS
Tamura's upper bound on N1258111621263340475665748596107120133
Clément and Bader's upper bound1257111521263339475565748595107119133-
best known solution1257111521253238475365728593104115130

Examples