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

In summary, the conversation discusses the minimum number of intersection graphs of ##n## simple curves in the plane, which has been proven to be at least ##2^{\Omega(n^2)}##. The method for constructing these curves involves choosing independent detours for each line, resulting in (n-1)! different intersection graphs, but this is not enough to meet the minimum requirement and a different approach is needed.
  • #1
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
 
Mathematics news on Phys.org
  • #2
What is the definition of simple curve here? I'm not sure why you think convex sets are involved.
 
  • #3
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.
 

1. What is an intersection graph?

An intersection graph is a type of graph where the vertices represent a set of objects and the edges represent the intersections between those objects.

2. How many intersection graphs can be formed from ##n## convex sets in the plane?

The number of intersection graphs that can be formed from ##n## convex sets in the plane is equal to the Bell number, which is a sequence that counts the number of ways a set can be partitioned. The formula for the Bell number is B(n) = Σk=0 to n S(n,k), where S(n,k) is the Stirling number of the second kind.

3. What is the significance of studying the number of intersection graphs of ##n## convex sets in the plane?

Studying the number of intersection graphs of ##n## convex sets in the plane has practical applications in fields such as computer science, graph theory, and geometry. It can also provide insights into the complexity and structure of various mathematical problems.

4. Is there a known formula for calculating the number of intersection graphs of ##n## convex sets in the plane?

Yes, there is a known formula for calculating the number of intersection graphs of ##n## convex sets in the plane. It is given by the formula B(n) = 2^(n-1) - 1, where B(n) is the Bell number for ##n## convex sets.

5. Can the number of intersection graphs of ##n## convex sets in the plane be generalized to higher dimensions?

Yes, the concept of intersection graphs can be extended to higher dimensions, where the objects are represented as convex polytopes instead of convex sets. However, the formula for calculating the number of intersection graphs in higher dimensions is more complex and is an active area of research.

Suggested for: The number of intersection graphs of ##n## convex sets in the plane

Replies
3
Views
1K
Replies
3
Views
956
Replies
2
Views
1K
Replies
4
Views
1K
Replies
8
Views
835
Replies
2
Views
571
Back
Top