Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Conjectures and Open Problems

This book is the second in a two-volume series on conjectures and open problems in graph theory. The primary motivation, theme and vision of the series was expressed in the Introduction to Volume I, a slightly revised version of which we reproduce here.

The series has its roots in the idea that conjectures are central to mathematics, and that it is useful to periodically identify and survey conjectures in the various branches of mathematics. Typically, the end results of mathematics research are theorems, the most important and famous of which show up in textbooks, which in turn are taught to students. This often gives students the impression that theorems are the most important things in mathematics. The popular press reinforces this idea; when mathematics is in the newspapers it is most often to report a proof of some well-known, unsolved conjecture or problem.

However, as every research mathematician knows, progress in mathematics involves much more than proving theorems, and its practice is much richer. Mathematics research involves not only proving theorems, but also raising questions, formulating open problems, and stating the conjectures, the solutions to which become the new theorems. Mathematics research also involves the formation of new concepts and methods, the production of counterexamples to conjectures, the simplification and synthesis of different areas of mathematics, and the development of analogies across different areas of mathematics.

The three editors of this volume happen to be graph theorists, or more generally discrete mathematicians, who explain the major focus of the following chapters. In this collection of papers, the contributing authors present and discuss, often in a story-telling style, some of the most well-known conjectures in the field of graph theory and combinatorics.

