Editing Combinatorics and Graph Theory

<div style="background-color: #4B0082; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
{{BloomIntro}}
Combinatorics is the branch of mathematics that studies finite or countable discrete structures — the art of counting, arranging, and analyzing collections of objects. Graph theory, its close partner, studies networks of vertices and edges. Together they form the mathematical foundation of computer science, operations research, and network science. Combinatorics answers questions like: how many ways can we arrange n objects? How many paths exist through a network? Is there a perfect matching? How many colors does it take to color a map? These questions are elementary to state but can be extraordinarily deep to resolve, as Ramsey theory and the four-color theorem demonstrate.
</div>

__TOC__

<div style="background-color: #000080; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Remembering</span> ==
* '''Combinatorics''' — The branch of mathematics studying counting, arrangement, and structure in finite and discrete settings.
* '''Permutation''' — An ordered arrangement of objects; P(n,k) = n!/(n-k)! arrangements of k items from n.
* '''Combination''' — An unordered selection; C(n,k) = n!/[k!(n-k)!] = "n choose k"; denoted ⁿCₖ or C(n,k).
* '''Binomial coefficient''' — C(n,k); coefficients in the expansion of (a+b)^n (Pascal's triangle).
* '''Pigeonhole principle''' — If n+1 objects are placed in n boxes, at least one box contains ≥ 2 objects; powerful despite simplicity.
* '''Inclusion-exclusion principle''' — |A ∪ B| = |A| + |B| - |A ∩ B|; generalized to n sets.
* '''Generating function''' — A formal power series encoding a combinatorial sequence; used to solve recurrences.
* '''Graph''' — A set of vertices V and edges E ⊆ V×V; the central object of graph theory.
* '''Degree (graph)''' — The number of edges incident to a vertex; handshaking lemma: Σdeg(v) = 2|E|.
* '''Path''' — A sequence of distinct vertices connected by edges.
* '''Cycle''' — A path that starts and ends at the same vertex.
* '''Tree''' — A connected acyclic graph; n vertices and n-1 edges.
* '''Euler path/circuit''' — A path/circuit traversing each edge exactly once; exists iff 0 or 2 vertices have odd degree.
* '''Hamiltonian path/cycle''' — A path/cycle visiting each vertex exactly once; NP-complete to decide in general.
* '''Graph coloring''' — Assigning colors to vertices so adjacent vertices have different colors; chromatic number χ(G).
* '''Four Color Theorem''' — Every planar graph can be 4-colored; proved in 1976 by Appel & Haken using computer.
</div>

<div style="background-color: #006400; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Understanding</span> ==
Combinatorics operates through creative counting arguments; graph theory through structural analysis of networks:

**The power of generating functions**: Many combinatorial sequences satisfy recurrences. Generating functions convert recurrences into algebraic equations. The Fibonacci recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂ corresponds to the generating function F(x) = x/(1-x-x²), whose partial fraction decomposition gives the closed form Fₙ = (φⁿ - ψⁿ)/√5 where φ = (1+√5)/2 (the golden ratio). Generating functions are the "Swiss army knife" of combinatorics.

**Ramsey theory — structure in chaos**: Ramsey theory proves that any sufficiently large combinatorial structure must contain ordered sub-structures. R(3,3) = 6: among any 6 people, there must be 3 mutual acquaintances or 3 mutual strangers. Ramsey numbers R(s,t) are known only for small values; R(5,5) is unknown. The Graham-Rothschild theorem and Van der Waerden's theorem extend these ideas to arithmetic progressions.

**Graph theory's structural theorems**: Menger's theorem: the maximum number of vertex-disjoint paths between s and t equals the minimum vertex cut separating s and t — a "max-flow min-cut" for graphs. König's theorem: in bipartite graphs, the maximum matching equals the minimum vertex cover. The Erdős-Gallai theorem characterizes degree sequences of graphs. Kuratowski's theorem: a graph is planar iff it contains no subdivision of K₅ or K₃,₃.

**Algorithms and complexity in graph theory**: Many natural graph problems are NP-complete: Hamiltonian cycle, graph coloring (for k ≥ 3), maximum clique, maximum independent set. Others are polynomial: shortest paths (Dijkstra, Bellman-Ford), minimum spanning trees (Kruskal, Prim), maximum bipartite matching (Hopcroft-Karp), network flow (Ford-Fulkerson). This dichotomy between tractable and intractable graph problems is central to computational complexity.
</div>

<div style="background-color: #8B0000; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Applying</span> ==
'''Graph algorithms and combinatorial computations:'''
<syntaxhighlight lang="python">
import heapq
from collections import defaultdict, deque
from typing import Optional

# === Core Graph Representation ===
class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(dict)  # adj[u][v] = weight
        self.directed = directed
    
    def add_edge(self, u, v, weight=1):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight
    
    @property
    def vertices(self): return set(self.adj.keys())
    def degree(self, v): return len(self.adj[v])

# === Dijkstra's Shortest Path ===
def dijkstra(graph: Graph, source) -> dict:
    """Shortest paths from source to all vertices. O((V+E) log V)."""
    dist = {v: float('inf') for v in graph.vertices}
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph.adj[u].items():
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# === Kruskal's Minimum Spanning Tree ===
class UnionFind:
    def __init__(self, n): self.parent = list(range(n)); self.rank = [0]*n
    def find(self, x):
        while self.parent[x] != x: x = self.parent[x] = self.parent[self.parent[x]]
        return x
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

def kruskal_mst(n: int, edges: list) -> tuple[list, float]:
    """Minimum spanning tree. edges = [(weight, u, v)]. O(E log E)."""
    edges = sorted(edges)
    uf = UnionFind(n)
    mst, total = [], 0
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w)); total += w
    return mst, total

