The Foundations of Computer Science

At first pass, it may seem odd for a computer science professor to pen a book about mathematical topics. But a chat with Ömer Eğecioğlu quickly dispels the notion that the fields are that different, at least from his point of view. The two titles, “Lessons in Enumerative Combinatorics” (2021) and “Lectures in Algebraic Combinatorics” (2020) offer an insightful introduction to the branch of mathematics that gives rise to theoretical computer science.

Eğecioğlu co-authored the works with his own Ph.D. advisor, Adriano Garsia, emeritus professor of mathematics at UC San Diego. He put together most of “Lessons” from his own teaching materials, while “Lectures” traces its origins to over six decades of Garsia’s research and unique perspective. “I was more of a collaborator on the ‘Lectures’ book,” Eğecioğlu said.

A combinatorial structure is a visual representation of some mathematical construct which often reveals aspects not readily apparent in the original formulation. The methods for counting these structures form the discipline known as enumerative combinatorics.

Among its many other applications, combinatorics opens up the basic theory of computability itself. The mathematics of counting, combinations and ordering eventually leads to symbolic representations, algorithmic thinking and finally, the Turing machine model. Much like Einstein’s light clock or Carnot’s heat engine, the Turing machine is a thought experiment that demonstrates a fundamental concept, and perhaps a fundamental limitation. It is a theoretical model that underpins the very definitions of computation and computability.

In addition to musing on topics in enumerative combinatorics, “Lessons” lays out a mathematical framework that serves as the foundation of modern computer science. It spans nine chapters, which can be approached from either a mathematical or a computer science perspective. Opportunities abound to wander further into various topics in advanced combinatorics or computer sciences along the way. In fact, Eğecioğlu hopes professors will use the content in the book as jumping off points to introduce and explore different topics in CS as they meander through the material.

Eğecioğlu set out to provide an engaging overview for those beginning to explore this subject. “We picked a number of topics with beautiful theories behind them and tried to present them to the uninitiated,” he said. “Once you know these topics and the machinery behind them, there are a thousand places you can go.”

A graphical device that establishes a correspondence between two different "statistics" on permutations.

ÖMER EĞECIOĞLU

For instance, Eğecioğlu approaches the puzzle of placing rooks on a partial chessboard so that they are non-capturing (i.e., not in the same row or column). This may seem like a pointless exercise, but it actually provides an introduction to flow problems in operations research, a rich subfield in its own right. Assigning applicants to different jobs is very similar to this rook placement problem, he explained.

“Lessons in Enumerative Combinatorics” is a bit like a map of a country, with the many subfields of CS standing in for cities and landmarks that students and teachers can explore. Rather than provide details on each of these destinations, the book shows how the “cities” of computer science relate to each other and how they were established amidst the landscape of mathematics.

“It’s not an encyclopedia,” Eğecioğlu said, noting that such a tome already exists — mathematician Richard Stanley’s two-volume title, “Enumerative Combinatorics.” Eğecioğlu has it on his bookshelf for reference. “Prof. Stanley was kind enough to write a wonderful foreword to our book,” he remarked.

The subject of “Lectures in Algebraic Combinatorics” trades some of its enumerative counterpart’s intuitiveness for mathematical power. Algebraic combinatorics might be likened to a geological assay of a region: useful and information dense, but also technical and abstract. Enumerative combinatorics is akin to a basic street map: simpler but more clear-cut. It won’t tell you how the mountains surrounding the city formed, but it will tell you how to get to the grocery store.

Eğecioğlu hopes that the two books make combinatorics accessible to people just beginning to learn about the subject, whether they’re actually pursuing an advanced degree or simply interested in the topic. And he hopes that these books can help students see the connections between topics in computer science and mathematics that they may otherwise have overlooked.

“It’s like the FedEx logo,” he said, “once you see it you cannot unsee it. Once somebody says, ‘look at that. There is an arrow there.’ That’s it, you’ll never forget it.”

This is the sense of surprise and awe that he hopes the books convey: new perspectives that enrich student’s lives as they come to see things in the world that they simply didn’t know to look for. According to Eğecioğlu, “Lectures” will have achieved its purpose if it is able to impart the sense of excitement and wonder that he himself felt upon first encountering these subjects.