IT'S A PUZZLE

by Marilyn Davis, ed.

Have you heard the one about the traveling salesman?

As any mathematician can tell you, it's no joke. It goes like this: Given x number of cities that a salesman must visit, what is the shortest circuit he can make?

If just a few cities are involved, this problem is a snap. But with lots of cities in the mix, it becomes a real snarl.

The traveling salesman problem belongs to a branch of mathematics, called combinatorics, that deals with arrangements of finite sets. A set may be composed of numbers or of other objects--cities, people, you name it. What's of interest to mathematicians is the relationship between those things (what they have in common) and the properties of the set itself, regardless of the identity of the objects (such as how many members it has and how many ways they can be combined).

Combinatorial problems crop up all the time in daily life. Take scheduling: Anyone who's ever booked a seat on a commercial flight or played intercollegiate sports has benefited from the solution to a combinatorial headache. But science, engineering, business, and the military rely on combinatorics too.

The Rubik's Cube-like puzzles of combinatorics are math professor Walter Wallis's bread and butter. Wallis, an internationally known expert in this field, has written numerous books on the subject.

One of Wallis's specialties is combinatorial computing. As he explains, combinatorics can help you determine the complexity of a computing problem--for example, whether it will require minutes, months, or years of processing time to arrive at a solution.

"What happens if you make a problem twice as big?" Wallis says. "It may actually take eight times as long to solve. It may take billions of times as long to solve." Combinatorics can help you figure out what kind of ballpark you're in--a playable one, or one that's out of this world.

That's of keen concern not just to scientists, but to cryptographers, who use computers to break codes.

"If you double the complexity of your code and it takes eight times as long for [your enemy] to solve it, all they've got to do is get a better computer," Wallis says.

"But if [doubling it] takes a billion times as long to solve it, then you'd feel safe. This idea of complexity comes up in issues like how secure your PIN number is."

One of Wallis's current projects is funded by Australia's Defence Science and Technology Organisation, which works closely with U.S. and English defense agencies. (An Australian citizen, Wallis earned his Ph.D. from the University of Sydney but has taught at SIUC since 1985.)

"This research involves intelligent networks, such as the Internet, where the network doesn't just form naturally but forms because there's intelligent input," Wallis says. "We're looking at various properties that would enable better network management. One of the big problems, of course, is bandwidth. You can only send so many messages from one server to another."

Phone companies sell off excess capacity to smaller companies, he says, but during high usage often must buy it back--at much higher prices.

"If you could predict when you're going to have a bandwidth shortage, that would be real nice. Or if you could look at this network and say, 'That looks like someone's starting to hack into our system,' that would be real nice for defense people, or for banks.

"We're looking at the underlying graph properties that seem to indicate interesting patterns of change in networks."

What Wallis means by "graph" has nothing to do with bar graphs. Combinatorial graphs, called linear graphs, look like networks, or webs. They're collections of things that are connected.

Linear graphs are made up of points (called "vertices") joined by lines (called "edges"). Each vertex, like the cities on a map, is connected to at least one other, but may be connected to several.

Graph modeling, or graph theory, is a valuable tool for solving problems in all sorts of disciplines. Its strength, says Wallis, is that it ignores extraneous information and zeroes in on a problem's underlying structure.

Epidemiologists can use linear graphs to help understand the spread of a disease like SARS. Engineers use them in designing integrated circuits for computer chips. And Wallis, as part of a team of mathematicians, engineers, experimental psychologists, and computer scientists, is using them in this security-related defense research.

"It's interesting--we started with pure mathematics, and we're ending up publishing stuff in applied engineering journals," he says with a grin.

"The network analysis we're doing also can apply to other social networks such as organizational hierarchies, which have similar properties."

Another area of combinatorics that Wallis is working on--this one outside of graph theory--derives from statistics. Given a certain set of numbers, can you construct an array that meets certain rules?

Here's an example: With a set of 35 numbers, using each number three times, create a table with 7 rows and 15 columns. Any two columns must have one number in common, any two rows must have five numbers in common, and any row/column pair must have three numbers in common.

Wallis and a group of colleagues solved that particular problem in 2001--almost four decades after it was first posed. Such row-and-column designs may sound migraine-inducing, but they have important uses in designing complex experiments.

Finally, Wallis is working with graph labeling problems. Labeling involves assigning numbers to a graph's edges, vertices, or both, to see if a graph has certain properties.

For instance, the numbers assigned to each connected pair of vertices might be required to differ by a set amount. That can be done with some graphs but not others. Or each segment of three vertices and two edges might have to add up to the same number.

The latter, called "edge magic property," resembles the "magic squares" that you may remember from childhood puzzles. In a magic square, each row of numbers--horizontal, vertical, and diagonal--adds up to the same sum. Mathematicians are interested in determining which graphs can be labeled so as to have "magic" or other interesting properties.

Many of these properties turn out to be useful. Graph labeling, as it happens, has real-world applications in signal processing, radar, and allocation of radio frequencies.

Still, it is the puzzle aspect of this research that Wallis appreciates the most--tackling and solving these thorny theoretical problems.

"If it wasn't fun," he says, "we [mathematicians] wouldn't be doing it."

Fall 2003 Contents | Perspectives Home | SIUC Home