1/n. Slow-moving thread on a series of related, relaxing puzzles. They all involve this game:
Label all vertices and edges of a graph. Use each number 1,2,3,... exactly once (don’t miss any). At each vertex the sum of its label and its incident edge labels must be a constant, h.
Label all vertices and edges of a graph. Use each number 1,2,3,... exactly once (don’t miss any). At each vertex the sum of its label and its incident edge labels must be a constant, h.
2/n The labeling is called “total” because vertices AND edges are labeled.
It’s called “vertex magic” because we form a sum at each vertex, and—magically—get the same result (called the magic constant) each time.
The 2 examples suggest questions, eg: which constants are ok&why?
It’s called “vertex magic” because we form a sum at each vertex, and—magically—get the same result (called the magic constant) each time.
The 2 examples suggest questions, eg: which constants are ok&why?
3/n With the “weight” of a vertex being the sum of its label with its incident edge labels, we maximize the sum of all weights (and therefore the magic constant) by placing the biggest labels on the edges.
-Different magic constants are possible. 12 would be the largest for C_3.
-Different magic constants are possible. 12 would be the largest for C_3.
4/n But of course, if C_3 has a labeling (VMTL) with a magic constant of h, it must also have another one with a magic constant of 21-h, because...
Idea: replace big labels with small and vice versa (generalize it!)
Idea: replace big labels with small and vice versa (generalize it!)
5/n. Here is a way to label any cycle of odd length (perhaps you’ve discovered this?! Perhaps while looking at this thread?)
Pick an edge, label it 1. Traveling clockwise, skip an edge, then label 2, skip an edge then 3, etc. Since the cycle is *odd* you will get to every edge.
Pick an edge, label it 1. Traveling clockwise, skip an edge, then label 2, skip an edge then 3, etc. Since the cycle is *odd* you will get to every edge.
6/n. With hints (if desired) from the preceding, one can find a VMTL for the odd cycle C_n with constant
h=2.5n+1.5. Also (duality) another VMTL with
h=3.5n+1.5.
What about other h?
“Applied basic number theory” lurks everywhere, making this great for students of all levels. Eg.
h=2.5n+1.5. Also (duality) another VMTL with
h=3.5n+1.5.
What about other h?
“Applied basic number theory” lurks everywhere, making this great for students of all levels. Eg.
7/n. Amazingly, it is not known (for general n) which numbers are magic constants for VMTLs for C_n.
Candidates must be between 2.5n+1.5 and 3.5n+1.5.
Computer searches strongly suggest all such integers work, provided n>6.
So, please solve it!
Some mid-thread comic relief:
Candidates must be between 2.5n+1.5 and 3.5n+1.5.
Computer searches strongly suggest all such integers work, provided n>6.
So, please solve it!
Some mid-thread comic relief:
8/n. Next, a look at a couple of bipartite graphs
(one can color the vertices with 2 colors; vertices with the same color are not adjacent)
including complete bipartite graphs and even cycles.
(one can color the vertices with 2 colors; vertices with the same color are not adjacent)
including complete bipartite graphs and even cycles.
9/n. I love this next one—it uses traditional magic squares (which have constant row sum, column sum and diagonal sum).
Since we don’t need the diagonal, we freely interchange two columns so that the biggest label is in a useless spot.
Then delete it to get a VMTL:
K_{2,2}=C_4.
Since we don’t need the diagonal, we freely interchange two columns so that the biggest label is in a useless spot.
Then delete it to get a VMTL:
K_{2,2}=C_4.
10/n. I learned that magic square trick at a colloquium by Jim MacDougall, at SIU Carbondale in December 2001.
That same talk he conjectured that every regular graph of degree at least 2 (except for one—stay tuned) has a VMTL.
Show K_{1,3} is not magic to get a sense for why.
That same talk he conjectured that every regular graph of degree at least 2 (except for one—stay tuned) has a VMTL.
Show K_{1,3} is not magic to get a sense for why.
11/n. In addition to Jim, let me highlight the other authors of the original paper on the subject.
First, Mirka Miller. This special edition of the Austrasian Journal of Combinatorics was in her honour.
ajc.maths.uq.edu.au/pdf/69/ajc_v69…
First, Mirka Miller. This special edition of the Austrasian Journal of Combinatorics was in her honour.
ajc.maths.uq.edu.au/pdf/69/ajc_v69…
12/n. The other authors of the original paper on vertex magic graphs are Slamin and Wallis. Here is the page for the very prolific Professor Slamin:
inacombs.id/slamin/
inacombs.id/slamin/
13/n I was very fortunate, during my brief time at SIU to meet Wal Wallis.
In addition to the paper, he co-wrote this fantastic book, coauthored by Alison Marr.
Thanks @dralimarr ! Here’s a link. It’s is full of open problems, so it’s ideal for students:
springer.com/gp/book/978081…
In addition to the paper, he co-wrote this fantastic book, coauthored by Alison Marr.
Thanks @dralimarr ! Here’s a link. It’s is full of open problems, so it’s ideal for students:
springer.com/gp/book/978081…
14/n. Perhaps you believe that K_{1,3} is not magic.
The idea is that, since v has degree 3 and the other vertices degree 1, one imagines placing the lowest labels at v; but this still gives v a larger weight than the other vertices could ever have.
So, lack of regularity hurts.
The idea is that, since v has degree 3 and the other vertices degree 1, one imagines placing the lowest labels at v; but this still gives v a larger weight than the other vertices could ever have.
So, lack of regularity hurts.
15/n. What’s more surprising is the much more general fact that
K_{n,n+2} is also never vertex magic.
Here’s a hint: in the *regular* bipartite graphs, the VMTLs all had:
sum of pink labels=sum of black labels.
(Prove it has to be!) For K_{2,3}, however something else .. why?
K_{n,n+2} is also never vertex magic.
Here’s a hint: in the *regular* bipartite graphs, the VMTLs all had:
sum of pink labels=sum of black labels.
(Prove it has to be!) For K_{2,3}, however something else .. why?
16/n. In the early days (~2000) many discoveries were (naturally!) made by generating examples by computer, finding patterns and proving they worked. I took the “swimming upstream” approach of trying to do computational mathematics without any computing.
Here’s what happened.
Here’s what happened.
17/n. Any cubic graph with a perfect matching has a VMTL.
This is quite general!
Rather than describing this result in detail here, I’ll focus on one from Ian Gray’s thesis (which is easier to describe, similar, and is a much more spectacular result).
sciencedirect.com/science/articl…
This is quite general!
Rather than describing this result in detail here, I’ll focus on one from Ian Gray’s thesis (which is easier to describe, similar, and is a much more spectacular result).
sciencedirect.com/science/articl…
18/n. Gray: Any Hamilton regular graph of odd order has a VMTL:
Idea: start with the Hamilton cycle and build up. Label the odd cycle (as before), add a 2-factor and orient these new edges. Slide the vertex label onto the outgoing new edge&Label a vertex to balance the incoming!
Idea: start with the Hamilton cycle and build up. Label the odd cycle (as before), add a 2-factor and orient these new edges. Slide the vertex label onto the outgoing new edge&Label a vertex to balance the incoming!
19/n. Ok I’ll do the cubic graphs with a perfect matching has a VMTL.
There are n matching edges (called spokes). Label them (randomly) with n+1, n+2, ... , 2n.
Without spokes there would be two 2-regular graphs, each with n vertices and n edges. Pick one and orient the edges.
There are n matching edges (called spokes). Label them (randomly) with n+1, n+2, ... , 2n.
Without spokes there would be two 2-regular graphs, each with n vertices and n edges. Pick one and orient the edges.
20/n. Label the outgoing edge, from {3n+1, ... , 4n}, chosen to “balance” its spoke. Label the vertex from {2n+1, ... ,3n} chosen to balance with the incoming edge. For the other (blue, lower) 2-regular piece, do something similar, except with different sets.
This always works!
This always works!
21/n. Back to MacDougall’s conjecture, that every regular graph of degree at least 2 (with one exception) has a vertex magic total labeling.
In light of Gray’s work, the only regular graphs of odd order left to consider are (most of) the ones without a Hamilton cycle.
In light of Gray’s work, the only regular graphs of odd order left to consider are (most of) the ones without a Hamilton cycle.
22/n. Gray’s method works on any regular graph G of odd order as long as:
G has a 2-regular spanning subgraph with a VMTL such that the biggest labels go on the vertices, called “strong”.
Gray made it a top priority to consider disjoint unions of cycles. sciencedirect.com/science/articl…
G has a 2-regular spanning subgraph with a VMTL such that the biggest labels go on the vertices, called “strong”.
Gray made it a top priority to consider disjoint unions of cycles. sciencedirect.com/science/articl…
23/n. For fun, label any of these 3 graphs. You can do C_9 (if needed, looking through the prequel) it would have h=24. Use the same constant 24 for these.
This is better than a crossword because you may think of ideas that lead to a solution of an open problem, discussed soon..
This is better than a crossword because you may think of ideas that lead to a solution of an open problem, discussed soon..
24/n. Here are answers & if you’re just joining, to take as good examples, used to guess definitions!
These answers won’t spoil your fun of doing these puzzles, as there are *infinitely more* just like them.
You may ask why the tweet # is also the constant. No one knows why ...
These answers won’t spoil your fun of doing these puzzles, as there are *infinitely more* just like them.
You may ask why the tweet # is also the constant. No one knows why ...
25/n. It’s all magic.
Based on results from computer searches up to 17 vertices, a 2-part conjecture was made regarding which 2-regular graphs of odd order have a strong VMTL.
Enter work with (at the time) undergraduate student Jeremy Holden. It’s hard to convey the excitement.
Based on results from computer searches up to 17 vertices, a 2-part conjecture was made regarding which 2-regular graphs of odd order have a strong VMTL.
Enter work with (at the time) undergraduate student Jeremy Holden. It’s hard to convey the excitement.
26/n. We worked for two summers on related problems (REU). The 3 of us showed, via (whole greater than sum of parts) effort:
All of the 2-regular odd order graphs conjectured *not* to have strong VMTLs do have them, except for the three found by computer.
sciencedirect.com/science/articl…
All of the 2-regular odd order graphs conjectured *not* to have strong VMTLs do have them, except for the three found by computer.
sciencedirect.com/science/articl…
27/n. This pic looks technical. I consider it artwork. Each row uses integers -m through m. Each column sums to 0.
Hard part (or else it wouldn’t help construct something thought not to exist) is the required use of 3 given columns.
It’s trivial to verify, but so hard to find!
Hard part (or else it wouldn’t help construct something thought not to exist) is the required use of 3 given columns.
It’s trivial to verify, but so hard to find!
28/n. One thing that’s kinda cool: there’s a tendency to think that everything is linear, so it can’t be that hard. But, if one labels with 1,2,3,... and then (say) doubles everything, one is no longer using *all* integers.
Patterns can disappear almost as a mirage, for large n.
Patterns can disappear almost as a mirage, for large n.
29/n. Time to express gratitude to others from the same time period. Dr. Katy Smith (as an undergraduate) & I spent a summer classifying all magic constants (meaning we found a lot of VMTLs generally, via number theory) for K_n, all odd n. sciencedirect.com/science/articl…
30/n. A few years later, Dr. Addie Armstrong (as an undergraduate) & I spent a summer almost classifying all magic constants (we found a lot of VMTLs generally—probably almost all of them) for K_n,
n=2 (mod 4) (& more!) —The even case is often harder. sciencedirect.com/science/articl…
n=2 (mod 4) (& more!) —The even case is often harder. sciencedirect.com/science/articl…
31/n. There remain many accessible, open problems regarding the set of possible magic constants for regular graphs. Eg. The complete graph K_n, for j a multiple of 4, the complete bipartite K_{n,n}—even the cycle C_n.
Back to MacDougall’s conjecture. The exceptional graph is:
Back to MacDougall’s conjecture. The exceptional graph is:
32/n. (Exception shown in photo.)It’s a small numbers thing, right?
Still, disjoint unions of triangles seem to be an interesting example.
Wallis has a general result (proved using Vizing’s theorem) implying an odd# of copies of an even-regular magic graph is magic
So... 2nC_3?
Still, disjoint unions of triangles seem to be an interesting example.
Wallis has a general result (proved using Vizing’s theorem) implying an odd# of copies of an even-regular magic graph is magic
So... 2nC_3?
33/n. Here’s a VMTL for 14C_3.
(While this is correct, it is a bit of a joke, and to remind anyone/help guess definitions.)
A difficult exercise would be to find a VMTL for 4C_3, or maybe 6C_3. (Hours of fun?)
There are many correct answers with different magic constants.
(While this is correct, it is a bit of a joke, and to remind anyone/help guess definitions.)
A difficult exercise would be to find a VMTL for 4C_3, or maybe 6C_3. (Hours of fun?)
There are many correct answers with different magic constants.
34/n. A strong VMTL for 5C_3 is possible—how Wallis’ result applies to do this will be shown next, tomorrow.
Having just one of the cycles not being a triangle is like throwing a monkey wrench into things.
For 4C_n (the harder one) an arithmetic argument prevents any strong VMTL.
Having just one of the cycles not being a triangle is like throwing a monkey wrench into things.
For 4C_n (the harder one) an arithmetic argument prevents any strong VMTL.
35/n. The labeling of 5C_3 proceeds via the following steps:
-shift a strong VMTL of C_3
-Find (or make) a “Kotzig array” with 3 rows and 5 columns
-color vertices and edges of C_3 with 3 colors
-combine the above
Assuming it’s described sufficiently well, each step is easy.
-shift a strong VMTL of C_3
-Find (or make) a “Kotzig array” with 3 rows and 5 columns
-color vertices and edges of C_3 with 3 colors
-combine the above
Assuming it’s described sufficiently well, each step is easy.
36/n. Shifting here just means subtract 1 from each label. So, the smallest label will be 0 instead of 1. This means it’s not a VMTL (which by definition has smallest label 1).
However, the weight of every vertex is still the same. It’s still magic, since C_3 is a regular graph.
However, the weight of every vertex is still the same. It’s still magic, since C_3 is a regular graph.
37/n. The 3x5 Kotzig array needs 3 rows and 5 columns. Each column has the same sum of elements. Each row has a permutation of 0,1,2,3,4.
Any such array will do. Find one as exercise, or see (in picture) that we’ve found one before, in disguise, when we found a VMTL for C_5:
Any such array will do. Find one as exercise, or see (in picture) that we’ve found one before, in disguise, when we found a VMTL for C_5:
38/n. Color the vertices and edges with 3 colors so that each color occurs once at each vertex.
The general case colors a d-regular graph with d+1 colors, and shows it’s possible by Vizing’s theorem. But for a triangle, we need no theory.
Now to put these three pieces together.
The general case colors a d-regular graph with d+1 colors, and shows it’s possible by Vizing’s theorem. But for a triangle, we need no theory.
Now to put these three pieces together.
39/n. We have a labeling of C_3 and want one for 5C_3. To get the labels for a new C_3, multiply the original by 5 and add a “fine tuning” bit.
The fine tuning is determined by the color and the array.
Picture first, explanation later.
The tweet # is *again* the magic constant.
The fine tuning is determined by the color and the array.
Picture first, explanation later.
The tweet # is *again* the magic constant.
40/n. So, the original VMTL, shifted down, provides a quotient and the array provides a remainder. The color determines the row and the component determines the column. It’s quite elegant (Wallis).
Next up, 4 triangles. It’s smaller, so perhaps an easier exercise?
Next up, 4 triangles. It’s smaller, so perhaps an easier exercise?
41/n. If you’re new to this game, there are standard arguments that help.
One can choose to focus only on sets of edge labels and magic constants that “have a chance” (many are ruled out by the little argument in the picture, which shows a feasible choice with h=38 & edge labels)
One can choose to focus only on sets of edge labels and magic constants that “have a chance” (many are ruled out by the little argument in the picture, which shows a feasible choice with h=38 & edge labels)
42/n. A VMTL for the disjoint union of four triangles.
What do you notice about the difference(s) between an edge label and its opposite vertex label?
Why?
Can this be used to help label 6C_3 or 8C_3?
What do you notice about the difference(s) between an edge label and its opposite vertex label?
Why?
Can this be used to help label 6C_3 or 8C_3?
43/n. This paper (free and open access) could be described as “easy to verify”, but I would say, very hard to come up with.
The hardest part is completely classifying all magic constants for sC_3 for infinitely many s.
Much of it is easier, however.
sciencedirect.com/science/articl…
The hardest part is completely classifying all magic constants for sC_3 for infinitely many s.
Much of it is easier, however.
sciencedirect.com/science/articl…
44/n. At the time the work was done, @violistinvt and I had 3 young children, which meant neither of us got much sleep!
45/n. One neat thing is that many people work on edge-magic total labeling, which is much different!
One defines the weight of an edge, rather than a vertex.
For 2-regular graphs, there’s a clear transformation that bijects these to VMTLs.
See the intro:sciencedirect.com/science/articl…
One defines the weight of an edge, rather than a vertex.
For 2-regular graphs, there’s a clear transformation that bijects these to VMTLs.
See the intro:sciencedirect.com/science/articl…
46/n. Working in Vermont, on a problem from the 90’s, then realizing it was an unsolved problem from the 70’s, based on a similar, but different idea, with different notation and characters? Totally felt like this: images.app.goo.gl/hqeF7wbKkznx94…
47/n. In 1970, Kotzig and Rosa asked (using different language): which 2-regular graphs have edge-magic total labelings? (They labeled all cycles).
This question has not been answered yet.
Back to vertex-magic total labeling.
Next up: odd complete graphs—all magic constants.
This question has not been answered yet.
Back to vertex-magic total labeling.
Next up: odd complete graphs—all magic constants.
48/n. An edge label counts towards the weights of *two* vertices. Thus, small vertex labels yields a big magic constant. Here are 2 VMTLs for K_5, each with constant h=45, the biggest possible.
One of these will be adjusted to make a new VMTL with h=44.
This is cool (Smith).
One of these will be adjusted to make a new VMTL with h=44.
This is cool (Smith).
49/n. Subtracting 1 from each vertex label can’t make the magic constant go down; also, what happens to the vertex labeled 1?
But let’s try it anyway...
After an adjustment, it works!
Also, after reflection, this seems far too lucky to generalize, except that it does! #math
But let’s try it anyway...
After an adjustment, it works!
Also, after reflection, this seems far too lucky to generalize, except that it does! #math
51/n. Subtract 2 from each vertex label, or at least use a mod 5 version of that. This time make 2 adjustments!
The idea for getting any possible magic constant, for general odd n, is to have a way of making lots of VMTLs for h a multiple of n. Then, one of them can be adjusted.
The idea for getting any possible magic constant, for general odd n, is to have a way of making lots of VMTLs for h a multiple of n. Then, one of them can be adjusted.
52/n. Examples for finding these plentiful labelings; in the pic, n=5:
Edge (v_i,v_j) labeled with something
=i+j mod n.
(So v_i labeled with something=i+i mod n).
This means all incongruent summands at each vertex.
So, not much actual adding of numbers is ever required here!
Edge (v_i,v_j) labeled with something
=i+j mod n.
(So v_i labeled with something=i+i mod n).
This means all incongruent summands at each vertex.
So, not much actual adding of numbers is ever required here!
53/n. I ❤️ that no addition of large numbers ever needs to happen & it’s elegant.
Taking the previous 5 tweets as hints, one could work through and see most ideas of paper, & magically label K_n with any possible constant for any odd n.
Reading works too:
sciencedirect.com/science/articl…
Taking the previous 5 tweets as hints, one could work through and see most ideas of paper, & magically label K_n with any possible constant for any odd n.
Reading works too:
sciencedirect.com/science/articl…
54/n.Thinking with a probabilistic attitude for a minute, there would be M! random labelings (using 1,2,3,...,M) of a graph with
M=# vertices + # edges.
If M>30, surely some of these would be vertex-magic.
Indeed, when a large enough graph has VMTLs, it has piles of them.
M=# vertices + # edges.
If M>30, surely some of these would be vertex-magic.
Indeed, when a large enough graph has VMTLs, it has piles of them.
55/n. As a result, I view this as artwork.
If there is no structural reason to prevent a family of graphs from being vertex magic, there will probably be many general constructions.
Yes, some team may find existence proofs. I still like the elegant constructions though.
If there is no structural reason to prevent a family of graphs from being vertex magic, there will probably be many general constructions.
Yes, some team may find existence proofs. I still like the elegant constructions though.
56/n. Here’s an example of a construction I really like, by José Gómez. It’s a VMTL of K_{4n} that uses the smallest labels on vertices. (There is no such labeling for K_4, so, n>1.)
The smallest example, K_8, has 36 objects to label.
sciencedirect.com/science/articl…
The smallest example, K_8, has 36 objects to label.
sciencedirect.com/science/articl…
57/n. Finding an example of a VMTL this big by computer, by a purely straightforward calculation would take too long, and perhaps if one could find one, there would be many to make sense of. So, an idea needs to come first.
Gómez takes other labelings and glues them together :)
Gómez takes other labelings and glues them together :)
58/n. The more general question, of which magic constants are possible for VMTLs for K_{4n}, n>1, is still not known.
There might be something
*really nice* there.
As far as I know, no one is working on it.
(I don’t know much, however).
:)
There might be something
*really nice* there.
As far as I know, no one is working on it.
(I don’t know much, however).
:)
59/n. For most infinite families of regular graphs, the determination of the range (spectrum) of possible magic constants is unknown.
My guess is that many of these questions are hard enough to be interesting yet still doable; eg-K_{n,n}, C_n?
Back to MacDougall’s conjecture...
My guess is that many of these questions are hard enough to be interesting yet still doable; eg-K_{n,n}, C_n?
Back to MacDougall’s conjecture...
60/n. Every regular graph of degree>=2 is magic, save 2C_3.
What’s wrong with degree 1?
This is an easy exercise, which I’ll touch on in this pic:
What’s wrong with degree 1?
This is an easy exercise, which I’ll touch on in this pic:
61/n. A couple of comments about this.
First, this is pretty trivial. In fact, if this were a colloquium talk, this should be the 2nd slide, just to help reinforce definitions.
(In my defense, >=1 person is looking at this without having looked at the previous..“like” if true ;)
First, this is pretty trivial. In fact, if this were a colloquium talk, this should be the 2nd slide, just to help reinforce definitions.
(In my defense, >=1 person is looking at this without having looked at the previous..“like” if true ;)
62/n. BTW my friends on twitter are mostly teachers, and all empathetic, thoughtful supportive and very kind people. Thank you.
The other comment is that a more general fact could have been stated with essentially the same proof:
Any graph with a component of K_2 is not magic.
The other comment is that a more general fact could have been stated with essentially the same proof:
Any graph with a component of K_2 is not magic.
63/n. As for MacDougall’s conjecture, (regular of degree>=2, order at least 7 are all vertex-magic), I’m so sure it’s true I would bet money on it, but, unfortunately I’m not sure enough to have a proof.
64/n (I think n=67).
Let’s say MacDougall’s conjecture is true. Intuitively, it suggests that, beyond the degree sequence, the structure of the graph is not playing a role in deciding whether or not it’s magic.
Well, that’s too much. The degree sequence can’t determine this. Eg:
Let’s say MacDougall’s conjecture is true. Intuitively, it suggests that, beyond the degree sequence, the structure of the graph is not playing a role in deciding whether or not it’s magic.
Well, that’s too much. The degree sequence can’t determine this. Eg:
65/n, n=67?
For example, we can make a magic graph with two vertices of degree 1. Take any 2-regular magic graph with “1” on an edge, delete the edge, subtract 1 from all else.
(Bonus: correcting a typo from tweet 24).
This is silly though. We’re working on something better:)
For example, we can make a magic graph with two vertices of degree 1. Take any 2-regular magic graph with “1” on an edge, delete the edge, subtract 1 from all else.
(Bonus: correcting a typo from tweet 24).
This is silly though. We’re working on something better:)
66/67. One last exercise, (VMTL posted tomorrow).
Find a strong VMTL for 4C_3 union C_5.
The point of this Q is to highlight how hard it is to use inductive arguments—Could one use the previous strong VMTL of C_5 as a useful hint?
Theory always helps, but may not be necessary.
Find a strong VMTL for 4C_3 union C_5.
The point of this Q is to highlight how hard it is to use inductive arguments—Could one use the previous strong VMTL of C_5 as a useful hint?
Theory always helps, but may not be necessary.
