Neodym's blog

Extremal Triangles
By Neodym, 10 years ago, translation, In English

Hi!

Recently I've met next problem: set of n lines is given, and they are in general position: no two lines are parallel, no three of them intersect at one point. This set of lines cuts plane into regions, some of which have finite area. Lest calculate an amount of triangles. Let f(n) be a minimal possible number of triangel, and g(n) — is a maximal number of triangles, which can occur.

It is true that f(n) = n - 2 for n ≥ 3. It's been unproven for hundred years, while somebady manage to use tricky matrix method (see article "Triangles and disasters").

Unfortunetely I can't find any inequalities for g(n) in the Internet. One can obtain trivial inequality using Euler formula: let's rewrite a picture as planar graph — where are vertices are line intersections, and edges are segments between vertices(which aren't intersect with some other segments inside). Let amount of vertices be V, amount of edges be E, and amount of faces (parts with finite area) be F. On given picture V = 10, E = 15, F = 6. Actually it's easy to get that g(5) = 5.

As it's known from Euler formula, V - E + F = 1(we don't count a face which is placed "outside"). It can be calculated easily that V and E equal and n(n - 2), respectively, that's why amount of parts with finite area is equal to — In fact, that gives a trivial inequality on g(n) as something of order .

So, we have a trouble — is this estimation good? Does an example with cn2 triangles exist, or maybe there some better estimation? To show, how this problem is untrivial, I'll show you an example which proves, that g(9) ≥ 14:

So, a challenge for society: I can prove (with example) that g(n) > c * nlog(n), where c is some predeterminated constant. Can somebody build an example with same amount of triangles? With better amount?:)

update: Examples which prove that was found by Endagorion and Ripatti, so, the topic is closed:) Example: let's draw a table with n rows and n columns, which almost parallel to each other. Than it's easy to draw 2n - 1 line, which are almost parallel to diagonal of this square, so that i'th line cuts i'th diagonal, so the amount of triangles is quadratic.

  • Vote: I like it
  • +67
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This thread is very far from being closed.

Proof that is in fact pretty easy and you can find it here: http://artofproblemsolving.com/community/c6h597095p3557339

I remember that I had once read article about it in Wikipedia and that it's still an open question to determine exact values of g, but it is possible to give very good estimations. I can't recall exact estimations, but it is possible that differences between some of them were 1. And given bound can't be much better, example with large g(n) can be improved much further than

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems funny, cause I met this problem when I was trying to improve constant c in this problem :)

    → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Some construction like this

gives (n + 1)2 - 3 triangles for 3n lines where n ≥ 2.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oops, my fault, it gives only constant instead of I thought earlier...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems from Swistakk's comment that bound cannot be reached, but your example is nice anyway:)

      By the way, aren't you an author of "Fragmentation algorithm and van der Waerden numbers" on Habrahabr?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I thought I found a counterexample for his proposition. I should check my results more diligently.

        Yes, that's me.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I like this algorithm and I even added your article to bibliography in my course work in MIPT. It was concerned with question "what is the minimal N such that if we color numbers 1, 2, ..., N in C colors then exist a nontrivial monochromatic solution of equation x + y + z = 3w", and I used that algorithm to find an answer for 4 colors:)

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Glad to see that my article is really useful!

            → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      UPD. Seems that this construction won't work.

      Nevertheless looks like I know how to improve it a bit.

      Consider 3 groups of almost parallel lines on the picture above. We can construct similar structure using them, but it will be very stretched on the plane. Like this:

      We will have 3 additional constructions with n / 9 lines. After that we can split (9 groups of lines now) again and build 9 additional structures having n / 27 lines.

      So, for n → ∞ we will have (n / 3)2 + 3(n / 9)2 + 9(n / 27)2 + ... + O(n) = = triangles.

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

Hey folks, can you check this construction?

Blue lines are bundles of k almost paraller lines, red ones are bundles of 2k ones.

Black dots are Endagorion's constructions, green is mine.

We have n = 12k lines total, for any black dot we have triangles and for the green dot. So, total number of triangles is

.

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Here is described a construction with n2 / 3 + O(n) triangles.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Construction is a bit similar to set of Simson lines. Cool.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems that lines not in general position are allowed there.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      For tniangles they are in the general position (aka simple arrangement as is stated in the paper).

      → Reply