Combinatorics, past and present: An interview with Pierre Duchet

Pierre Duchet is one of France’s few specialists in combinatorics. He has had a front-row seat to the major developments in discrete mathematics, from Erdös’s discoveries to prime numbers in arithmetic progression, by way of the proofs of the four-color theorem and Berge’s conjecture (Claude Berge was his doctoral supervisor).

How far back can the beginnings of combinatorics be traced? Combinatorics, in the modern sense, is the systematic study of structures. Its beginnings can be traced to the 1930s. We can even pinpoint its geographical origins: Hungary is the country where combinatorics has gained the greatest recognition and developed most extensively! Take Erdös, Turán, Halmos, Szemerédi, Bollobás, Lovász, Frankl… All these famous mathematicians were born in Hungary. It would almost be harder to name specialists in combinatorics who were not Hungarian! Today, besides Hungary, there are North American schools of combinatorics, as well as schools in the former USSR, several Eastern European countries and, to a lesser extent, France; more recently, they have also emerged in Japan over the past thirty years and in China over the past decade. That said, combinatorics could be traced back to the brilliant Euler and his Königsberg bridges problem [see FOCUS]. This is structural combinatorics—in other words, a "soft way of talking about space." Or it could be traced back to Laplace and his atomistic view of space and the universe. Or again to Leibniz, who, in order to "predict the future," was led to "divide up" surfaces [an allusion to integral calculus]. Poincaré and his Analysis situs should also be mentioned! But we must admit that combinatorics truly took off only with the explosion of operations research (OR) and the emergence of graphs [see FOCUS] as mathematical structures in their own right. An archetypal OR example is the traveling salesman problem: imagine a sales representative driving around a country and having to visit each of its N cities to meet clients. The route must minimize the total distance traveled, because fuel is expensive. Of the N! possible routes, which is optimal? And what if all distances are equal to 1 and the traveler must pass through each city exactly once—the Hamiltonian cycle problem? These are the kinds of problems posed by operations research. For small values of N, we know the solution, but the best we can soon offer the traveling salesman is a set of heuristics. This problem is extremely difficult. [It is said to be NP-hard.] And today we are returning to problems posed in the 18^th century. Combinatorics did not appear by chance; it belongs to a historical continuum.

NP-hard problems ----------------

**The 18^th century, Poincaré in the early 20^th century, the 1930s and graph theory, the birth of OR during the Second World War… What happened next?**

OR produced a great many discrete optimization problems, such as graph coloring. The aim of these problems is to find an algorithm. An important variant of the graph-coloring problem is the 5-flow problem, formulated by William Thomas Tutte in 1954 [see FOCUS].

OR, graph theory, the study of algorithms, and the study of set systems (set systems), also known as hypergraphs (hypergraphs), remain major sources of problems in combinatorics: packing problems (finding the densest possible packings of objects within a given space), covering problems (does one combinatorial structure cover another?), the four-color conjecture (now a theorem), Hadwiger’s conjecture… Graph theory was the foundation, and these major problems drove research throughout the field. But that is no longer really the case today.

####

Today, major problems are no longer the main drivers of research: considerable progress has been made on many of them, while others have been solved, such as Berge’s conjecture, now the strong perfect graph theorem, and the four-color theorem. The 1970s saw the development of complexity theory to deal with decision problems—those that can be answered yes or no. First come the “easy” problems: those solvable in polynomial time. They form what is known as the class P (for “polynomial”). For these problems, we know how to find an algorithm whose running time is bounded above by a polynomial in the input size. Next come the “difficult, or even downright impossible” problems, which form the class known as NP. These are the problems for which we know a “fast” way to verify a solution. Finally, there are problems not known to belong to P, NP, or any other class, as well as problems that by their very nature fall outside complexity theory! Every researcher is convinced that NP is not contained in P. But no one can prove it. The traveling salesman problem is NP-hard, meaning that it is at least as hard as an NP-complete problem. [A problem is NP-complete if solving it in polynomial time would allow every NP problem to be solved in polynomial time.] In practice, an NP-hard problem is intractable. Over the years, it became clear that many of the major problems driving research in combinatorics were NP-hard. One example is the total chromatic number problem, which is fairly easy to explain: it is conjectured that the total chromatic number of a graph G is less than D(G) + 2, where D(G) is the maximum degree of the vertices of G. Let’s see what this means. To color a graph G with k colors—a k-coloring of G—is to assign one of the k colors to every vertex and every edge of G so that any two adjacent objects, whether edge–vertex, vertex–vertex, or edge–edge, always have different colors. The total chromatic number of G is the smallest integer k for which a k-coloring of G exists. Determining this number is an NP-hard problem. But it can sometimes be characterized or bounded. Hadwiger’s conjecture is another unsolved coloring problem. Suppose the chromatic number of the undirected graph G is greater than m—meaning that its vertices cannot be colored with fewer than m colors without two adjacent vertices receiving the same color. Then G has m disjoint connected subgraphs, each joined to every other by at least one edge.

