As noted in my bio, I’ve been involved in public service and amateur radio for decades. Fortunately, I happen to live in Ham Radio Central — Cedar Rapids, IA. We have (last I heard) the second-highest number of hams per capita of anyplace in the world, due primarily to the presence of what used to be Collins Radio. As of this year, about 1000 licensees in my county. This means I have a large pool of people who are willing to be involved in public service, which has led to some very solid and well-vetted protocols we’ve applied to various situations.
Linn County’s plans (you can find them here) have long included pre-assigned frequencies for both repeater and simplex operation, two each. If we have a large-scale emergency, everyone knows what frequencies to check first. It’s a simple thing that works remarkably well when the chips are down.
I’d mentioned this to my state-level leader. He felt it would be good to define that for all counties within a district, but we didn’t want neighboring counties to use the same frequencies. I puzzled for a bit on how to make that happen — and then it hit me. I was trying to solve the “four color map problem.”
In graph theory, a map coloring problem asks how one can color all the areas on a map so no two neighboring areas have the same color. Two areas are considered neighbors if they share part of a border. Meeting at a POINT doesn’t count…there has to be a line. The four color map theorem states that it is possible to color any two-dimensional map this way using no more than four colors. This was proven in 1976, and was the first theorem to be proven by computer. (I’ve read that some doubts remain, but it’s not important to the story.) Bear in mind this is true of ANY map, from the simple and familiar
to the complex
I was trying to do something similar, except instead of using colors, I was using frequencies. Same problem, different labels. I found some Python code on the web that solves constraint problems like this generically, then focused on setting it up to get all 99 Iowa counties assigned. This was fairly straightforward, if a bit labor-intensive on the typing. I had to set up a map of the counties with their neighbors (the code lets me do this efficiently), and then I told it to solve the problem using eight frequency pairs. (Note: due to a lesson learned at an event this summer, the pairs include one simplex frequency in the 146.xxx range, and one in 147.xxx.) The result came less than a second later, and it used only five pairs. I also ran it for four pairs, and it worked, but it took a bit longer.
Originally, we wanted things so that no neighboring counties had the same assignments, but I realized it would be good if we added the constraint that no two counties that have a common neighbor have the same assignment. I reasoned that this is equivalent to setting up a new map where your neighbors’ neighbors are also your neighbors….
Yeah, you guessed it. That took longer than expected. In the amount of time it took me to generate the second setup from the first, I could probably have typed it all in by hand. This would have bored me to the point that I gave up on it. And it turns out the constraint solver is not very forgiving of doing stupid things like having a county be its own neighbor. It turns out that the code will work on the three-dimensional maps my modifications apparently created, but that “can be done with four” thing doesn’t apply in three dimensions. Five pairs wouldn’t cut it. The final solution ended up using all 12 available pairs.
[Side note: if you start at the bottom edge of the simplex range on the two meter band plan, and go up in 15 kHz increments, you can fit 12 147 MHz frequencies, and 13 146 MHz frequencies. The latter includes 146.52, which is not to be used for general purposes, so I very conveniently get 12 pairs out of it.]
I’m not done working things out yet, as I know a few of our larger counties have frequencies already that they’d like to keep. I have not figured out how to pre-assign pairs to certain counties as additional constraints, and that may take a while. I’m also going to see if I can get this down to nine pairs, and use the remaining three to assign as district-wide for the six districts. (This will require simplifying the map for the sparsely populated parts of the state.)
All in all, a fun foray into math, and I built some Python chops in the process.