Analyzing Linkless Graphs on Donut Surfaces

Graphs are like dots connected by lines. You can think of them as drawings made of points and paths. Some of these drawings can twist and turn without tangling and are called linkless. Now, imagine you want to draw these graphs on a donut-shaped surface. It seems simple, but there’s a twist (pun intended). If the graph tangles while you draw it on the donut, it becomes a linked graph. This study is about finding out which graphs can be drawn on a donut without tangling, especially when the graphs are not linked to each other.

#Background: Graphs and Their Types

To understand what's going on, we need to talk about some basic terms.

• Planar Graphs: These are graphs that can be drawn on a flat surface without lines crossing. Think of drawing with crayons on paper.

• Toroidal Graphs: These are graphs that can be drawn on a donut-shaped surface without crossing lines. It's like trying to draw your crayon art on an inflatable pool toy.

• Linkless Graphs: Imagine two lines that can twist around each other without tying a knot. This is what we mean by linkless. It’s important because we want our graph drawings to avoid getting tangled.

In the world of graphs, some are naturally more complex, while others are simple. If a graph can be drawn on a donut without any lines crossing, it’s called toroidal. If it can be drawn on that donut without lines getting tied up with each other, it’s linkless or non-intrinsically linked (nIL for short).

#The Big Question

The question we want to answer is: if we have a graph that can be drawn on a donut and is also linkless, can we guarantee that we can draw it without any tangles on a standard donut shape?

So far, we know that for smaller graphs (with up to 9 points), if they can be drawn on the donut and avoid tangles, we can confidently say they can be drawn on a standard donut shape too. But what about bigger graphs?

#Links on the Donut

Let’s take a moment to talk about links. Links are like those annoying moments when two people try to pass each other in a hallway and end up tangled together.

• Linking Number: There’s a way to measure how tangled two paths are. We can count how these paths cross over each other. If they cross and twist in a certain way, we assign them values. At the end of the day, if the total value isn't zero, they are tangled.

#Exploring Graph Families

We can group graphs together based on common features, much like a club of friends with similar hobbies.

• Minor-Closed Families: These are groups of graphs that don't change their nature when you remove or shrink some of their parts. If you're a part of this club, you can’t be part of another club that doesn’t allow certain members.

We have two main clubs in our study: the club of toroidal graphs and the club of linkless graphs. All linkless graphs are also toroidal graphs, but not all toroidal graphs are linkless. Think of it like being a cat person; all cat people love pets, but not all pet lovers prefer cats.

#MaxnIL Graphs and Their Importance

Sometimes, we find special graphs that are at the top of the chain. These are called maxnIL graphs. They are linkless and can’t have any extra edges added without turning linked. They are like the head honchos in the linkless graph community.

Most of our study focuses on these maxnIL graphs because if we can figure out how to draw them linklessly on a donut, we can also work backward to see if it holds for all other graphs.

#Toroidal Obstructions

While exploring the world of toroidal graphs, we find some that don’t fit the linkless description. These are called toroidal obstructions, and they’re like the unfortunate party crashers that ruin the fun.

So far, we’ve discovered a few toroidal obstructions that can’t be drawn linklessly without twisting. The smallest one has 8 points and is the first we need to kick out of the linkless club.

#Finding MTN Graphs

To answer the big question, we need to find out which graphs can be drawn linklessly on a donut without tangling. We begin with smaller graphs and work our way up.

For the smaller graphs (like the ones with 6 or 7 points), we can confidently say they are linkless. As we climb higher, the challenge becomes more complex, especially when we encounter graphs of order 9.

#The Search for Linklessness

When we dig deeper into graphs of order 9, we use a variety of techniques and observations. We have a prior understanding that certain graphs are unlinkable.

Through a series of clever deductions, we can determine that from the twenty maxnIL graphs of order 9, only four cannot be drawn on the donut without tangling. These four troublemakers make our lives more interesting but also complicate our research.

#Tools of the Trade

Throughout this journey, we use various algorithms to help us keep track of which graphs we are dealing with. By applying these algorithms, we can outline conditions that determine if a graph can be drawn linklessly or not.

One helpful algorithm helps us identify linkless graphs based on their path crossings. This is crucial because it saves us from drawing each graph by hand. After all, who has the time for that?

#Proving Linklessness

Now that we have a solid understanding of the graphs we're working with, it's time to prove that a graph is linkless. We use our earlier definition of slopes and crossings, and we can set up a little test. If the list returned by our algorithm shows no conflicts or tangles, we can confidently say the graph is linkless.

#The Results

After countless hours of drawing, examining, and testing, we've gathered a complete collection of MTN graphs for orders ranging from 6 to 9. The findings indicate that all these graphs can be drawn on a donut without tangling, so party on!

#Future Directions

Having tackled the smaller graphs, we now want to see if we can extend this work to larger graphs. We believe there’s a good chance that all toroidal, nIL graphs could be linklessly drawn on a donut.

We’ve made significant strides, but the future will require a lot of work. Understanding the forbidden minors for these graph types might eventually lead us to stronger conclusions about their linkless behavior.

#Conclusion

In summary, we’ve taken a fun dive into the world of graphs on donuts, discovering how these mathematical shapes can exist without tangling. With our findings, we now have a better grasp of how these graphs function on a toroidal surface, and while there’s still more to dig into, we’re happy to have proven one thing: not all graphs like to get tangled up, and that’s a relief.