What mathematical tools have made it possible to solve, or at least make headway on, problems in discrete mathematics? The combinatorialist’s toolbox contains only a very small number of fundamental results. The first, and undoubtedly the most important, is the marriage theorem. [Let there be a set of boys, a set of girls, and a map assigning to each boy the girls he likes. If, for every subset of boys, the number of girls liked by at least one of them is greater than the number of boys in that subset, then each boy can be matched with a different girl he likes.] Attempts to generalize this problem led to a powerful theory of matchings, in which matroid theory plays an important role.

Berge (1926–2002) on his right.**

There are also general methods. For example, Paul Seymour and his team consistently tackle graph-theory problems through the same “decomposition” approach: the aim is to “break apart” a given graph in such a way that the only “unbreakable” graphs have a known structure. When trying to assemble an arbitrary graph from known elementary building blocks, the art lies in finding the “right glue.” I must admit that I never believed this approach would one day solve Berge’s conjecture, and yet it did… Discrete optimization problems are often reformulated as linear programs: the constraints are modeled by a system of linear inequalities in the decision variables, and the problem then becomes one of maximizing—or minimizing—a linear objective function. The fundamental theorem of linear programming [see elsewhere in this issue] can then be applied, with one important difference: the optima of the combinatorial problem must correspond to integer values of the variables, rather than arbitrary rational or real values. When the structures used to model the problem are “well behaved,” it can be proved that the integer optimum coincides with the fractional optimum. Otherwise, there are very few general results for analyzing structures. We work by analogy. Seymour’s team, once again, had the idea of comparing graphs to words on a surface. By generalizing a theorem of Kuratowski—who was Polish!—they developed a theory of graph minors. In some twenty papers spanning more than twenty-five years, they managed to prove the famous Wagner conjecture [according to which, in every infinite family of graphs, one graph is isomorphic to a minor of another]!

When the lottery inspires an unsolved problem ---------------------------------------------

"Structure" seems fundamental to combinatorics. What is a "structure"? We should be wary of the word "structure"! A tree, a graph, a hypergraph, a set system… all these provide modeling tools that a mathematician can manipulate both qualitatively and quantitatively. A bipartite graph [a graph that can be colored using only two colors], by contrast, does provide a modeling tool, but not one that can be manipulated. Structural combinatorics is concerned with everything that can readily be modeled as a set of finite sets—and that covers a vast territory! In fact, we need to develop an intuition for what makes a "good structure," and that requires representational tools. Venn diagrams, or "potato diagrams," are one such tool. Likewise, geometry and topology provide tools for representing space. Other fields that study structures include algebra and algebraic combinatorics. But in algebra, at least one operation is always defined on the structure in question. We do not even have that! We are interested in connectivity between elements—whether they are linked or connected.

