- #1

kmitza

- 17

- 4

- TL;DR Summary
- 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

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