Graph theory research, investigating the properties of figures

At Keio University, the Ota Group in the Department of Mathematics is doing research on combinatorics, which concerns the structures of finite sets. In this field, the Ota Group focuses on graph theory, which investigates the properties of figures consisting of vertices linked by a number of edges.
Graphs are closely related to many aspects of daily life. Familiar examples of things that can be described as graphs include railway maps, electric circuits, and the link structure of the Word Wide Web. In such ways, graph theory has many applications. But many problems in graph theory originated in puzzles. A famous example is the Four Color Theorem. The theorem says that "on any planar map, just four colors are enough for any two adjacent areas to have different colors." This problem was tackled by many mathematicians from the late 19th Century onward. In 1879, a mistaken proof was presented by Kempe. For a century after that, no-one was able to prove the Four Color Theorem. But in 1976, Appel and Haken succeeded in proving it using a computer. Until then, it was thought that proof in mathematics had to be achieved through papers that built up the logic involved. So the proof of the Four Color Theorem using a computer attracted considerable attention.
Other problems in graph theory include the Eulerian trail problem, which is to find a trail passing through every edge exactly once; the Hamiltonian cycle problem, which investigates whether there exists a path that passes through every vertex of a graph exactly once; and the matching problem, where the goal is to create as many vertex pairs linked by edges as possible.
Q. "Graph theory includes the Hamiltonian cycle problem, coloring problems, and ultimately, the problem of finding algorithms for paths and coloring schemes. So there are very deep relationships between theory and algorithm in this field, and then there's the theory of how much computation is required to obtain a final solution. So even if a problem has been solved, finding the simplest way to solve it is still a subject for research. There's also the question of finding a good algorithm, or an elegant theorem; in mathematics, one of our goals is to find elegant theorems. I think what's interesting about graph theory is, it involves pursuing both those aspects."
The problem of determining whether a given graph has a Hamiltonian cycle is algorithmically very hard, and the necessary and sufficient conditions are still not known theoretically. Even now, research on Hamiltonian cycles and related structural problems is very vigorous.
As one project with a view to the future of combinational logic, the Ota Group holds an annual symposium for junior researchers. This year, too, many researchers from Japan and overseas gathered at Keio University to share results and opinions, and listen to invited speakers.
Q. "I think this year's workshop is our eighth. Most of the people involved are in graduate school, or they've just got their degree. Both the people who attend this event and those who organize it are such young researchers; that was the idea when we thought of holding a graph theory workshop eight years ago.
People who were doing their doctorate back then are now post-docs or professors, and they continue to organize this event each year. This year, too, it's a three-day symposium. One feature is, we invite several people to give long talks on various topics of interest to graduate students."
Q. "I think that this conference is an excellent opportunity to talk about your own research.
Of course, it is also an excellent chance to listen to other people's research, and find out about fields and theorems that you didn't know about.
So I think it is also a good chance to improve and expand your knowledge."
Q. "What's different about this workshop is that some of the sessions are in lecture format. I think it's great, because it provides an introduction to advanced research, which is something I don't often hear about. This symposium gives me a chance to meet people I wouldn't usually meet. This year, especially, there are lots of people from quite different fields taking part."
Graph theory has a broad range of applications, including topics in engineering and social science, such as the structure of computer data and algorithms. The Ota Group will continue doing further research to investigate graph structures.