What major theories have been developed to study structures? Graph theory raises a great many interesting problems—more than it solves. And what is more, moving from undirected to directed graphs brings a phenomenal leap in complexity! It is a jungle! We have also discussed structural combinatorics. Enumerative combinatorics, which is concerned with counting according to a given method, must also be mentioned. Counting concerns the quantitative aspect of structures: are they numerous or rare? Exactly how many are there, or how many asymptotically? Counting problems abound. Doing combinatorics on numbers, for example, means revealing particular arithmetic structures. Another important field is Ramsey theory, according to which some order can always be found in a structure provided it is "sufficiently large." A typical question in this theory is: "What is the minimum number of elements I need to bring together to be certain that a particular property holds?" In fact, this theory arose from very general extremal problems. A simple example is the lottery problem: what is the minimum number of different tickets you must fill in to be certain of matching, say, four winning numbers? Despite extensive research, this problem remains unsolved! In general, an extremal problem consists in minimizing a function of three parameters, k, n and t. The integer n is the size of the reference set (n = 49 numbers in the lottery example), while k is the number of elements in each subset considered (a lottery ticket always has k = 6 numbers). Finally, t is the minimum number of elements in the subsets that must be covered (for the lottery, the requirement is to guarantee t = 4 winning numbers). That is an extremal problem: minimizing the cardinality of a family T of k-element subsets such that, for every t-element subset E, some set F in the family T is guaranteed to contain E. Apart from a few trivial cases, we do not know how to solve these problems. Continuing our tour of the major fields of combinatorics, we must mention design theory (design theory). This is a theory of regular structures. Here is an example: in a dodecahedron, it studies the arrangement of all the cubes formed from eight of the dodecahedron’s vertices. Regular polyhedra, error-correcting codes and lattices are all designs. One of the major problems in this theory is the classification of projective planes [see FOCUS]. It is a very old problem. More generally, the question is whether t-designs exist. It was recently proved that no projective plane of order 10 exists. But beyond 10, and beyond projective planes, we know very little… Knot theory and braid theory also belong to combinatorics: a knot diagram captures the combinatorics of a curve! How can we recognize whether a knot is trivial? How can we untie a knot known to be trivial? These questions are formidably difficult.

Doing combinatorics without realizing it ----------------------------------------

To hear you tell it, combinatorics seems to be everywhere! What place does it hold within mathematics? Many mathematicians do combinatorics without realizing it. Yet in 2010, discrete mathematics is still not recognized as a field in its own right. Absent from the major international congresses, it is still seen as a tool rather than an object of study—or even dismissed as the preoccupation of computer scientists! That is very unfair: if problems seem a priori easier in the continuous world than in the discrete one, where they are often unassailable, perhaps it is because the continuous is an approximation of reality. I see the real numbers as a convenient modeling device that hides the forest of reality. Discrete mathematics has many applications in molecular chemistry and atomic physics! There is a genuine combinatorial vision of the world. Even so, attracting students to combinatorics remains difficult. Why? Discrete mathematics lacks a well-developed overarching theory. It lacks any real theoretical depth, and its problems are difficult to relate [sic.] to one another. But this is a symptom of youth: the theory is simply waiting to mature. My American colleague Jack Edmonds, for his part, knows how to formulate good optimization problems. *\In the same room, Edmonds is deciphering [Tangente 131, devoted to mathematics in the United States.\]* A “good problem” is one that belongs to both NP and co-NP.

What broad questions are specialists in combinatorics tackling today? Well, any min–max theorem is considered important because it reveals the existence of a structure. One generalization of the marriage problem, for instance, is to seek the maximum number of disjoint sets in a given family of sets. This is the packing problem, or packing problem. The dual optimization problem is to cover all the elements with the fewest possible sets: this is the covering problem, or covering problem. Perfect graphs provide an example of a min–max theorem: the minimum number of colors needed to color a perfect graph—its chromatic number—equals the maximum number of pairwise connected vertices—its largest clique. This property characterizes perfect graphs. Turning to an entirely different register and simpler objects, there are all the problems involving polyominoes, elementary geometric objects made of unit squares joined edge to edge. Join two squares and you get… a domino. Yet we do not know how to count the polyominoes made of n squares, even asymptotically; it is conjectured that their number is less than a constant times 4ⁿ. Here is another problem that epitomizes the hell these little creatures put us through. Let us take an arbitrary polyomino and try to tile it with horizontal bars of length 3—horizontal trominoes—and vertical dominoes, so that the entire polyomino is covered and neither the trominoes nor the dominoes overlap. Deciding whether your polyomino can be tiled in this way is an NP-complete problem! It is appalling… That said, I conjecture that if we restrict ourselves to simply connected polyominoes—that is, those without holes—the problem becomes tractable again…

#### **

Endre Szemeredi (born 1940).**

Finally, number theory teems with open problems, thanks particularly to Erdös: the Erdös–Szemeredi and Erdös–Turan conjectures, and the Erdös discrepancy problem, which is currently the subject of intensive research… But here mathematicians have scored a major success: in 2005, Ben Green and Terence Tao proved that the prime numbers contain arithmetic progressions of arbitrary length. They used tools from additive combinatorics and a new theory now known as ergodic theory. This shows that successes do sometimes occur!