Fact-checked by Grok 2 weeks ago

Combinatorics

Combinatorics is a branch of mathematics concerned with selecting, arranging, constructing, classifying, and counting discrete objects, as well as the underlying theory of enumeration.^[1] It focuses on finite or countable structures, such as sets, graphs, permutations, and sequences, to solve problems involving their combinations and properties.^[2] This field encompasses both theoretical developments in counting techniques and practical methods for analyzing discrete systems.^[3] The origins of combinatorics trace back to ancient civilizations, where early problems in enumeration appeared in Indian, Chinese, and Arabic mathematics, such as calculating permutations for poetic meters or astronomical arrangements.^[4] Modern combinatorics emerged in the 17th century with contributions from Blaise Pascal and Jacob Bernoulli on probability and arrangements, evolving through the 18th century with Euler's work on partitions and the Königsberg bridge problem, which laid foundations for graph theory.^[5] By the 20th century, the field expanded rapidly due to influences from algebra, topology, and computing, with key figures like Paul Erdős advancing extremal problems and asymptotic methods.^[6] Combinatorics includes several interconnected subfields, each addressing distinct aspects of discrete structures. Enumerative combinatorics deals with counting the number of objects satisfying given criteria, often using generating functions and recurrence relations.^[7] Algebraic combinatorics applies algebraic tools, such as representation theory and symmetric functions, to study symmetries and invariants in combinatorial objects.^[8] Extremal combinatorics examines the maximum or minimum sizes of structures avoiding certain substructures, as in Turán's theorem for graphs.^[9] Other areas include combinatorial geometry, focusing on discrete points and lines, and probabilistic combinatorics, which uses probability to prove existence results via the Erdős probabilistic method.^[10] Applications of combinatorics span numerous disciplines, providing essential tools for modeling and optimization. In computer science, it underpins algorithm design, data structures, and complexity analysis, such as in sorting permutations or analyzing network topologies.^[11] In engineering, combinatorial optimization techniques solve problems like scheduling, resource allocation, and circuit design, with methods like integer programming drawing directly from enumerative principles.^[12] The field also informs probability theory, statistical mechanics, and biology, for instance, in counting molecular configurations or phylogenetic trees in evolutionary biology.^[13]

Overview

Definition and Scope

Combinatorics is a branch of mathematics that deals with the enumeration, combination, and arrangement of discrete objects. It focuses on counting the number of ways to select, order, or structure these objects within finite or countable sets.^[2] This field primarily emphasizes discrete rather than continuous structures, though certain subfields incorporate infinitesimal methods from calculus and analysis.^[14]^[15] The scope of combinatorics extends to problems involving the existence, construction, and optimization of configurations in discrete settings. While primarily concerned with finite sets, it also addresses countable infinite sets, such as those in enumerative problems over natural numbers. Key questions include determining whether certain arrangements exist, devising explicit constructions for them, and finding optimal configurations under given constraints.^[16] Combinatorics forms a central component of the broader discipline of discrete mathematics, which includes topics like logic, set theory, and algorithms, but distinguishes itself through its emphasis on quantitative counting and structural analysis. A classic example is the handshake problem: in a room with n people where each pair shakes hands exactly once, the total number of handshakes is \frac{n(n-1)}{2}.^[1]^[17] Combinatorics has applications in probability, for modeling event spaces, and in computer science, for designing efficient algorithms.^[18]^[19]

Importance and Applications

Combinatorics plays a pivotal role in solving real-world problems, particularly through combinatorial optimization techniques that address challenges in logistics and supply chain management. For instance, it enables efficient route planning and resource allocation in transportation networks, minimizing costs and time while handling constraints like vehicle capacity and delivery deadlines. In computing, combinatorial methods underpin algorithm design, such as in scheduling tasks or selecting optimal paths in networks, which are essential for scalable software systems.^[20]^[21]^[22] The field also has profound interdisciplinary impact, serving as a foundational pillar for probability theory by providing tools to count and enumerate possible outcomes in random processes. Combinatorial structures, like permutations and subsets, are integral to deriving probability distributions and analyzing stochastic events.^[18]^[23] Combinatorial methods also contribute to coding theory through the development of error-correcting codes, which ensure reliable data transmission by detecting and correcting errors in binary strings.^[24] Additionally, combinatorics supports cryptography via structures such as designs and protocols for secure key establishment.^[25] In the modern era, combinatorics has seen growing relevance in data science, where it facilitates pattern recognition by identifying combinatorial structures in large datasets, such as recurring motifs in biological sequences or network anomalies. This utility extends to the 2020s AI landscape, addressing needs like combinatorial search in machine learning to explore vast solution spaces for optimization problems in neural network architectures and theorem proving. A specific example is its application in election systems, where combinatorial analysis underpins Arrow's impossibility theorem, revealing inherent limitations in designing fair voting procedures that aggregate individual preferences without bias or dictatorship.^[26]^[27]^[28]^[29] Combinatorics further intersects with graph theory, modeling relationships in networks for applications ranging from social connectivity to biological interactions.^[14]

Historical Development

Ancient and Medieval Contributions

The origins of combinatorial ideas trace back to ancient Indian texts, particularly the Sulba Sutras, composed around 800 BCE, which provided geometric instructions for constructing Vedic fire altars of specific shapes and areas using bricks arranged in precise patterns. These constructions required systematic enumeration of brick placements to achieve equivalent volumes across different forms, implicitly involving early notions of permutations and combinations to optimize arrangements without excess or deficiency. In ancient China, the Nine Chapters on the Mathematical Art, compiled around 200 BCE, addressed practical problems of distribution and arrangement, such as dividing resources fairly among groups or sequencing items in rows, which necessitated counting methods for equitable allocations. These problems, found in chapters on proportions and excesses, demonstrated rudimentary combinatorial reasoning applied to administrative and agricultural tasks, emphasizing systematic enumeration over abstract theory.^[30] Greek mathematicians contributed foundational problems with combinatorial elements, as seen in Euclid's Elements (circa 300 BCE), where Book VII explores divisibility and selections that resemble binomial-like enumerations, such as counting ways to partition numbers into sums. Euclid's propositions on relatively prime numbers and their divisions laid groundwork for later counting principles, though presented geometrically rather than algebraically. Similarly, Archimedes posed the Cattle Problem around 250 BCE, a Diophantine challenge requiring the determination of herd sizes satisfying proportional constraints across colored groups, which involves solving simultaneous equations with combinatorial implications for minimal integer solutions.^[30]^[31] In medieval India, Pingala's Chandaḥśāstra (circa 200 BCE) analyzed Sanskrit poetic meters through binary patterns of short (laghu) and long (guru) syllables, generating sequences that enumerate all possible combinations for a given length, effectively introducing recursive counting akin to modern binary representations. This work marked an early systematic approach to combinatorics in prosody, using algorithms to list and index patterns without formal notation.^[32] Islamic scholars advanced these ideas during the medieval period, with Al-Karaji (circa 1000 CE) developing methods for binomial coefficients in his algebraic treatise Al-Fakhri, where he computed sums of powers and expansions resembling the binomial theorem through iterative addition, providing a table of coefficients generated additively. Al-Karaji's approach, which included proof by mathematical induction for the first time, facilitated enumeration of terms in polynomial expansions without symbolic algebra. In China, Yang Hui's 1261 text Xiangjie jiuzhang suanfa presented a graphical precursor to Pascal's triangle, illustrating binomial coefficients as a triangular array for solving higher-degree equations and counting problems, building on earlier lost works by Jia Xian. These developments highlighted enumeration techniques driven by practical and algebraic needs, setting the stage for later European integrations during the Renaissance.^[33]^[34]^[35]

17th to 19th Century Foundations

In the 17th century, Blaise Pascal laid foundational work in combinatorics through his development of the arithmetical triangle, now known as Pascal's triangle, which systematically organized binomial coefficients and facilitated the calculation of combinations. This tool, detailed in his posthumously published Traité du triangle arithmétique (1665), provided a combinatorial method for solving problems in probability, such as dividing stakes in interrupted games, and predated formal algebraic proofs of the binomial theorem by figures like Isaac Newton.^[36] Pascal's approach emphasized counting arrangements without regard to order, influencing later systematic treatments of permutations and combinations.^[37] Gottfried Wilhelm Leibniz advanced these ideas in his Dissertatio de Arte Combinatoria (1666), where he explored the "art of combination" as a universal language for reasoning, including enumerative techniques for permutations and the introduction of factorial notation. Leibniz's work extended combinatorial methods to philosophical and logical applications, treating combinations as building blocks for knowledge representation. Concurrently, the Bernoulli family, particularly Jacob Bernoulli, contributed to early uses of generating functions in the late 17th and early 18th centuries; in his Ars Conjectandi (1713), Bernoulli employed power series expansions to analyze combinatorial probabilities, bridging counting principles with infinite series. These efforts by Leibniz and Bernoulli marked the initial formal application of generating functions to encode combinatorial sequences, such as those arising in probability calculations.^[38] Leonhard Euler's 18th-century contributions solidified combinatorics as a distinct field. In 1736, Euler addressed the Seven Bridges of Königsberg problem, proving it impossible to traverse all seven bridges exactly once and return to the starting point; this analysis, using degree conditions on vertices, served as a precursor to graph theory by modeling connectivity through abstract networks rather than geometric constraints. Euler also pioneered partition identities, demonstrating in the 1740s that the number of partitions of an integer into distinct parts equals the number of partitions into odd parts, using generating function techniques to establish infinite product representations. These results highlighted the power of analytic methods in enumeration.^[39]^[40] The 19th century saw further milestones in structural enumeration. Arthur Cayley enumerated trees in his 1857 paper "On the Theory of the Analytical Forms called 'Trees'," deriving recursive formulas for counting rooted and unrooted trees with labeled vertices, which laid groundwork for algebraic graph theory and applications in chemistry. James Joseph Sylvester complemented this with his work on invariants and partitions, introducing graphical representations of integer partitions in the 1850s and advancing invariant theory alongside Cayley to classify symmetric structures under group actions. These developments formalized combinatorial invariants, essential for understanding symmetry in enumerative problems. Links to probability theory emerged as these tools were applied to model random walks and distributions.^[41]