Related to conjectures are open problems. Conjectures are either true or false. But what counts as the resolution of a problem is often less clear-cut. Nevertheless, a conjecture clearly specifies a problem—and many problems can be naturally formulated as conjectures. For example, it is a famous unsolved problem to determine whether or not the class P of decision problems is equal to its superclass NP. The famous P=NP problem is one of the seven Millennium Problems identified by the Clay Mathematics Institute, whose resolution carries a $1 million dollar prize (http://www.claymath.org/millennium-problems/rules-millennium-prizes). For any problem like this, having a yes or no outcome, the associated conjectures are either that the problem can be resolved in the positive or that it cannot be. Many or most mathematicians, for instance, conjecture that P≠ NP. But a few, including Bela Bollabás, conjecture that P=NP.

While most mathematicians are most likely to be known for their theorems, some are known for their conjectures. Fermat and Poincaré, while famous for their theorems, are also known for their conjectures. Graph theorists know the name of Francis Guthrie only for his conjecture that planar maps can be colored with four colors [10].

The world-famous mathematician Paul Erdös is an exceptional example. While he is known for, among other things, his development of Ramsey theory, the probabilistic method, and contributions to the elementary proof of the prime number theorem, he is perhaps equally famous for his conjectures and problems. He travelled with these, talked about them, worked on them with hundreds of collaborators, and even offered monetary prizes for the solutions of many of them. Some of his graph theory conjectures are collected in [3]. His conjectures and prizes have inspired considerable research and numerous research papers, and still more than 20 years after his death in 1996 his conjectures continue to have considerable influence.

Not all conjectures are of equal importance or significance, and not all will have the same influence on mathematics research. The resolution of some conjectures will impact textbooks and even the history of mathematics. The resolution of others will soon be forgotten. What makes a conjecture significant or important? A few mathematicians have recorded their thoughts on this question.

The famous British mathematician, G.H. Hardy, the early twentieth century analyst and number theorist, discussed this question in his 1940 essay, A Mathematician’s Apology [8], which is a biographical defense of mathematics as he saw and practiced it. Hardy is often remembered for discounting the practicality or utility of mathematics.

Laszlo Lovász has discussed the question of what makes a good conjecture [9]. He says that “it is easy to agree that” the resolution of a good conjecture “should advance our knowledge significantly.” Nevertheless, Lovász wants to make room for some of the conjectures of Erdös that don’t obviously satisfy this criteria, but are “conjectures so surprising, so utterly inaccessible by current methods, that their resolution must bring something new—we just don’t know where.”

Lovász also discusses experimental mathematics as a source of conjectures, a specific example of which being Fajtlowicz’s Graffiti [4], a computer program which makes conjectures, many of which are in graph theory. It is easy to write a program to produce syntactically correct mathematical statements. The difficulty in writing a mathematical conjecture-making program is exactly how to limit the program to making interesting or significant statements. When Fajtlowicz began writing his program he would ask mathematicians what constituted a good conjecture. John Conway told him that a good conjecture should be “outrageous.” Erdös, in effect, refused to answer, telling Fajtlowicz, “Let’s leave it to Radymanthus.”

We won’t here give a definitive answer to the question: what makes a good conjecture? Fame is neither a necessary nor a sufficient condition for a conjecture to be considered good. Sociology plays some role in fame. The nonexistence of odd perfect numbers is probably more famous due to its age, dating back to Euclid and later to Descartes, than its importance [11]. But many conjectures of famous mathematicians are worked on because of their intrinsic importance to mathematics. We certainly expect there to exist little known but significant conjectures. The history of mathematics contains numerous examples of important research which was not recognized in its own time. The work of Galois, for instance, is a well-known example.

Our thought is that there may not be any better way of identifying good conjectures than to ask the experts, people who have tilled the mathematical soil for some time, and know best which seeds will sprout.

There are also internal reasons for the importance of a conjecture, strictly mathematical reasons related to the furtherance of mathematical research, and the question, how would resolution of a given conjecture advance mathematics?

Of course the goal of mathematical research, and what research mathematicians are paid to do, is to advance mathematics. Mathematics is seen by the public as a tool for the sciences—they would have much less interest in paying mathematicians to be artists than they would as researchers who may play a role in improving their lives.

But how can a conjecture play a role in advancing mathematics? In particular it may seem that we have a new question to address: how does mathematics advance?

A conjecture can be said to advance mathematics if the truth of the conjecture yields new knowledge about a question or object of existing mathematical interest.

Furthermore, the advancement of mathematics requires not just new concepts, conjectures, counterexamples, and proofs (uniquely mathematical products) but also effective communication. Lovász writes:

Conjecture-making is one of the central activities in mathematics. The creation and dissemination of open problems is crucial to the growth and development of a field. Lovász, in his 1998 reflection “One Mathematics”[9], writes: “In a small community, everybody knows what the main problems are. But in a community of 100, 000 people, problems have to be identified and stated in a precise way. Poorly stated problems lead to boring, irrelevant results. This elevates the formulation of conjectures to the rank of research results.” Conjecturing became an art in the hands of the late Paul Erdös, who formulated more conjectures than perhaps all mathematicians before him put together. He considered his conjectures as part of his mathematical œuvre as much as his theorems. One of my most prized memories is the following comment from him: “I never envied a theorem from anybody; but I envy you for this conjecture.”

2 About This Book

Earlier, we mentioned that this series of monographs grew out of the idea that conjectures are central to mathematics and that it is useful to identify and survey conjectures in the various branches of mathematics. This idea is not novel and this two-volume series has many predecessors, even in our own field of graph theory. Erdös, of course, regularly gave talks on his favorite problems in graph theory and the other fields of mathematics in which he worked. Bondy and Murty’s classic graph theory text [1] includes a listing of conjectures, a recent updated version of which was compiled in 2014 by Bondy [2]. The second edition of the Handbook of Graph Theory contains some conjectures and open problems as well. [7].

The conference Quo Vadis in Anchorage, Alaska in 1990, was an inspiration as well, when John Gimbel assembled many leading graph theorists to talk about the future of graph theory [6].

A nice collection of 50 graph theory conjectures and open problems can also be found online in the “Open Garden Problem” (http://www.openproblemgarden.org/ category/graph_theory).

The aim of the first volume in this series was to contribute to the identification and distribution of many outstanding problems in graph theory. Two of the editors, Gera and Larson, of Volume 1 started this by co-organizing three special sessions at AMS meetings on the topic “My Favorite Graph Theory Conjectures.” These sessions were held at the winter AMS/MAA Joint Meeting in Boston in January 2012, the SIAM Conference on Discrete Math in Halifax in June 2012, and the winter AMS/MAA Joint Meeting in Baltimore in January 2014. At these three sessions, many of the most well-known graph theorists spoke. All sessions were highly popular and extremely well attended. At the Boston session, there was standing room only for a series of 12 talks, and at the Halifax session, people were sitting on the steps and there were rows of people at the door listening in. The speakers and the titles of their talks at these sessions can be found at http://faculty.nps.edu/rgera/conjectures.html.

The success of these sessions prompted this series of monographs. The editors of Volume 1 [5] of this series, published in 2016, asked the contributors to write informally, to share anecdotes, to pull back the curtain a little on the process of conducting mathematical research, in order to give students some insights into mathematical practice. We believe that Volume 1 is a valuable resource for researchers that provides conjectures and open problems, sheds light on the research process, and keeps alive the rich history of graph theory.

The editors of this second volume asked the contributors to continue with the same style. Thus, all the chapters of this volume, with the exception of the final one, are written in a much less formal style, than that which is required in archival journal publications. Furthermore, they include more interesting personal anecdotes of the type that contributed to the success of Volume 1. The final chapter of this volume deviates from the story-telling style adopted in the other chapters. Instead, it is an annotated glossary of some 300 graph theory parameters, which contains some 70 conjectures and more than 30 suggested new parameters and open problems, and more than 600 references. The listing of parameters is annotated to provide a clearer understanding of the parameters beyond their mere definition. Written with an eye toward the discovery of new ideas in graph theory, this glossary fits in its own way within the favorite conjectures and open problems theme of this series.