Mapping the way to real-life solutions through COLOR
In 1852, mathematician Francis Guthrie was coloring a map of England when he discovered that only four colors were needed to color any map as long as no two regions with a common boundary shared the same color. Determining why that was became known in the mathematics community as the Four Color Problem.
Cun-Quan Zhang, a professor of mathematics in the Eberly College, has been working in the areas of integer flows and cycle covers, a key component of the map-coloring problem, for more than 25 years.
He has recently been awarded a roughly $128,000 grant from the National Science Foundation to support his research in this area over the next two years.
The map-coloring problem is considered one of the major catalysts of the tremendous development of graph theory in its 275-year history. Graph coloring and its related problems have always been in the main line of graph theory research.
Traffic light patterns, radio station frequency assignments, cell phone channel distributions, and a number of other areas of everyday life all use the same premises and logic as the solution to the map-coloring and network-flow problems, making finding a solution critical.
“In the morning, a lot of people from a certain community go to work. You will find farther out that somewhere, the traffic jams. We call it a bottleneck. In mathematics we try to find out ‘where’s the bottleneck?’ and ‘how can we maximize the traffic with the lowest cost to improve the flow?’” Zhang said. W.T. Tutte, a famous 20th century mathematician, observed that the map-coloring problems could be formulated in terms of the network-flow problem, as well as in terms of its cycle covers. A major conjecture in this theory was three-flow conjecture.
“We are only a small step away from the final solution of the three-flow conjecture,” Zhang said.
This development is 25 years in the making for Zhang, who said he’s driven to find the solution to the second-most famous unsolved problem in mathematics.
“Mathematical research is not only motivated by the beauty of our universe, but also promoted from our daily life,” he said.
Working on structures, patterns, connectivity of networks and graphs, Zhang has published around 100 papers on the topics of mathematical theory and application.
Armed with those theoretical discoveries, he and his colleagues at WVU further developed application projects for pattern recognitions, such as data mining, social network analysis, bioinformatics, and algorithm/software development for operational research.
Their discoveries include terrorist network analysis, FBI crime data analysis, DNA sequence analysis for phylogenetic study, and other medical study.