20th Century Expansion and Modern Advances

The 20th century marked a significant expansion in combinatorics, driven by foundational results that addressed problems in order and structure within large sets. In 1930, Frank P. Ramsey introduced what is now known as Ramsey theory through his paper "On a Problem of Formal Logic," establishing that in sufficiently large structures, certain ordered substructures are unavoidable, such as monochromatic cliques in graph colorings. This work laid the groundwork for studying inevitable patterns in combinatorics, influencing later developments in extremal graph theory. Building on this, Endre Szemerédi proved in 1975 his eponymous theorem, demonstrating that any subset of the integers with positive upper density contains arithmetic progressions of arbitrary length.^[42] Szemerédi's result resolved a long-standing conjecture and extended Ramsey-type ideas to additive combinatorics, with profound implications for number theory and ergodic theory. Post-World War II, combinatorics experienced a boom, fueled by innovative techniques and international collaboration. Paul Erdős pioneered the probabilistic method in the 1940s, notably in his 1947 paper "Some Remarks on the Theory of Graphs," where he used probability to prove the existence of graphs with specific properties without constructing them explicitly. This non-constructive approach revolutionized the field, enabling proofs of existence for combinatorial objects in extremal problems. The growth was further propelled by events like the 1950 International Congress of Mathematicians in Cambridge, Massachusetts, which attracted approximately 2,300 participants, signaling the field's institutionalization and interdisciplinary appeal amid post-war recovery.^[43] Combinatorial game theory emerged as a distinct subfield in the 1930s, with the Sprague-Grundy theorem providing a unified framework for analyzing impartial games. Independently developed by Roland Sprague in 1935 and Patrick M. Grundy in 1939, the theorem assigns a nimber (Grundy number) to each game position, allowing complex games to be decomposed into sums of simpler Nim heaps via the XOR operation. Recent applications have extended this to algorithm design, particularly in optimizing strategies for computational problems like network routing and resource allocation in multi-agent systems.^[44] From 2000 to 2025, combinatorics has integrated with emerging technologies, notably in quantum and artificial intelligence domains. Quantum combinatorics has advanced through quantum annealing algorithms for solving optimization problems, as demonstrated in benchmarks showing improved scalability for NP-hard combinatorial tasks on quantum hardware.^[45] Similarly, AI-driven tools have enhanced enumeration by generating conjectures and discovering structures in algebraic combinatorics, with datasets like ACBench enabling machine learning models to tackle research-level problems in posets and matroids. A notable 2023 development in extremal combinatorics was the proof of asymptotic bounds on the Ramsey number r(4,t) = Ω(t³ / log⁴ t), confirming a conjecture of Erdős up to logarithmic factors.^[46] These advances have influenced computer science by providing algorithmic frameworks for efficient discrete optimization.

Basic Concepts and Tools

Counting Principles

Counting principles form the foundational tools in combinatorics for determining the number of possible outcomes or configurations in a given scenario. These principles provide systematic methods to tally elements without direct enumeration, enabling the solution of complex problems by breaking them into simpler parts. They are essential prerequisites for more advanced enumerative techniques and apply broadly across mathematical and applied contexts. The multiplication principle, also known as the fundamental counting principle, states that if one event can occur in m ways and a second independent event can occur in n ways, then the two events together can occur in m \times n ways. This principle extends to any finite sequence of independent choices, where the total number of outcomes is the product of the individual possibilities; for instance, the number of ways to arrange three distinct books on a shelf is $3 \times 2 \times 1 = 6.^[47] The addition principle applies to mutually exclusive alternatives, asserting that if there are m ways to perform one action and n ways to perform a disjoint alternative action, then the total number of ways to perform either action is m + n. For example, if a committee can be formed by selecting from group A in 5 ways or from group B in 3 ways with no overlap, the total committees number 8.^[48] This principle generalizes to the sum over counts of disjoint sets in a union. The pigeonhole principle guarantees that if n items are distributed into m containers where n > m, then at least one container holds more than one item.^[49] Formally, in the generalized version, distributing n items into m containers ensures that at least one container has at least \lceil n/m \rceil items; a classic application shows that among any 13 people, at least two share a birth month since there are only 12 months.^[47] The inclusion-exclusion principle provides a method to count the size of the union of sets by accounting for overlaps: for two sets, |A \cup B| = |A| + |B| - |A \cap B|, and it extends recursively to n sets via alternating sums of intersections.^[48]

|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n|

This formula is derived from the additivity of disjoint unions and is crucial for avoiding overcounting.^[47] An illustrative application is the counting of derangements, permutations where no element appears in its original position; the number d(n) is given by inclusion-exclusion as d(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!}, which approximates to n!/e for large n, where e \approx 2.71828 is the base of the natural logarithm.^[47]

Recurrence Relations and Generating Functions

Recurrence relations provide a fundamental method for defining and solving counting problems in combinatorics by expressing the number of objects of size n in terms of smaller sizes. A linear homogeneous recurrence relation with constant coefficients takes the form a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} for n > k, where c_i are constants and initial conditions specify a_0, \dots, a_{k-1}.^[50] The solution involves the characteristic equation r^k - c_1 r^{k-1} - \cdots - c_k = 0, whose roots determine the closed-form expression for a_n.^[51] A classic example is the Fibonacci sequence, defined by the recurrence F_n = F_{n-1} + F_{n-2} for n \geq 2, with F_0 = 0 and F_1 = 1. This arises combinatorially in counting the number of ways to tile a $1 \times n board with tiles of size 1 and 2, where F_{n+1} gives the number of tilings.^[50] The characteristic equation is r^2 - r - 1 = 0, with roots \phi = (1 + \sqrt{5})/2 and \hat{\phi} = (1 - \sqrt{5})/2, yielding the Binet formula F_n = (\phi^n - \hat{\phi}^n)/\sqrt{5}.^[51] Generating functions offer a powerful algebraic tool for encoding sequences and solving recurrences in combinatorial enumeration. The ordinary generating function for a sequence \{a_n\}_{n \geq 0} is the formal power series A(x) = \sum_{n=0}^\infty a_n x^n, while the exponential generating function is A(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}.^[51] Ordinary generating functions suit unlabeled structures, such as combinations, whereas exponential ones are appropriate for labeled objects, like permutations, due to the factorial scaling. For products of structures, the generating functions multiply: if A(x) and B(x) are ordinary generating functions for two classes, then A(x) B(x) enumerates their disjoint unions or compositions.^[7] To solve counting problems, one constructs a generating function and extracts coefficients, often using series expansions. For distributing n indistinguishable items into k distinct bins (allowing empty bins), the ordinary generating function is (1 + x + x^2 + \cdots)^k = (1 - x)^{-k}. The coefficient [x^n] (1 - x)^{-k} = \binom{n + k - 1}{k - 1} gives the number of non-negative integer solutions to x_1 + \cdots + x_k = n, known as the stars-and-bars theorem.^[52] A prominent application is the Catalan numbers C_n, which count structures like correctly matched parentheses or binary trees with n nodes. They satisfy the recurrence C_0 = 1 and C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i} for n \geq 1, reflecting the decomposition of a structure into a root and two substructures. This yields the closed form C_n = \frac{1}{n+1} \binom{2n}{n}, derivable via the generating function C(x) = \sum C_n x^n = \frac{1 - \sqrt{1 - 4x}}{2x}.^[7] These tools extend to enumerating integer partitions by modeling part sizes recursively.^[51]

Enumerative Combinatorics

Permutations, Combinations, and Binomial Coefficients

Permutations are arrangements of distinct objects where the order matters. For a set of n distinct objects, the number of possible permutations is n!, the product of all positive integers up to n. More generally, the number of ways to arrange k objects out of n distinct ones, known as permutations of n things taken k at a time, is given by the formula

P(n,k) = \frac{n!}{(n-k)!},

which counts the sequential choices without replacement.^[7] Combinations, in contrast, are selections of objects where the order does not matter. The number of ways to choose k objects from n distinct ones is the binomial coefficient

\binom{n}{k} = C(n,k) = \frac{n!}{k!(n-k)!},

often read as "n choose k." This formula arises from dividing the number of permutations P(n,k) by k! to account for the indistinguishability of orderings within each selection. A key identity is \binom{n}{k} = \binom{n}{n-k}, reflecting the symmetry in choosing k elements or the complementary n-k elements.^[7] Binomial coefficients play a central role in the binomial theorem, which expands powers of a binomial expression:

