Monday, June 20, 2011

Planar Divisibility Graphs and The Bible

I've talked about graph theory here before in the context of Ramsey theory.

However, there are many other interesting graph theory problems.

A graph is said to be planar if one can draw it on a plane with none of the edges intersecting. So for example, K3, the graph formed by three vertices all of which connect to each other is planar, but the similar graph K5 formed by five vertices all of which connect is not planar.
We can also change our notion of graph by allowing our edges to have directions, and represent them with arrows rather than straight lines. Thus for example, if one wanted to use a graph to represent who knows the name of whom with a bunch of people, using a directed graph would be quite natural.

Over the last few days I have been thinking about divisibility graphs of sets. These graphs arise when one takes some set of positive integers and assigns each to a vertex then draws the corresponding arrows when one integer divides another. (So for example, if our set was was {1,2,4} then 1 would have arrows going to 2 and 4 and 2 would have an arrow going to 4). For convenience, I am ignoring the arrows that vertices would have going to themselves.
Now, assume one has a set of positive integers A and we know that corresponding divisibility graph is planar. What can we say about how large the set is. That is, if we let A(x) be the number of elements in A which are at most x, how fast does A(x) grow? It is not difficult to see that one can get A(x) to grow at least about as fast as x/log x. One does this by taking A to be the set of prime numbers. The resulting graph is certainly planar since it has no edges at all. Then the prime number theorem does the rest. With a small amount of tweaking, one can get this to grow at about 2x/log x since one can include all the numbers of the form 2p and still get a planar graph. I suspect that the actual best possible growth is on the order of x/log x but I'm not sure. One possible approach to making a large planar divisibility graph is to use the greedy algorithm. That is, throw 1 into the set and then go by induction on each integer, throwing in the next integer if it still allows a planar graph. If one call this set G, then the first number not in G is 18. It seems at first that G grows quickly, and G includes every prime number. But most large integers are in fact not in G, a result of the fact that most large integers have a lot of prime factors. For example, every multiple of 6 other than 6 and 12 is not in G.

Now, you may be thinking, "Josh, this is an interesting math problem, but the title mentioned the Bible. What does that have to do with anything?" The truth is that the connection is tenuous. The problem about planar divisibility graphs occurred to me when I was tutoring a professor's young kid in graph theory, and we discussed divisibility graphs. The professor's family is Orthodox, and so another graph we talked was to take different Biblical figures and make a graph representing who had met whom. The major graph had three large components, one corresponding to the patriarchal time period (with Abraham, Issac and Jacob as the most connected points), one to the time around the Exodus (with Moses at the center), and one at the early monarchy, with David, Samuel and Solomon as the main points. However, an issue came up. My young student wanted to add Eli, the high priest during most of the of Samuel to the graph. This raised an issue which neither he nor I knew the answer: Did Eli ever encounter David? The text does not mention such an event, but the chronology seems tentatively to allow such a meeting. I'm also unaware of any midrashim claiming that they met. I'm mentioning this here therefore for two reasons: One can any more knowledgeable readers point me to anything in the text itself which deals with this, or can any of my more midrashically inclined readers point me to any midrashim that address whether they met?


Sniffnoy said...

What if you replace the problem with a simpler set of forbidden minors? Like demanding that it be a tree?

Joshua said...

Thinking about your tree question made me realize that there's a fairly trivial and much better construction. Fix a k, and let A be the set of numbers that are the product of k distinct primes. From this construction, one can do at least as well as x (log log x)^m / log x, for any fixed m.

Sniffnoy said...

Heh, having no edges certainly does the job. What's next, having edges but no two that are next to each other?

aravind said...

Hi Joshua,

One can do better: A(x) >= x/2. Just take all integers greater than x/2 and <= x.

Joshua said...

avarind, There's a quantifier issue there. That's a set that you are choosing in terms of x. A should be chosen independently of x.