Discrete Mathematics – Lecture Notes (Lovász & Vesztergombi, Yale 1999)

Vocabulary flashcards covering key concepts, definitions, and theorems from the lecture notes.

Set

A collection of elements. Notation: a set A has elements; a universe may contain many sets.

Cardinality

The number of elements in a set, denoted |A| (∞ is used for infinite sets like Z, R).

Subset

A set A is a subset of B if every element of A is also an element of B; written A ⊆ B.

Empty set

The set with no elements, denoted ∅; it is a subset of every set.

Power set

The set of all subsets of a given set A. If A has n elements, its power set has 2^n elements.

Union

The set of elements that are in A or B (A ∪ B).

Intersection

The set of elements common to A and B (A ∩ B).

Disjoint

Two sets with empty intersection, A ∩ B = ∅.

Binary encoding of subsets

Encode a subset by a binary string of length n where the i-th bit is 1 if the i-th element is in the subset, 0 otherwise.

Bijective correspondence

A one-to-one correspondence (a perfect pairing) between two sets; implies the sets have the same cardinality.

Two-to-one correspondence (bijective idea)

A one-to-one mapping between subsets and numbers (e.g., 0 to 2^n−1) used to count or enumerate.

2^n subsets theorem

A set with n elements has exactly 2^n subsets (Theorem 2.1).

Strings over an alphabet

Number of length-n strings from a k-letter alphabet is k^n (Theorem 2.2).

Permutation

An ordering of n distinct objects; number of permutations is n! (Theorem 2.4).

Factorial

n! denotes the product n·(n−1)·…·2·1; the number of ordered arrangements of n objects.

Stirling’s formula

Asymptotic: n! ∼ (n/e)^n · √(2πn); provides a good approximation for large n.

Binomial coefficient

Notation: C(n,k) = n!/(k!(n−k)!). Counts number of k-subsets of an n-element set.

Binomial Theorem

(x+y)^n = Σ_{k=0}^n C(n,k) x^{n−k} y^k; explains appearance of binomial coefficients.

Pascal’s Triangle

Triangular array of binomial coefficients with symmetry and recurrence C(n,k)=C(n−1,k−1)+C(n−1,k).

Sum of squares in a row identity

Sum of the squares of the binomial coefficients in row n equals C(2n,n).

Theorem 4.2 (k-subsets)

The number of k-subsets of an n-set is C(n,k) = n!/(k!(n−k)!).

Cayley’s Theorem

The number of labeled trees on n nodes is n^{n−2}.

Prüfer code

A bijection between labeled trees on n nodes and sequences of length n−2 over {0,…,n−1}; used to count and generate trees.

Planar code

A 0-1 sequence of length 2(n−1) encoding an unlabelled tree by walking around it; not unique but compact.

Rooted tree

A tree with a designated root; each node (except root) has exactly one parent (father).

Leaf

A node of degree 1 in a tree (except possibly the root if the tree has one node).

Tree

A connected acyclic graph. For a tree with n nodes, there are n−1 edges.

Spanning tree

A tree that connects all the vertices of a graph (subgraph with all vertices and no cycles).

Minimum spanning tree (MST)

A spanning tree of a weighted graph with minimum possible total edge weight.

Travelling Salesman Problem (TSP)

Find a minimum-cost cycle visiting every given vertex exactly once; MST-based 2-approximation exists.

Augmenting path

In a graph with a current matching M, a path starting and ending at unmatched vertices with edges alternating between non-M and M; flipping along it increases the size of M.

Perfect matching

A matching that covers every vertex of the graph.

Bipartite graph

Graph whose vertex set can be partitioned into A and B with edges only between A and B.

Hall’s Marriage Theorem

A bipartite graph has a perfect matching iff |A|=|B| and for every subset S⊆A, |N(S)|≥|S| (where N(S) is the neighborhood).

Algorithm for perfect matching

Augmenting-path algorithm: repeatedly find augmenting paths to enlarge a matching until it becomes perfect or impossible.

NP-property

A problem property for which a solution can be verified in polynomial time; many graph properties are NP.

Two-coloring (circle regions)

Regions formed by circles can be colored with two colors so adjacent regions have different colors (Theorem 13.1); a special case of planarity/coloring.

Prime number theorem

π(n) ∼ n/ln n; describes the asymptotic distribution of primes.

Twin primes

Pairs of primes that differ by 2 (e.g., (3,5), (11,13)); it is unknown whether infinitely many exist.

Fermat’s Little Theorem

If p is prime and a is an integer, then a^p ≡ a (mod p), i.e., p | (a^p − a).

GCD

Greatest common divisor gcd(a,b): the largest positive integer dividing both a and b.

LCM

Least common multiple lcm(a,b): the smallest positive integer that is a multiple of both a and b.

Euclidean algorithm

Efficient method to compute gcd(a,b) by repeated division with remainder.

Pseudoprime (Carmichael number)

Composite n such that a^n ≡ a (mod n) for many bases a; Carmichael numbers satisfy this for all a.

Prime number theorem (π(n))

π(n) counts primes ≤ n; asymptotically π(n) ∼ n/ln n.

Binary representation

Expressing numbers in base 2 with bits 0 and 1; used to encode subsets and compute digits.

Induction

A proof technique: base case holds; if the statement holds for n−1, it holds for n; conclude for all n.

Order of growth: n! vs 2^n

For large n, n! grows faster than 2^n; n! eventually dominates 2^n.

Answer key: 2 Let us count!

Count of seating arrangements uses factorial growth and combinatorial reasoning.