(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k.

This theorem, in its modern form for positive integer exponents, was rigorously developed by Blaise Pascal in his 1654 treatise Traité du triangle arithmétique, where he demonstrated its properties using the arithmetical triangle (now known as Pascal's triangle). The coefficients \binom{n}{k} form the entries of this triangle, providing a tabular method for computation and revealing further identities, such as the hockey-stick identity \sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}.^[53]^[7] Beyond selections and arrangements of distinct objects, enumerating partitions into subsets involves Stirling numbers of the second kind, denoted S(n,k), which count the ways to divide n distinct objects into k non-empty unlabeled subsets. For example, S(3,2) = 3, corresponding to the partitions \{\{1\},\{2,3\}\}, \{\{2\},\{1,3\}\}, and \{\{3\},\{1,2\}\}. These numbers were first introduced analytically by James Stirling in his 1730 work Methodus differentialis, though their combinatorial interpretation emerged later. The total number of partitions of n objects into any number of non-empty subsets is the Bell number B_n = \sum_{k=1}^{n} S(n,k), with B_3 = 5. Stirling numbers connect to permutations via the formula k! \, S(n,k) = number of surjective functions from a set of n elements to a set of k elements.^[54]^[7] A classic application illustrating these concepts is the ballot theorem, which models scenarios of sustained superiority in sequences of events, such as vote counts. Formulated by Joseph Bertrand in 1887, the theorem states that if candidate A receives a votes and candidate B receives b votes with a > b \geq 0, then the number of ways for A to always lead B throughout the counting of the ballots is \frac{a - b}{a + b} \binom{a+b}{a}, or equivalently, the probability under uniform random ordering is \frac{a - b}{a + b}. This result relies on reflections of paths in the plane to count favorable lattice paths from (0,0) to (b,a) that stay above the line y = x.^[55]^[7]

Integer Partitions and Compositions

Integer partitions represent a fundamental way to decompose a positive integer n into a sum of positive integers, disregarding the order of the summands. Formally, a partition \lambda = (\lambda_1, \lambda_2, \dots, \lambda_k) of n, denoted \lambda \vdash n, satisfies \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_k \geq 1 and \sum_{i=1}^k \lambda_i = n. The partition function p(n) counts the number of distinct such partitions. For instance, the partitions of 4 are (4), (3,1), (2,2), (2,1,1), and (1,1,1,1), yielding p(4) = 5. In contrast, integer compositions of n are ordered sums of positive integers equaling n. A composition into k parts is a sequence (c_1, c_2, \dots, c_k) where each c_i \geq 1 and \sum_{i=1}^k c_i = n. The total number of compositions of n is $2^{n-1}, as can be seen by placing n-1 "bars" among n units with n-1 possible positions between them, each either occupied or not by a bar, or equivalently by the binomial theorem summing \sum_{k=1}^n \binom{n-1}{k-1} = 2^{n-1}. The ordinary generating function for the partition numbers p(n) is the infinite product

P(x) = \sum_{n=0}^\infty p(n) x^n = \prod_{k=1}^\infty \frac{1}{1 - x^k},

where p(0) = 1 by convention. This product arises from the geometric series expansion for each possible part size k, allowing zero or more occurrences of k in the partition. A landmark result on the growth of p(n) is the Hardy–Ramanujan asymptotic formula, which states that

p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left( \pi \sqrt{\frac{2n}{3}} \right)

as n \to \infty. This approximation captures the rapid exponential growth of partitions and has been refined into exact formulas using the circle method. Partitions can be structurally analyzed using Ferrers diagrams, where a partition is depicted as rows of dots or boxes with \lambda_i boxes in the i-th row. The conjugate partition \lambda' is obtained by reflecting the diagram over its main diagonal, transposing rows and columns, so the parts of \lambda' are the column lengths of \lambda. Conjugation provides a bijection between partitions with largest part at most m and those with at most m parts. The Durfee square of a partition is the largest k \times k square fitting in the upper-left corner of its Ferrers diagram, where k is the largest integer such that \lambda_k \geq k; it partitions the diagram into the square, a subsequent partition to the right, and one below, aiding in recursive decompositions and generating function derivations.

Structural Combinatorics

Graph Theory Fundamentals

In graph theory, a fundamental branch of combinatorics, a graph G is formally defined as an ordered pair (V, E), where V is a finite set of vertices (also called nodes) and E is a set of edges, each connecting a pair of vertices from V./02:_Induction_and_Recursion/2.03:_Graph_and_Trees) Graphs serve as combinatorial models for pairwise relations between objects, with vertices representing the objects and edges the relations. The number of edges is denoted by m = |E|, and the degree d(v) of a vertex v \in V is the number of edges incident to it./02:_Induction_and_Recursion/2.03:_Graph_and_Trees) Graphs are classified by the nature of their edges. An undirected graph has edges without direction, meaning connections are symmetric between vertices. In contrast, a directed graph (or digraph) assigns a direction to each edge, indicating an asymmetric relation from one vertex to another. Weighted graphs extend these by associating a numerical weight with each edge, often representing distances, costs, or capacities in applications./15:_Basics_of_Networks/15.02:_Terminologies_of_Graph_Theory) A key combinatorial property is captured by the handshaking lemma, which states that in any undirected graph, the sum of the degrees of all vertices equals twice the number of edges: \sum_{v \in V} d(v) = 2m. This lemma, first established by Leonhard Euler in his 1736 analysis of the Königsberg bridges problem, underscores the parity of edge contributions to vertex degrees and implies that the number of odd-degree vertices is even.^[56] Trees represent a basic acyclic structure in graphs: a tree is a connected undirected graph with no cycles, containing exactly n-1 edges for n = |V| vertices. The enumeration of trees is exemplified by Cayley's formula, which counts the number of distinct spanning trees in the complete graph K_n on n labeled vertices as n^{n-2}. This result, proved by Arthur Cayley in 1889, highlights the exponential growth in the number of tree structures and has implications for network design and phylogenetic modeling.^[57] Paths and cycles are sequences of edges connecting vertices without repetition (except possibly the start and end for cycles). An Eulerian cycle traverses every edge exactly once and returns to the starting vertex, requiring all vertices to have even degree in a connected graph. A Hamiltonian cycle, conversely, visits every vertex exactly once before returning, a problem that is NP-complete to determine in general. A sufficient condition for the existence of a Hamiltonian cycle in a simple graph with n \geq 3 vertices is given by Dirac's theorem: if every vertex has degree at least n/2, then the graph contains such a cycle. This 1952 result by Gabriel Dirac provides a degree-based guarantee for Hamiltonicity in dense graphs. Planar graphs are those that can be embedded in the plane without edge crossings, modeling maps and circuits. For a connected planar graph with V vertices, E edges, and F faces (including the outer face), Euler's formula asserts V - E + F = 2. Originally derived by Leonhard Euler in 1752 for polyhedra and extended to planar graphs, this relation bounds the complexity of planar embeddings, implying E \leq 3V - 6 for simple planar graphs with V \geq 3.^[58]

Design Theory and Finite Geometries

Design theory is a branch of combinatorics concerned with the systematic arrangement of elements into subsets, known as blocks, such that specified collections of elements appear together in blocks with uniform frequency. These structures ensure balanced coverage of subsets, making them useful for modeling symmetric configurations and solving covering problems. Block designs, a central concept in this area, generalize simpler combinatorial arrangements by imposing regularity conditions on how elements and their combinations are distributed across blocks.^[59] A balanced incomplete block design, or BIBD, denoted by parameters (v, b, r, k, \lambda), consists of a set of v points and b blocks, each of size k < v, such that every point appears in exactly r blocks and every pair of distinct points appears together in exactly \lambda blocks. The parameters satisfy the fundamental relations b k = v r and \lambda (v-1) = r (k-1), which ensure the design's balance and consistency. This framework was formalized in the context of statistical applications, where blocks represent experimental units grouped to control variability.^[60] Steiner systems represent a special class of BIBDs where \lambda = 1 for pairs (i.e., t=2), and more generally, a Steiner system S(t, k, v) is a set of v points and k-element blocks such that every t-subset of points is contained in exactly one block. These systems achieve maximal efficiency in covering t-tuples without repetition, and their existence depends on divisibility conditions derived from the design parameters. A classic example is the Fano plane, which is the Steiner system S(2, 3, 7) consisting of 7 points and 7 lines (blocks), each line containing 3 points, and it serves as the smallest projective plane.^[61] The Kirkman's schoolgirl problem, posed in 1850, illustrates a resolvable BIBD, where the blocks can be partitioned into parallel classes that each cover all points exactly once. In this problem, 15 schoolgirls walk in groups of 3 over 7 days such that every pair walks together exactly once, forming a resolvable S(2, 3, 15) with 35 triples divided into 7 parallel classes of 5 triples each. Resolvability adds a partitioning property that enhances applicability in scheduling and grouping scenarios.^[62] Finite geometries provide geometric interpretations of these designs, embedding them in abstract spaces with incidence structures analogous to Euclidean geometry but over finite sets. A projective plane of order n (where n is a prime power) has n^2 + n + 1 points and the same number of lines, with each line containing n+1 points and every pair of points lying on exactly one line, making it a Steiner system S(2, n+1, n^2 + n + 1). An affine plane of order n has n^2 points and n(n+1) lines, each with n points, and every pair of points on exactly one line, forming an S(2, n, n^2). These planes, constructed using finite fields, capture essential symmetries and have inspired constructions of higher-dimensional finite geometries.^[63] In statistics, block designs like BIBDs are applied in experimental design to allocate treatments to units while minimizing bias from extraneous factors, as pioneered by Ronald Fisher to improve the precision of comparative trials in agriculture and beyond. These configurations allow efficient estimation of treatment effects under resource constraints. Additionally, the balanced structures of designs find use in coding theory for constructing error-correcting codes with optimal distance properties.^[64]

Analytic and Probabilistic Combinatorics

Analytic Combinatorics Techniques

