I The number of intersection graphs of ##n## convex sets in the plane

[kmitza]

TL;DR

My friend gave me a problem that's been given in her combinatorial geometry class, I have been struggling with finding any ideas on how to do it. I don't have many tools from this topic and I might not understand any hints/solutions but I would still like to see if people have any ideas

Let $S$ be a set of n geometric objects in the plane. The intersection graph of $S$ is a
graph on $n$ vertices that correspond to the objects in $S$. Two vertices are connected
by an edge if and only if the corresponding objects intersect.

Show that the number of intersection graphs of $n$ simple curves in the plane is at least $2^{\Omega(n^2)}$.

I thought that this would be easy to see, online I found out that this is equivalent to finding this number is equivalent to finding the number for convex sets. This doesn't change the nature of the problem though and I think this shouldn't be too hard to prove but I can't figure it out. Any hints and ideas on how to think about this would be appreciated

 

[Office_Shredder]

What is the definition of simple curve here? I'm not sure why you think convex sets are involved.

 

[mfb]

You might be able to show how to construct curves in enough different ways to reach that limit.

Imagine a set of N parallel lines parallel to the x axis. At x=1, line 1 at the lowest y value makes a "detour" crossing 0...n-1 other curves above it. At x=2, line 2 makes a detour crossing 0...n-2 other curves above it. And so on. For each line the choice is independent and each choice leads to a different intersection graph, so we get (n-1)! different intersection graphs. That's not enough, you'll need a better approach, but it's an example how you can show a lower bound.