# === Graph Coloring (Greedy) ===
def greedy_coloring(graph: Graph) -> dict:
    """Greedy vertex coloring. Not necessarily optimal, but fast."""
    color = {}
    for v in sorted(graph.vertices, key=lambda x: -graph.degree(x)):  # Largest first
        neighbor_colors = {color[u] for u in graph.adj[v] if u in color}
        for c in range(len(graph.vertices)):
            if c not in neighbor_colors:
                color[v] = c; break
    return color  # Chromatic number ≤ max_color + 1

# === Combinatorics ===
from math import comb, factorial

def binomial_coefficient(n: int, k: int) -> int: return comb(n, k)

def count_permutations(n: int, k: int) -> int:
    """P(n,k) = n!/(n-k)!"""
    return factorial(n) // factorial(n - k)

def inclusion_exclusion_union(*sets) -> int:
    """Count |A₁ ∪ A₂ ∪ ... ∪ Aₙ| using inclusion-exclusion."""
    from itertools import combinations
    n = len(sets)
    total = 0
    for r in range(1, n + 1):
        for combo in combinations(range(n), r):
            intersection = set.intersection(*[sets[i] for i in combo])
            total += ((-1)**(r+1)) * len(intersection)
    return total

# Pigeonhole: demonstrate that in any 13 people, 2 share a birth month
print(f"Pigeonhole: 13 people, 12 months → {13 // 12 + 1} guaranteed to share a month")
print(f"C(52,5) = {comb(52,5):,} possible poker hands")
print(f"Permutations of 8 queens on 8 columns: {count_permutations(8,8):,}")
</syntaxhighlight>

; Key results and open problems
: '''Graph theory''' → Four Color Theorem · Euler/Hamilton path conditions · Menger's theorem · Ramsey theory
: '''Extremal combinatorics''' → Turán's theorem · Szemerédi regularity lemma · Green-Tao theorem
: '''Enumerative combinatorics''' → Catalan numbers · Stirling numbers · Polya enumeration
: '''Open problems''' → R(5,5) unknown · Hadwiger conjecture · Graceful tree conjecture
</div>

<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Analyzing</span> ==
{| class="wikitable"
|+ Classical Combinatorial Results
! Result !! Statement !! Application
|-
| Pigeonhole Principle || n+1 objects in n boxes → repeat || Birthday paradox; hash collisions; proofs
|-
| Binomial Theorem || (a+b)^n = Σ C(n,k) a^k b^{n-k} || Probability; algebra; generating functions
|-
| Ramsey R(3,3)=6 || 6 people → 3 friends or 3 strangers || Guaranteed structure in large structures
|-
| Four Color Theorem || Every planar map 4-colorable || Map coloring; register allocation in compilers
|-
| Erdős-Rényi ER(n,p) || Phase transition at p=1/n || Random graph theory; network models
|}

'''NP-complete graph problems''': Graph 3-coloring, Hamiltonian cycle, Maximum clique, Vertex cover, Independent set, Subgraph isomorphism. These are all equivalent in hardness (polynomial-time reducible to one another) and are NP-complete — unlikely to have efficient algorithms.
</div>

<div style="background-color: #483D8B; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Evaluating</span> ==
Combinatorial results are assessed by: (1) **Exactness**: does the formula give a precise count or bound? (2) **Tightness**: are the bounds achievable? (3) **Generalizability**: does the result extend to other structures? (4) **Algorithmic efficiency**: can the combinatorial structure be computed or searched efficiently? (5) **Connection to other areas**: does the result reveal connections to algebra, probability, or geometry?
</div>

<div style="background-color: #2F4F4F; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
== <span style="color: #FFFFFF;">Creating</span> ==
Advanced directions in combinatorics and graph theory: (1) **Probabilistic method** (Erdős): prove existence of combinatorial structures by showing a random construction has the desired property with positive probability — no explicit construction needed. (2) **Spectral graph theory**: study graphs through eigenvalues of adjacency and Laplacian matrices; reveals connectivity, expansion, and random walk behavior. (3) **Extremal graph theory**: Turán-type problems: how many edges can a graph have without containing a given subgraph? (4) **Algebraic combinatorics**: symmetric functions, representation theory of Sₙ, Young tableaux. (5) **Network science applications**: community detection, influence maximization, epidemics on networks — graph theory meets data science.

[[Category:Mathematics]]
[[Category:Combinatorics]]
[[Category:Graph Theory]]
</div>