Analytic combinatorics techniques employ complex analysis to derive precise asymptotic approximations for the coefficients of generating functions that arise in the enumeration of combinatorial structures. By examining the behavior of these functions near their dominant singularities in the complex plane, one can obtain explicit formulas for the growth rates and finer corrections of the sequence of coefficients, enabling quantitative predictions for large-scale combinatorial phenomena. This approach is particularly suited to problems where generating functions satisfy functional equations, such as those from recursive decompositions in enumerative combinatorics.^[65] Central to these methods are the transfer theorems, which systematically link the singular expansion of a generating function f(x) around its dominant singularity \rho to the asymptotics of [x^n] f(x). For a singularity of the form f(x) \sim g\left(1 - \frac{x}{\rho}\right) where g admits a Laurent or Puiseux series expansion, the theorems translate algebraic, logarithmic, or other local behaviors into corresponding contributions to the coefficients, often via Darboux integrals or residue calculus. These theorems facilitate automated asymptotic extraction for a wide class of "admissible" singularities, ensuring rigorous error bounds and higher-order terms when needed.^[65] The Flajolet-Odlyzko framework provides a foundational toolkit for handling algebraic singularities, common in combinatorial generating functions derived from algebraic specifications. In this setting, if the generating function exhibits a singularity of algebraic type, such as f(x) \sim c \left(1 - \frac{x}{\rho}\right)^{-\alpha} near x = \rho, the coefficient extraction yields [x^n] f(x) \sim c \, n^{\alpha - 1} \rho^{-n} / \Gamma(\alpha) for non-integer \alpha > 0, with adaptations for logarithmic factors or multiple scales. This method underpins many applications in enumerative problems, offering uniform asymptotics across families of structures defined by recursive constructions.^[65] For generating functions amenable to integral representations, such as those involving Cauchy integrals over contours enclosing the origin, the saddle-point method delivers asymptotic estimates by optimizing the contour deformation to critical points of the integrand's phase. At a saddle point where the derivative of the phase function vanishes but the function itself is nonzero, a local Gaussian approximation around the point dominates the integral, yielding leading exponential growth modulated by subexponential factors like powers of n. This technique excels in scenarios with entire functions or essential singularities, complementing singularity analysis for exponential generating functions. A paradigmatic example is the enumeration of labeled trees via the exponential generating function T(x) satisfying T(x) = x \exp(T(x)), which counts rooted labeled trees. Singularity analysis reveals a dominant singularity at \rho = 1/e with square-root branching, and application of the transfer theorems gives [x^n] T(x) / n! \sim n^{n-1} e^{-n} / \sqrt{2 \pi n}, confirming Cayley's formula n^{n-1} for the exact count up to the Stirling approximation. This asymptotic captures the exponential growth aligned with the radius of convergence and the polynomial correction from the singularity type. For permutations with restricted positions, where certain entries are forbidden in the permutation matrix (as in rook placements or generalized derangements), the exponential generating function often takes the form of an exponential of a kernel or a product over allowed positions. Using singularity analysis, asymptotics can be derived from the dominant singularity determined by the support of the restriction matrix; for instance, in the classical derangement case (restrictions on the diagonal), the generating function e^{-x}/(1-x) has a simple pole at x=1, yielding the asymptotic !n \sim n!/e. More general cases, such as band restrictions or sparse forbidden sets, lead to algebraic singularities analyzable via the Flajolet-Odlyzko framework, producing terms like c \rho^{-n} n^{-\alpha} where \alpha reflects the singularity order.^[65]

Probabilistic Methods and Extremal Combinatorics

Probabilistic methods in combinatorics provide non-constructive proofs for the existence of combinatorial structures by analyzing random objects and showing that desirable properties hold with positive probability. Pioneered by Paul Erdős, these techniques often involve random graphs, such as the Erdős–Rényi model G(n,p), where each possible edge is included independently with probability p, to establish bounds in extremal problems. For instance, Erdős demonstrated the existence of graphs on n vertices containing no clique of size r and no independent set of size s, by showing that a random graph G(n,1/2) avoids both with positive probability when certain binomial inequalities are satisfied. This approach revolutionized extremal graph theory by proving existence without explicit construction.^[66] A key refinement is the Lovász Local Lemma, which addresses dependencies among bad events in probability spaces. Consider a probability space with bad events A_1, ..., A_m, each with Pr(A_i) ≤ p, where each A_i is mutually independent of all but at most d others. The symmetric version states that if e p (d+1) ≤ 1, then Pr(∩ \bar{A_i}) > 0, ensuring the simultaneous avoidance of all bad events with positive probability. Introduced by Erdős and Lovász to resolve hypergraph coloring problems, the lemma has broad applications in extremal combinatorics, such as bounding the chromatic number of random hypergraphs or guaranteeing large subgraphs with prescribed properties in random graphs.^[67] Extremal combinatorics seeks the maximum size of structures avoiding forbidden subconfigurations, often yielding precise bounds via probabilistic or deterministic methods. Turán's theorem provides the canonical example for graphs: the maximum number of edges in an n-vertex K_r-free graph is achieved by the complete (r-1)-partite Turán graph T(n, r-1), with ex(n, K_r) = \left\lfloor \frac{n^2}{2} \left(1 - \frac{1}{r-1}\right) \right\rfloor. This result, proven constructively, underpins many extremal problems and connects to probabilistic existence proofs for near-extremal graphs. In the bipartite case, the Zarankiewicz problem asks for the maximum edges in an m × n bipartite graph without a K_{s,t} subgraph, with the Kővári–Sós–Turán theorem giving z(m,n; s,t) ≤ (s-1)^{1/t} n m^{1-1/t} + (t-1) m, a bound derived partly through extremal considerations and influencing incidence geometry.^[68]^[69]

Algebraic and Geometric Combinatorics

Algebraic Combinatorics

Algebraic combinatorics utilizes algebraic structures, particularly groups and their representations, to analyze and enumerate combinatorial objects that exhibit symmetry. This approach bridges abstract algebra with counting problems, enabling the resolution of complex enumeration tasks through linear algebra and group-theoretic insights. Key developments include the application of group actions to count orbits of symmetric structures and the use of representation theory to decompose permutation representations into irreducibles, often visualized via Young tableaux. A fundamental tool in algebraic combinatorics is the study of group actions on sets, where a group G acts on a set X to produce orbits representing equivalence classes under the action. To count the number of distinct orbits |X/G|, Burnside's lemma provides the formula

|X/G| = \frac{1}{|G|} \sum_{g \in G} \fix(g),

where \fix(g) denotes the number of fixed points of g in X. This lemma, originally presented in Burnside's work on finite group theory, is widely applied to count colorings, necklaces, and other symmetric configurations up to group symmetry. For instance, it enumerates the distinct ways to color the faces of a cube with six colors under rotations. In representation theory, the symmetric group S_n plays a central role, as its irreducible representations are indexed by partitions \lambda of n and closely linked to Young tableaux. The character of the irreducible representation corresponding to \lambda, evaluated at a conjugacy class, can be computed using combinatorial properties of Young tableaux, such as the number of fixed points under permutations visualized in the tableaux. This connection, developed through Young's quantitative substitutional analysis, allows for the decomposition of permutation representations and provides insights into the symmetries of combinatorial objects like permutations and set partitions. Seminal constructions here include the use of Young symmetrizers to project onto these representations. Specht modules form the algebraic backbone for these representations over fields of characteristic zero. For a partition \lambda \vdash n, the Specht module S^\lambda is the irreducible module generated by the polytabloid associated with a standard Young tableau of shape \lambda. Introduced by Specht in his comprehensive theory of finite group representations, these modules span the representation space and are defined via antisymmetrizers and symmetrizers over rows and columns of the tableau. A key result is the hook-length formula, which gives the dimension of S^\lambda as the number f^\lambda of standard Young tableaux of shape \lambda:

f^\lambda = \frac{n!}{\prod h(u)},

where the product runs over all cells u in the Young diagram of \lambda, and h(u) is the hook length of u (the number of cells to the right and below u, plus one for u itself). Discovered by Frame, Robinson, and Thrall, this formula simplifies the computation of representation dimensions and has profound combinatorial implications. Polynomial identities in algebraic combinatorics often arise from generating function techniques applied to structured objects like plane partitions. The MacMahon Master Theorem exemplifies this, providing a closed-form determinant expression for the generating function of coefficients in products of linear forms. Specifically, for an m \times m matrix A = (a_{ij}) and variables x_1, \dots, x_m, let G(k_1, \dots, k_m) be the coefficient of x_1^{k_1} \cdots x_m^{k_m} in \prod_{i=1}^m (\sum_{j=1}^m a_{ij} x_j)^{k_i}. Then the generating function \sum G(k) t_1^{k_1} \cdots t_m^{k_m} = 1 / \det(I_m - T A), where T = \diag(t_1, \dots, t_m). Originally proved by MacMahon in his foundational work on combinatory analysis, this theorem generates explicit formulas for multivariate sums and has applications to enumerating plane partitions and other lattice structures. For plane partitions specifically, it yields the generating function \prod_{k=1}^\infty (1 - q^k)^{-k}, highlighting connections to partition theory.^[70] q-Analogs extend classical combinatorial counts to incorporate a parameter q, often tracking statistics like inversions or area. The Gaussian binomial coefficient, or q-binomial coefficient, q-analogizes the binomial coefficient:

\binom{n}{k}_q = \prod_{i=1}^k \frac{1 - q^{n - i + 1}}{1 - q^i} = \frac{(q; q)_n}{(q; q)_k (q; q)_{n-k}},

