Of Counting and Colors: Graphs, Combinatorics, and the AI Revolution
Image commercially licensed from Unsplash
Combinatorics is the branch of mathematics that deals with the counting, arrangement, and selection of objects. It is concerned with finding the number of ways that a certain event or combination of events can occur. In contrast to Algebra and Analysis, elementary Combinatorics has few formal prerequisites. I argue that these prerequisites are known intuitively to many young children, albeit under more informal names. In this article, they shall be deemed the “Fundamental Counting Principle,” “Principle of Permutation,” “Principle of Combination,” and “Inclusion-Exclusion Principle.” I briefly sketch how these principles facilitate Neural Networks and Network Topology, which are some of the pillars of Artificial Intelligence – a topic that has dominated the news in recent days.
The first fundamental principle – aptly described by mathematicians as the “Fundamental Counting Principle” – states that if there are n ways to perform one task and m independent ways to perform another task, then there are n x m unique ways to perform both tasks together. By “independent,” we mean that our selection of the first task does not restrict or otherwise influence our selection of the second task. As an example, if there are 8 routes from Ithaca to Utica and 10 independent routes from Utica to Rochester (numbers are fictional and strictly for the purpose of discussion), then there are 80 possible itineraries that begin at Ithaca and end at Rochester. The second principle is called the “Principle of Permutation,” and is a repeated application of the first principle. A permutation is an arrangement of symbols where the order is taken to matter to the inquiry at hand. For instance, if we are listening to a concert that offers 10 songs with a single intermission somewhere in the middle, where we place the intermission matters to the overall itinerary of the program. Two programs with two different intermissions or orders of songs are fundamentally different to the people experiencing the event. Even if we were to hear the same songs but in a different order or with a different intermission, someone who desired to meet us when a particular song was playing would have to be apprised of the change in itinerary.
The third principle is deemed the “Principle of Combination.” Combinations differ from permutations in that a selection of objects or events is made without regard to order. Drawing upon the previous example, two concerts are said to be the same up to combination if and only if they have the same songs and a single intermission but the order of these elements is immaterial to us. There are clearly fewer combinations of songs in a given concert than permutations of the same. After all, if I have 5 distinct songs and play two of them in a row where I have determined that the order matters, there must be 5 x 4 = 20 permutations by the Principle of Permutation. The reason we multiply by 4 instead of 5 again is by the distinctness assumption. Once I play a song, there are only 4 of the 5 original songs in the program that stand to be played. If, however, I am listing combinations only – that is, the order of the songs does not matter to me – have only 10 possibilities to count. The original 20 permutations are split in half because I no longer care which selection is first and which is second. So far, we have not discussed an intuitive problem that arises when children learn to count, and that problem is deemed “double-counting.”
Mathematicians call double-counting “Inclusion and Exclusion”. We may phrase the problem so intuitively and concretely that it seems to require no justification, although we would be misguided to believe that it is self-evident or can be taken on faith. If there are 5 numbered stones included in one pile (numbered 1-5) and 4 stones included in a second pile (numbered 6-9), there are clearly 9 stones in total. Permit us, however, to change the situation a bit. Suppose that the first pile of stones contains stones {1, 2, 3, 4, 5} and the second pile contains {4, 5, 6, 7, 8, 9}. That is, the piles are now taken to be non-distinct but the stones are still assumed to be distinct. How many distinct stones are in the two piles when considered together? If we answered “9,” we would quickly see that this guess is incorrect (there are two stones common to both piles), and we would have to subtract (or “exclude”) the number of stones “in the middle” to avoid double-counting. This approach yields 7 distinct stones: {1, 2, 3, 6, 7, 8, 9}.
Although these concepts are simple to state, they are ubiquitous in Artificial Intelligence and related fields. Some applications of fundamental Combinatorics include Game Theory, Machine Learning, Statistics, Computer Vision, Symbolic Logic, and Graph Theory. Ramsey Theory counts the number of subgraphs of a given graph. If one thinks of graphs in terms of associations, this theory becomes intelligible in AI algorithms like “Nearest Neighbors”. What A and B plausibly share in common is determined by the edges of knowledge graphs that A and B both inhabit. Matching Theory is a common AI principle and arises in Machine Learning as well as the theory of human and animal perception. What does it mean for two groups of objects to “match,” in a given abstract sense? Perhaps we are looking at population age demographics, crime rates, weather patterns, housing prices, or labor statistics. Once we define what “matching” means, we may construct a knowledge graph that represents the connections between and among the relevant categories. Counting the edges and vertices (e.g. points where edges intersect) can clarify quite a bit about the relationships among the variables that basic statistical analysis would miss. In addition to edges and vertices, data visualization relies upon coloring to make associations among data sets. Graph Coloring Theory asks whether it is possible to color in a graph in a certain way – or, if it is already known to be possible, how probable such a coloring should be in the long run. One may consider many applications: coloring zip codes by poverty rates, crime rates, proportion of commuters that encounter substantial traffic, population, voting demographics, or propensity to attend religious services, just to name a few. One may then proceed to color these zip codes according to a bespoke scheme that is determined by whatever research questions are of interest (e.g. zip codes in which a majority of commuters encounter traffic delays only in the winter months). According to publicly-available documentation, data visualization tools like Tableau, Cognos, NoSQL products, Oracle, Google Analytics, Microsoft Analytics, SAP, and countless others rely on such mathematics to make compelling cases for the acceptance or rejection of data-driven claims. Specific algorithms and capabilities are highly monetizable and often remain trade secrets via encryption and code obfuscation. Physical scientists know Graph Coloring under a different name (Chromodynamics), in which particles are assigned colors based upon their spin, mass, or other properties. Spectral analysis of chemical compounds, crystal lattices in molecules, attractive and repulsive forces in magnetic fields, particle trajectories in nuclear reactors, and spectral analysis of the light generated by cosmic radiation all have roots wherein the Combinatorics of color is indispensable.
Machine Learning engineers have yet another take on the same four fundamental combinatorial principles. A Neural Network is a type of machine learning model that is inspired by the structure and function of the human brain. A network consists of interconnected nodes (called neurons, just like the neurons in human and animal brains) which are organized into depths (or layers, just as they are arranged in the nervous systems of living things). As in human brains, each neuron receives stimulus signals, processes them to determine their plausibility, applicability, or propensity for threat, and produces an output signal, which is then passed on to other neurons in the network. Network Topology is the study of such connections, and its application in Machine Learning is behind such prominent trends as the ChatGPT revolution, Amazon rapid delivery, aerial and naval warfare simulations, and the logistics of consumer preference respecting advertisements. Spam filters for mobile devices and electronic communication use Network Topology to identify malicious messages and block or categorize them. Telecommunications satellites use the same theory to optimize mobile and wireless signals. Power companies use Network Topology to determine the locations of outages in the power grid. Without such methods, line workers would have to determine outage locations manually – a daunting task when millions of kilometers of line may be involved. Network Topology simplifies this task by a factor of several thousand.
I hope to continue the discussion of Combinatorics and its applications to networks in future submissions. These are quite possibly multi-trillion dollar industries that have the capability to upend the laws and customs of nation-states and disrupt the delicate ecology of industry the world over. Space in this publication is difficult to obtain and is rightfully rationed in accordance with readers’ interests, and I have nearly exhausted my share for this article. We have only surveyed the hundredth part of combinatorial applications in the vast and burgeoning field of Network Theory. It would be my privilege to continue the discussion if you, the readers, permit me. I endeavor to provide comprehensive resources for further study if you are indeed interested. In selecting the resources for inclusion, I weigh readability highly. However, I do not desire to cut theoretical corners in support of insipid discussions. The selection of works consequently represents a (hopefully) prudent middle-course between rigor and readability.
Respectfully,
Dr. Jonathan Kenigson, FRSA
Sources:
https://medium.com/@jonathanjkenigson/ny-weekly-sources-866a392e879e