where (a; q)_m = \prod_{i=0}^{m-1} (1 - a q^i) is the q-Pochhammer symbol. This counts subspaces in vector spaces over finite fields or lattice paths avoiding certain regions, with q weighting the paths by area or turns. Developed in the context of q-series and basic hypergeometric functions, it underlies many q-identities and refinements in algebraic combinatorics.

Geometric and Topological Combinatorics

Geometric combinatorics examines the enumeration of configurations invariant under geometric symmetries, such as rotations of polyhedra or tilings. A key tool is Pólya's enumeration theorem, which counts distinct colorings of a geometric object under the action of a symmetry group G, like the cyclic group of rotations for a necklace. The cycle index of G is defined as Z(G) = \frac{1}{|G|} \sum_{g \in G} \fix(g), where \fix(g) is the number of colorings fixed by group element g, typically computed as the product over cycle lengths in the permutation induced by g. For example, applying this to coloring the faces of a cube under its rotation group yields the number of distinct colorings with a given palette.^[71] This approach builds on algebraic tools like Burnside's lemma for averaging fixed points under group actions.^[72] Simplicial complexes provide a discrete model for geometric spaces, consisting of vertices, edges, and higher-dimensional simplices satisfying closure under faces. The f-vector (f_0, f_1, \dots, f_d) records the number of simplices of each dimension, from f_0 vertices to f_d maximal d-simplices. A fundamental topological invariant is the Euler characteristic \chi = \sum_{i=-1}^{d} (-1)^i f_i, where f_{-1} = 1 accounts for the empty simplex, linking combinatorial data to global topology; for instance, \chi = 2 for sphere-like complexes and \chi = 1 for disk-like ones.^[73] These invariants facilitate the study of connectivity and holes in geometric configurations. Shellability extends combinatorial structure to partially ordered sets (posets) associated with simplicial complexes, where a poset is shellable if its order complex admits a shelling order of facets such that each new facet intersects the previous union in a face. This property implies sequential Cohen-Macaulayness of the Stanley-Reisner ring over the poset, meaning the ring is Cohen-Macaulay after localizing at each prime ideal, which ensures strong homological properties like vanishing of certain Tor groups. For example, the face poset of a polytope is often shellable, enabling efficient computation of Betti numbers. Topological graph theory investigates embeddings of graphs into surfaces, focusing on planarity and obstructions. A graph is planar if it admits a crossing-free embedding in the plane, characterized by Kuratowski's theorem: a graph is non-planar if and only if it contains a subdivision of K_5 or K_{3,3} as a subgraph. The crossing number \cr(G) is the minimum number of edge crossings in any drawing of G in the plane, quantifying embedding complexity; for complete graphs, \cr(K_n) = \frac{1}{4} \floor{\frac{n}{2}} \floor{\frac{n-1}{2}} \floor{\frac{n-2}{2}} \floor{\frac{n-3}{2}} provides an exact formula.^[74]^[75] Recent advances in combinatorial topology have enhanced data visualization through tools like the Mapper algorithm, which constructs simplicial complexes from point cloud data to reveal topological features such as clusters and loops. In 2024, differentiable variants of Mapper enable optimization of filter functions for better representation of high-dimensional datasets, improving interpretability in applications like biomedical imaging.^[76]

Advanced and Infinitary Topics

Combinatorics on Words and Arithmetic Combinatorics

Combinatorics on words examines finite and infinite sequences, or words, over a finite alphabet, with a focus on structural properties such as the avoidance of repetitive patterns. A fundamental concern is the avoidance of powers, where a k-power is a word of the form w^k = www\cdots w (k times) for a nonempty word w. Axel Thue demonstrated the existence of infinite words avoiding cubes ($3-powers) over a [ternary](/page/Ternary) alphabet and overlaps (specific 2^+-powers of the form axaxa, where ais a single letter andx$ a word) over a binary alphabet.^[77] The Thue-Morse sequence provides a canonical example of an overlap-free binary word. Defined as the fixed point of the uniform morphism \mu: 0 \mapsto 01, $1 \mapsto 10 starting from $0, it begins 0110100110010110\cdotsand avoids both overlaps and cubes, ensuring no subword repeats a block three or more times consecutively. This construction, also due to Thue, highlights the richer avoidance possibilities over [binary](/page/Binary) alphabets for weaker repetition classes compared to square-free words (avoidingww$), which require at least three letters.^[77] Overlap-free binary words form a rich family studied through morphisms and automata, with the Thue-Morse sequence generating many via iterations. The growth of such words is subexponential, and their subword complexity is linear, reflecting the constrained structure imposed by avoidance. Thue's results established the foundations for repetition avoidance, influencing subsequent work on pattern-avoiding languages.^[77] Automatic sequences represent another key class in combinatorics on words, generated by finite automata or uniform morphisms (where all letters map to words of equal length). These sequences are recognized by automata reading their terms in a given base, yielding morphic words fixed by iterated substitutions. The Fibonacci word, produced by the nonuniform morphism \sigma: 0 \mapsto 01, $1 \mapsto 0 starting from $0, is a prototypical example: its infinite fixed point 010010100100101001010\cdotsis Sturmian (with subword complexityp(n) = n+1$) and avoids long squares.^[78] Arithmetic combinatorics investigates combinatorial structures in additive groups, particularly subsets of integers avoiding certain equations or progressions. Sum-free sets are subsets A \subseteq \mathbb{N} such that A \cap (A + A) = \emptyset, meaning no x, y, z \in A satisfy x + y = z. The maximal size of a sum-free subset of \{1, \dots, n\} is \lceil n/2 \rceil, achieved by the odd integers or \{ \lceil n/2 \rceil + 1, \dots, n \}, providing density $1/2 asymptotically. Erdős proved that every set of m positive integers contains a sum-free subset of size at least c \log m for some absolute c > 0, with recent improvements to \log^{1+c} m. Schur numbers S(k) arise in Ramsey theory for sumsets: S(k) is the smallest integer such that every k-coloring of \{1, \dots, S(k)\} yields a monochromatic triple x, y, z with x + y = z. Issai Schur established the existence of S(k) for all k, originally in the context of solutions modulo primes, with known values including S(1) = 2, S(2) = 5, S(3) = 14, S(4) = 45, and S(5) = 161 (determined in 2017). These numbers quantify the inevitability of monochromatic solutions in colorings, with growth superlinear in k.^[79] Roth's theorem addresses arithmetic progressions (APs): any subset A \subseteq \{1, \dots, n\} with |A| \geq \delta n for fixed \delta > 0 contains a nontrivial 3-term AP \{x, x+d, x+2d\} (d > 0), implying the maximal size r_3(n) of 3-AP-free subsets satisfies r_3(n) = o(n). Klaus Roth proved this in 1953 using Fourier analysis and density increment arguments on intervals, establishing that 3-AP-free sets have vanishing density; subsequent refinements yield r_3(n) \ll n / \log \log n. This result initiated quantitative additive combinatorics, contrasting with van der Waerden's qualitative guarantees.^[80] Van der Waerden numbers W(k, r) extend this to colorings: W(k, r) is the smallest N such that every r-coloring of \{1, \dots, N\} contains a monochromatic k-term AP. Bartel van der Waerden proved in 1927 that W(k, r) < \infty for all k, r \geq 1, resolving a conjecture of Baudet via compactness and finite Ramsey theory. Known values include W(3, 2) = 9 and W(3, 3) = 27, with W(3, 4) = 76 and W(3, 5) = 178, while bounds grow tower-like in k and exponentially in r, reflecting the theorem's role in forcing structure in colorings.^[81]

Infinitary Combinatorics and Matroid Theory

Infinitary combinatorics extends classical combinatorial principles to infinite structures, often employing cardinal arithmetic to analyze partitions of infinite sets. For an infinite cardinal κ, the cardinality of the set of all partitions of a set of size κ into finitely many nonempty subsets is κ, reflecting basic operations in cardinal arithmetic where unions and products preserve the maximum cardinality for infinite sets.^[82] More generally, the partition calculus, initiated by Erdős and Rado, studies relations of the form κ → (λ)^μ_n, which assert that in any coloring of the n-element subsets of a set of cardinality κ with μ colors, there exists a monochromatic subset of cardinality λ; these relations quantify the unavoidable order in infinite colorings and connect to larger cardinal properties.^[82] A foundational result in this area is König's infinity lemma, which states that every infinite tree with finite branching degree contains an infinite path.^[83] This lemma bridges finite and infinite combinatorics by enabling compactness arguments, such as proving the existence of infinite branches in trees representing sequences of finite choices, and it underpins many proofs in descriptive set theory and graph theory on infinite graphs. The infinite Ramsey theorem further exemplifies these ideas: in any 2-coloring of the edges of the complete graph on countably infinite vertices, there exists an infinite monochromatic clique.^[84] Equivalently, every infinite graph contains either an infinite clique or an infinite independent set, highlighting the persistence of order in infinite random-like structures.^[84] Matroid theory abstracts the notion of independence from linear algebra and graph theory to general finite sets, providing a unified framework for combinatorial optimization. Introduced by Whitney, a matroid is defined on a finite ground set E via a family ℐ of independent subsets satisfying three axioms: (I1) the empty set is independent; (I2) every subset of an independent set is independent; and (I3) if A, B ∈ ℐ with |A| < |B|, then there exists e ∈ B \ A such that A ∪ {e} ∈ ℐ (the augmentation property).^[85] An equivalent formulation uses the exchange property: for distinct elements e, f in E and A ∈ ℐ, if e ∈ ℐ(A ∪ {e}) but f ∉ ℐ(A ∪ {f}), then f ∈ ℐ(A ∪ {e}). The rank function r: 2^E → ℕ of a matroid assigns to each subset S ⊆ E the maximum size of an independent subset of S, i.e., r(S) = max{|I| : I ∈ ℐ, I ⊆ S}, and it satisfies r(∅) = 0, monotonicity r(X) ≤ r(Y) for X ⊆ Y, and submodularity r(X ∪ Y) + r(X ∩ Y) ≤ r(X) + r(Y).^[85] Specific classes of matroids illustrate these concepts. The graphic matroid of a graph G = (V, E) has ground set E and independent sets corresponding to the forests (acyclic subgraphs) of G, where the rank of a subset of edges equals the number of vertices minus the number of connected components in the subgraph they induce.^[85] Uniform matroids U_{k,n}, defined on a ground set of n elements, consist of all subsets of size at most k as independent sets, capturing maximal independence without structural constraints like cycles.^[86] Matroids support operations of deletion and contraction: deleting an element e from M yields M \ e with independent sets {I ∈ ℐ : e ∉ I}, while contracting e produces M / e with independent sets {I ∈ ℐ : e ∉ I} ∪ {I ∪ {e} : I ∪ {e} ∈ ℐ, I ⊆ E \ {e}}; a minor of M is any matroid obtained by a sequence of such operations.^[85] A matroid M on E is representable over a field F if there exists a matrix A with columns indexed by E over F such that the independent sets of M are precisely the linearly independent columns of A; graphic matroids are representable over any field, as they arise from the incidence matrix of the graph.^[85] Uniform matroids U_{k,n} are representable over F whenever the characteristic of F does not divide binomial coefficients in certain ways, but not all matroids are representable; for instance, the non-Pappus matroid violates field axioms and is unrepresentable over any field. Minors play a key role in representability: a class of matroids representable over a fixed finite field F is characterized by forbidding a finite set of minors, as resolved by the solution to Rota's conjecture.^[86]

Combinatorial Optimization and Algorithms

Combinatorial optimization involves finding the optimal solution among a finite set of possibilities, often modeled as discrete structures like graphs or sets, where exact solutions are sought under constraints. These problems frequently arise in operations research and computer science, requiring algorithms that efficiently navigate exponential search spaces. Key techniques adapt continuous optimization methods to discrete domains, such as integer linear programming, which extends linear programming to require integer variables for applications like scheduling and resource allocation. Seminal advancements include adaptations of the simplex method for integer constraints, ensuring termination and optimality in polynomial time for linear relaxations while handling integrality through iterative refinements.^[87] In integer linear programming (ILP), the simplex method, originally developed by George Dantzig for solving linear programs by traversing vertices of the feasible polyhedron, is adapted via cutting planes and branch-and-bound procedures to enforce integer solutions. Cutting planes, introduced by Ralph Gomory, generate valid linear inequalities that eliminate fractional solutions from the linear programming relaxation without excluding integer-feasible points; for instance, from an optimal simplex tableau row a_j = f_j + i_j where $0 < f_j < 1 and i_j is integer, the cut \sum f_j x_j \geq 1 (for non-basic variables) tightens the formulation. This process repeats until an integer solution is obtained, with Gomory's mixed-integer extension allowing fractional coefficients. Complementarily, branch-and-bound, proposed by Ailsa Land and Alison Doig, systematically partitions the solution space by branching on fractional variables (e.g., fixing x_k \leq \lfloor x_k^* \rfloor or x_k \geq \lceil x_k^* \rceil) and bounding subproblems using linear relaxations to prune infeasible or suboptimal branches, guaranteeing global optimality. These adaptations have enabled practical solvers like CPLEX to handle large-scale ILPs in logistics.^[87] For bipartite graphs, matching problems seek to pair vertices to maximize edges without sharing endpoints, with König's theorem establishing that the size of the maximum matching equals the size of the minimum vertex cover—a set of vertices incident to all edges. Formally, in a bipartite graph G = (U \cup V, E), if \nu(G) is the matching number and \tau(G) the vertex cover number, then \nu(G) = \tau(G), proven via the max-flow min-cut theorem by modeling the graph as a flow network with unit capacities on edges from a source to U, V to sink, and infinite on bipartition edges; the minimum cut corresponds to a minimum vertex cover. This duality enables polynomial-time algorithms like the Hungarian method to compute both simultaneously. Network flow algorithms generalize matching to directed graphs with capacities, where the Ford-Fulkerson method computes maximum flow from source s to sink t by iteratively finding augmenting paths in the residual graph and updating flows until no path exists. The max-flow min-cut theorem states that the maximum flow value equals the minimum cut capacity—a partition (S, T) with s \in S, t \in T, minimizing the sum of capacities from S to T—with the theorem proven by showing any s- t flow saturates some cut and residual paths imply no minimum cut is reached. For integer capacities, the algorithm yields integer flows, and implementations like Edmonds-Karp using BFS run in O(VE^2) time. These techniques optimize transportation and assignment under capacity constraints.^[88]^[88] Many combinatorial optimization problems, including the traveling salesman problem (TSP)—finding the shortest Hamiltonian cycle in a complete graph with edge weights—are NP-complete, meaning no known polynomial-time algorithm solves them exactly for all instances, and verifying solutions is efficient. Richard Karp demonstrated TSP's NP-completeness in 1972 by reducing the Hamiltonian cycle problem (itself NP-complete via Cook's theorem) to TSP through dynamic programming gadgets that preserve cycle existence while incorporating weights. This hardness motivates approximation algorithms, such as Christofides' 1.5-approximation for metric TSP. Recent advances leverage quantum computing for NP-hard problems via the quantum approximate optimization algorithm (QAOA), proposed by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, which applies alternating unitary operators e^{-i\beta_p H_M} e^{-i\gamma_p H_C} (for mixer H_M and cost H_C Hamiltonians) over p layers to approximate ground states encoding optimal solutions, optimized classically. In 2025, developments include multi-objective QAOA variants that handle trade-offs in conflicting objectives without parameter retraining on quantum hardware, achieving better scalability for problems like MaxCut on NISQ devices. Additionally, adaptive QAOA extensions dynamically tailor operators to problem instances, showing empirical speedups over classical heuristics for large-scale combinatorial tasks.^[89]^[90]

Applications in Computer Science and Physics

In computer science, universal hashing employs families of hash functions designed to ensure that the probability of collisions between any two distinct keys is at most 1/M, where M is the size of the hash table, providing a probabilistic guarantee against worst-case adversarial inputs. This approach, introduced by Carter and Wegman, enables efficient randomized data structures like hash tables that achieve expected constant-time operations while mitigating attacks on deterministic hashing.^[91] SAT solvers, central to automated reasoning and verification, utilize conflict-driven clause learning (CDCL) algorithms that systematically enumerate partial variable assignments through backtracking while dynamically adding learned clauses to prune the search space and avoid redundant explorations. This combinatorial enumeration over the exponential space of Boolean assignments, combined with unit propagation and clause minimization, allows modern solvers like MiniSat to tackle industrial-scale satisfiability problems with millions of clauses efficiently.^[92] In artificial intelligence and machine learning, combinatorial bandits extend multi-armed bandit frameworks to scenarios in reinforcement learning where actions involve selecting subsets or combinations of options, such as resource allocation in networks, with regret bounds achieved via semi-bandit feedback models. For instance, algorithms like Combinatorial Upper Confidence Bound (CUCB) balance exploration and exploitation over combinatorial action spaces, enabling applications in online advertising and sensor selection. Neural architecture search (NAS) leverages enumeration techniques within combinatorial multi-armed bandit formulations to explore vast design spaces of deep neural networks, decomposing the search into subproblems for efficient sampling and evaluation of architectures like convolutional layers.^[93] In physics, the partition function in statistical mechanics sums over all possible microstates weighted by their Boltzmann factors, encapsulating combinatorial enumerations of configurations such as spin alignments in the Ising model or particle arrangements in gases to derive thermodynamic properties like free energy. Stabilizer codes in quantum error correction define error-correcting subspaces as the +1 eigenspace of an abelian subgroup of the Pauli group, relying on combinatorial constructions from classical linear codes to detect and correct errors on logical qubits while preserving quantum coherence. Briefly, de Bruijn graphs model genome assembly as Eulerian path finding in overlap graphs of k-mers, combinatorially reconstructing sequences from short reads in bioinformatics applications.^[94]^[95]^[96]

References

[1]
[PDF] What is combinatorics? - UCLA Mathematics
Combinatorics is a branch of mathematics concerned with selecting, arranging, constructing, classifying, and counting things, and the theory of enumeration.
[2]
MAT378 – discrete Mathematics II – Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the ...
[3]
MAT 3650 - INTRODUCTION TO COMBINATORICS - Elmira College
Combinatorics is the study of counting and enumeration problems that arise from discrete structures in mathematics such as sets, graphs and sample spaces.
[4]
[PDF] subject: A Brief Survey of Combinatorics - UCSD Math
mathematics and its applications. History. Early developments. Certain types of combinatorial problems have fascinated mathematicians since early times.
[5]
Discrete Mathematics: Past, Present, and Future
The beginning of Combinatorics as we know it today started with the work of Pascal and De Moivre in the 17th century, and continued in the 18th century with the ...
[6]
[PDF] Enumerative and Algebraic Combinatorics in the 1960's and 1970's
Three further mathematicians who were active in enumerative combina- torics prior to 1960 (and afterwards) are John Riordan (1903–1988), Leonard. Carlitz (1907– ...<|separator|>
[7]
[PDF] Enumerative Combinatorics Volume 1 second edition - Mathematics
What is Enumerative Combinatorics? Enumerative combinatorics has undergone enormous development since the publication of the first edition of this book in 1986.
[8]
[PDF] A Course in Combinatorics, SECOND EDITION
This is the second edition of a popular book on combinatorics, a subject dealing with ways of arranging and distributing objects, and which involves.
[9]
Combinatorics - MIT Mathematics
Combinatorics involves the general study of discrete objects. Reasoning about such objects occurs throughout mathematics and science.
[10]
[PDF] Probabilistic Combinatorics
Mar 15, 2019 · The probabilistic method was spearheaded by Paul Erd˝os to an extend that it is sometimes called the “Erd˝os method”.
[11]
[PDF] Chapter Combinatorics in Computer Science
It is not surprising that computer science is perhaps the most important eld of appli cations of combinatorial ideas Modern computers operate in a discrete ...
[12]
Brief Description of Combinatorics | LSU Math
Combinatorics is one of the oldest branches of mathematics. It has been influenced by almost all areas of mathematics, including number theory, algebra, ...
[13]
Combinatorics-based approaches to controllability characterization ...
Combinatorics-based approaches to controllability characterization for bilinear systems ... applications across science and engineering disciplines. Although much ...<|separator|>
[14]
[PDF] An Introduction to Combinatorics and Graph Theory - Whitman College
Combinatorics is about combining things, including counting, while graph theory is about networks or models of networks called graphs.
[15]
Combinatorics Group - Department of Mathematics - UF Math
In particular, combinatorics is often interested in the existence, construction, enumeration, and/or optimization of certain types of finite structures.
[16]
[PDF] M362K Probability Homework Solutions Homework 1: Due ...
However, this is counting every handshake twice, once from the perspective of each person, so the answer is half that, or 190 = 20. 2 . Problem 21. You take ...
[17]
[PDF] 4 Combinatorics and Probability - Stanford InfoLab
Combinatorics is the science of counting, and probability theory measures the likelihood of events. This chapter introduces these two fields.
[18]
Combinatorics and Graph Theory | West Virginia University
Jan 28, 2025 · Combinatorics is an area of mathematics mainly concerned with counting and properties of discrete structures. Both have applications in computer science, data ...
[19]
Application of Combinatorial Optimization in Logistics - IEEE Xplore
Abstract: Combinatorial optimization problems are becoming more and more important as its applications take place in many aspects, especially in logistics ...
[20]
[PDF] Combinatorial optimization in production and logistics systems
It is widely acknowledged that planning, scheduling and transport logistics play a vital role in the competitiveness of organizations by producing and ...
[21]
Combinatorial optimization in transportation and logistics networks
Jan 1, 2013 · This chapter is designed so as to introduce the reader in the notions tackled by important problems in transportation and logistics engineering ...
[22]
4: Probability and Combinatorics - Statistics LibreTexts
Jun 21, 2024 · Key rules include the complement rule, stating that the probability of an event not occurring is 1 minus the probability that it does occur.
[23]
IEEE BITS Special Issue on Error-Correcting Codes
Apr 14, 2025 · The interplay between coding, theoretical computer science, and combinatorics; Error-correcting codes and cryptography; Coding for signal ...
[24]
Combinatorial pattern discovery for scientific data - ACM Digital Library
This paper presents an example of combinatorial pattern discovery: the discovery of patterns in protein databases. The structural representation we consider are ...
[25]
Finding Combinatorial Patterns in Real Valued Omics Data
Apr 18, 2024 · In this dissertation, we employ combinatorial optimization techniques to improve upon three steps in the precision medicine analysis pipeline.
[26]
[PDF] NSF AI+MPS Workshop - 03 - Domain Overviews.pdf - Indico
Mar 26, 2025 · as theorem prover co-pilots like Lean and SAT solvers. ○. Combinatorics: Transformer models have been used for finding geometric combinatorial ...
[27]
A Distributed Combinatorial Topology Approach to Arrow's ...
Jul 21, 2022 · We present here a novel combinatorial topology approach that does not use advanced mathematics, while giving a geometric intuition of the ...
[28]
Nine chapters - MacTutor History of Mathematics
The Jiuzhang suanshu or Nine Chapters on the Mathematical Art is a practical handbook of mathematics consisting of 246 problems intended to provide methods ...
[29]
The Archimedean Cattle problem - MacTutor - University of St Andrews
This ancient problem is a Diophantine equation (i.e. an equation with integer solutions) which can be posed as follows. The sun-god had a herd of cattle ...
[30]
[PDF] Pingala and the Beginnings of Combinatorics in India - IISc Math
It has been claimed that Pingala's lists show an awareness of binary numbers. As given above, neither choice l = 0, g = 1 or g = 0, l = 1 turns a list into ...
[31]
The binomial theorem: A widespread concept in medieval Islamic ...
While the binomial theorem is presumed to have been discovered by al-Karaj i (ca. 1029) and utilized by several subsequent mathematicians, the elaboration of ...
[32]
al-Karaji (953 - 1029) - Biography - MacTutor History of Mathematics
Al-Karaji was an Islamic mathematician who wrote about the work of earlier mathematicians ... binomial theorem, the binomial coefficients and the Pascal triangle.
[33]
Yang Hui (1238 - 1298) - Biography - MacTutor History of Mathematics
In 1261 Yang wrote the Xiangjie jiuzhang suanfa (Detailed analysis of the mathematical rules in the Nine Chapters and their reclassifications). He tells us that ...
[34]
Blaise Pascal - Biography - MacTutor - University of St Andrews
Blaise Pascal was a very influential French mathematician and philosopher who contributed to many areas of mathematics. He worked on conic sections and ...Missing: Ars Mogica 1666 combinatorics
[35]
Blaise Pascal Math - The Story of Mathematics
Blaise Pascal was a prominent 17th Century scientist, philosopher and mathematician. Like so many great mathematicians, he was a child prodigy.Missing: Ars Mogica 1666 combinatorics
[36]
De Arte Combinatoria | work by Leibniz - Britannica
Oct 22, 2025 · In Gottfried Wilhelm Leibniz: Early life and education. ” In 1666 he wrote De Arte Combinatoria (“On the Art of Combination”), ...
[37]
Königsberg bridge problem | Mathematics, Graph Theory & Network ...
Sep 27, 2025 · The history of graph theory may be specifically traced to 1735, when the Swiss mathematician Leonhard Euler solved the Königsberg bridge problem ...
[38]
[PDF] 8. PARTITIONS George E. Andrews
The history of partitions is filled with starts and stops. Euler's ... Alder, Partition identities – from Euler to the present, Amer. Math. Monthly ...
[39]
A brief history of partitions of numbers, partition functions and their ...
Aug 5, 2015 · This is followed by Euler's new discovery of the additive number theory based on partitions of numbers. Special attention is given to many ...
[40]
On sets of integers containing k elements in arithmetic progression
Szemerédi, E.. "On sets of integers containing k elements in arithmetic progression." Acta Arithmetica 27.1 (1975): 199-245.Missing: original | Show results with:original
[41]
[PDF] PROCEEDINGS INTERNATIONAL CONGRESS MATHEMATICIANS
The central theme for the Conference in Algebra was the Theory of Rings. Because of the complexities of programming, the session on Algebraic Geometry.
[42]
[PDF] Algorithmic Combinatorial Game Theory - Erik Demaine
Nonetheless, the Sprague-Grundy theory is extremely helpful for analyzing impartial two-player games, and for many games there is an efficient algorithm to ...
[43]
Quantum annealing for combinatorial optimization: a benchmarking ...
May 16, 2025 · Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems.
[44]
The asymptotics of r(4,t) | Combinatorics and more
Jun 9, 2023 · Sam Mattheus wrote on his blog “Points and Lines” a summary with a general overview of the proof for his breakthrough with Jacques ...
[45]
[PDF] Applied Combinatorics - William T. Trotter
Feb 15, 2015 · The principle of inclusion-exclusion is not the only approach available for counting derangements. We know that d1 = 0 and d2 = 1. Using ...<|control11|><|separator|>
[46]
[PDF] Combinatorics: The Art of Counting - Michigan State University
Sep 21, 2020 · This book covers basic counting, permutations, combinations, set partitions, integer partitions, graphs, trees, and lattice paths.
[47]
[PDF] Basic Combinatorics - UTK Math
Basic combinatorics covers Fibonacci numbers, functions, sequences, words, distributions, multisets, sets, and useful counting strategies.
[48]
[PDF] Counting - 61DM Handout
The Fibonacci sequence F1 = 1,F2 = 1,F3 = 2,F4 = 3,F5 = 5,F6 = 8,F7 = 13,F8 = 21,F9 = 34,... satisfies the linear homogeneous recurrence relation Fn+2 = Fn+1 + ...
[49]
[PDF] generatingfunctionology - Penn Math
May 21, 1992 · This book is about generating functions and some of their uses in discrete mathematics. The subject is so vast that I have not attempted to give ...
[50]
[PDF] Ordinary Generating Functions - UCSD Math
We'll begin this chapter by introducing the notion of ordinary generating functions and discussing the basic techniques for manipulating them.
[51]
The Story of the Binomial Theorem - jstor
Various mathematicians have suggested that the. Chinese could expand binomials to quite high powers. The first writer to give us something really solid is ...
[52]
Close encounters with the Stirling numbers of the second kind - arXiv
Jun 22, 2018 · We tell the story of their birth in the book of James Stirling (1730) and show how they mature in the works of Johann Grunert (1843).<|control11|><|separator|>
[53]
[PDF] Four Proofs of the Ballot Theorem 1
the theorem tells us that if all ballot permutations are equally likely, then the probability of a good permutation occurring is (a − kb)/(a + b). In 1887 ...
[54]
[PDF] Introduction to Graph Theory
This result, due essentially to Leonhard Euler in 1736, is called the handshaking lemma. It implies that if several people shake hands, then the total ...Missing: URL | Show results with:URL
[55]
The collected mathematical papers of Arthur Cayley - Internet Archive
Nov 5, 2007 · The collected mathematical papers of Arthur Cayley. by: Cayley, Arthur, 1821-1895; Forsyth, Andrew Russell, 1858-1942. Publication date: 1889-97.
[56]
Twenty-one Proofs of Euler's Formula - UC Irvine
The formula V − E + F = 2 was (re)discovered by Euler; he wrote about it twice in 1750, and in 1752 published the result, with a faulty proof by induction for ...
[57]
[PDF] Steiner systems S(2,4,v) - a survey
Jan 21, 2009 · A Steiner system S(t, k, v) is a pair (V, B) where V is a v-element set and B is a family of k-element subsets of V called blocks such that ...
[58]
On the construction of balanced incomplete block designs
Bose. RC and Fisher, RA 1939. On the construction of balanced incomplete block designs. Annals of Eugenics. 9 (4), pp. 353-399.
[59]
Fano Plane -- from Wolfram MathWorld
The Fano plane is the configuration consisting of the two-dimensional finite projective plane the Galois field of order 2 GF(2).Missing: source | Show results with:source<|control11|><|separator|>
[60]
Kirkman's Schoolgirl Problem -- from Wolfram MathWorld
In a boarding school there are fifteen schoolgirls who always take their daily walks in rows of threes. How can it be arranged so that each schoolgirl walks ...
[61]
Projective Plane -- from Wolfram MathWorld
A projective plane can be constructed by gluing both pairs of opposite edges of a rectangle together giving both pairs a half-twist. It is a one-sided surface, ...
[62]
[PDF] Fisher, Statistics, and Randomization - University of Cambridge
Apr 22, 2022 · Intuitively, a more “balanced” design—assigning treatments equally often in each block—should be favoured. Fisher showed that blocking ...
[63]
https://mathworld.wolfram.com/ProjectivePlane.html
[64]
[PDF] Some remarks on the theory of graphs
The present note consists of some remarks on graphs. A graph G is a set of points some of which are connected by edges. We assume here that no two points are ...
[65]
[PDF] 6 Lovász Local Lemma - Yufei Zhao
The Lovász local lemma (LLL) was introduced in the paper of Erdős and Lovász · (1975). It is a powerful tool in the probabilistic method.
[66]
[PDF] EXTREMAL GRAPH THEORY 1 Turán's theorem
Theorem 1.2 guarantees the existence of a complete (r − 1)-partite graph H such that either H = G or else G has fewer edges than H. In particular, if G has the ...
[67]
[PDF] ON A PROBLEM OF K. ZARANKIEWICZ
We restrict ourselves here to the original problem of Zarankiewicz; nevertheless we shall treat in Section 7 the case n₁-p(p+1), n, p,i-ja-2 (p prime), in which ...
[68]
A Study on a Probabilistic Method for Designing Artificial Neural ...
Jan 1, 2023 · This article is devoted to the study of the possibility of using a method for the probabilistic formation of neural network structures developed by the authors.
[69]
Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und ...
Download PDF ... Cite this article. Pólya, G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68, 145–254 (1937).
[70]
Pólya's Counting Theorem Via Tensors - jstor
A very general and elegant theorem due to G. Polyal supplies the answer. In order to state Polya's result, we must first define the cycle index of a permutation ...
[71]
Combinatorics and Commutative Algebra - SpringerLink
The second topic deals with the face ring of a simplicial complex, and includes a proof of the Upper Bound Conjecture for Spheres. An introductory chapter ...
[72]
Sur le problème des courbes gauches en Topologie - EuDML
Kuratowski, Casimir. "Sur le problème des courbes gauches en Topologie." Fundamenta Mathematicae 15.1 (1930): 271-283. <http://eudml.org/doc/212352> ...
[73]
Crossing Numbers of Graphs | Marcus Schaefer
Jan 2, 2018 · The book presents a wide variety of ideas and techniques in topological graph theory, discrete geometry, and computer science. The first part of ...
[74]
Differentiable Mapper For Topological Optimization Of Data ... - arXiv
Feb 20, 2024 · In this work, we build on a recently proposed optimization framework incorporating topology to provide the first filter optimization scheme for Mapper graphs.Missing: advances | Show results with:advances
[75]
[PDF] Axel Thue's papers on repetitions in words: a translation
Jul 21, 1994 · Thue, Uber unendliche Zeichenreihen, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana 1906, Nr. 7. Page 82. [47] A. Thue, Die L ...
[76]
[PDF] Decision algorithms for Fibonacci-automatic Words, I: Basic results
The prototypical example of an automatic sequence is the Thue-Morse sequence t = t0t1t2 ..., the fixed point (starting with 0) of the morphism. 0 → 01, 1 → 10.
[77]
Über Kongruenz x ... (mod. p.). - EUDML
Schur, I.. "Über Kongruenz x ... (mod. p.).." Jahresbericht der Deutschen Mathematiker-Vereinigung 25 (1917): 114-116. <http://eudml.org/doc/145475>.Missing: pdf | Show results with:pdf
[78]
On Certain Sets of Integers - London Mathematical Society (LMS)
This paper, 'On Certain Sets of Integers', by K.F. Roth, was published in the Journal of the London Mathematical Society in January 1953.
[79]
AMS :: Proceedings of the American Mathematical Society
B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212-216. Similar Articles. Retrieve articles in Proceedings of the ...
[80]
[PDF] A partition calculus in set theory
Part of this paper was material from an address delivered by P. Erdös under the title Combinatorial problems in set theory before the New York meeting of the ...
[81]
[PDF] arXiv:1411.5874v3 [math.LO] 3 Sep 2016
Sep 3, 2016 · König's lemma states that every infinite, finitely branching tree has an infinite path. The corresponding problem is thus that of finding an ...Missing: source | Show results with:source
[82]
[PDF] ON A PBOBLEM OF FOKMAL LOGIC This paper is primarily ...
This paper is primarily concerned with a special case of one of the leading problems of mathematical logic, the problem of finding a regular.
[83]
[PDF] On the Abstract Properties of Linear Dependence - GRAAL
Author(s): Hassler Whitney. Source: American Journal of Mathematics, Vol. 57, No. 3 (Jul., 1935), pp. 509-533. Published by: The Johns Hopkins University ...
[84]
[PDF] What is a matroid? - LSU Math
It was noted earlier that graph theory played an important role in moti- vating Whitney's founding paper in matroid theory and we show next how matroids arise ...
[85]
An Automatic Method of Solving Discrete Programming Problems
10 This is an upper bound to the branch value of y which has been obtained by ignoring the fact that Y2 would be negative at this point. The true branch value ...
[86]
[PDF] maximal flow through a network - lr ford, jr. and dr fulkerson
399 Page 2 400 L. R. FORD, JR. AND D. R. FULKERSON a saturated arc. The value of a flow is the sum of the numbers of all the chain flows which compose it.
[87]
[1411.4028] A Quantum Approximate Optimization Algorithm - arXiv
Nov 14, 2014 · Authors:Edward Farhi, Jeffrey Goldstone, Sam Gutmann. View a PDF of the paper titled A Quantum Approximate Optimization Algorithm, by Edward ...Missing: Shor | Show results with:Shor
[88]
Quantum approximate multi-objective optimization - Nature
Oct 24, 2025 · This eliminates the need to train QAOA parameters on a quantum computer and removes a computational bottleneck for the considered problems.
[89]
Universal classes of hash functions (Extended Abstract)
This paper gives an input independent average linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function.
[90]
[PDF] Conflict-Driven Clause Learning SAT Solvers - cs.Princeton
Besides using DPLL, building a state-of-the-art CDCL SAT solver involves a number of additional key techniques: • Learning new clauses from conflicts during ...<|control11|><|separator|>
[91]
Neural Architecture Search via Combinatorial Multi-Armed Bandit
Jan 1, 2021 · In this paper, we formulate NAS as a Combinatorial Multi-Armed Bandit (CMAB) problem (CMAB-NAS). This allows the decomposition of a large search space into ...Missing: enumeration | Show results with:enumeration
[92]
[PDF] Five lectures on statistical physics methods in combinatorics
The partition function of the hard-core model, ZG(λ), is also known as the indepen- dence polynomial in combinatorics. ZG(λ) encodes a lot of combinatorial ...
[93]
[quant-ph/9705052] Stabilizer Codes and Quantum Error Correction
May 28, 1997 · Access Paper: View a PDF of the paper titled Stabilizer Codes and Quantum Error Correction, by Daniel Gottesman. View PDF · TeX Source · view ...Missing: original | Show results with:original
[94]
Why are de Bruijn graphs useful for genome assembly? - PMC - NIH
De Bruijn graphs were first brought to bioinformatics in 1989 as a method to assemble k-mers generated by SBH; this method is very similar to the key ...
[95]
Press release: The Nobel Prize in Physics 2023 - NobelPrize.org
Oct 3, 2023 · Attosecond pulses can also be used to identify different molecules, such as in medical diagnostics. Illustrations. The illustrations are free ...