Please enable JavaScript.

Coggle requires JavaScript to display documents.

Combinatorics, Definition (Bistochastic and permutation matrices): A real…

- - - - Definition: A path in the above sense is called saturated (with respect to a given flow \( f \)) if for some edge \( e_i = (v_{i-1}, v_i) \) oriented in the forward direction we have \( f(e_i) = c(e_i) \), or for some edge \( e_i = (v_i, v_{i-1}) \) oriented in the backward direction we have \( f(e_i) = 0 \). A path that is not saturated is called unsaturated. Unsaturated paths from the source to the sink are also often called augmenting paths. A flow \(f\) is called saturated if every path from source to target is saturated.
        
        Proposition: A flow is maximum if and only if it is saturated. For every maximum flow \( f \) there exists a cut \( R \) such that \( w(f) = c(R) \).
        
        Algorithm (Ford–Fulkerson): Set \( f(e) = 0 \) for all edges \( e \). While there exists an augmenting path \( P \), determine \( \varepsilon_P \) as in the proof of the previous theorem, augment the flow along \( P \), and repeat this step as long as an unsaturated path exists. The resulting flow \( f \) is a maximum flow.
      - Proposition: For every flow \( f \) and every cut \( R \), we have \( w(f) \leq c(R) \). Hence the maximum flow is at most equal to the minimum cut.
- - - - implies
    - - Lemma (Faces of drawings of 2-connected graphs): Let \( G \) be a planar 2-vertex-connected graph. Then the boundary of every face in every planar drawing of \( G \) is a (graph) cycle in \( G \).
        
        uses
    - - uses
- - - - direct consequence
        
        Theorem: For every planar graph G, \( |E(G)| \le 3|V(G)| - 6 \). Hence every planar graph contains a vertex of degree at most 5.
      - uses for proof
    - - Theorem (Kuratowski): A graph is planar if and only if it does not contain a subdivision of \( K_5 \), nor of \( K_{3,3} \). (You should only have seen the proof of the “only if” part of the theorem so far. We will do the “if” part in this course.)
    - - uses
  - - - Corollary: For every graph \( G \), \( |E(G)| \le 3|V(G)| + 6(g(G) - 1) \).
        
        uses for proof
- - - - Definition (Vizing classes): A graph \( G \) is called Vizing class 1 if \( \chi'(G) = \Delta(G) \), and it is called Vizing class 2 otherwise (i.e., if \( \chi'(G) = \Delta(G) + 1 \)).
        
        Theorem (Holyer): It is NP-complete to decide if a graph is Vizing class 1. In particular, it is NP-complete to decide if \( \chi'(G) = 3 \) for a cubic graph \( G \).
- - - - Observation: SDRs for \( M \) are in 1-1 correspondence with matchings of size \( |I| \) in \( B_M \). (See below if you need to refresh the definition of a matching.)
        
        Theorem (Hall): A set system \( M = { \bigcup }_{i \in I} M_i \) has an SDR if and only if \( \forall J \subseteq I, \, \big|\bigcup_{j \in J} M_j\big| \ge |J| \).
        
        implies by proof
        
        implies
        
        one of the proofs uses (HC)
        
        Theorem (Birkhoff): Every bistochastic matrix is a convex combination of permutation matrices. Thus, the set of bistochastic matrices (of the same order) is equal to the convex hull of permutation matrices of that same order.
  - - - implies
        
        Theorem: For every matrix, the maximum size of an independent set equals the minimum number
        of lines that contain all non-zero elemets.
    - - direct use
    - - Lemma: A matching \( M \) in a graph \( G \) is maximum if and only if there are no augmenting paths with respect to \( M \).
        
        uses for proof
        
        uses for proof
    - - implies
        
        Theorem (Petersen): Every bridgeless cubic graph contains a perfect matching.
    - - Lemma: Let \( M \) be a matching in a graph \( G = (V, E) \) and let \( C \subseteq G \) be a blossom with respect to \( M \). Let \( G' \) be the graph obtained from \( G \) by contracting the cycle into one vertex, and let \( M' = M \setminus E(C) \). Then \( M \) is a maximum matching in \( G \) if and only if \( M' \) is a maximum matching in \( G' \).
        
        Lemma (Edmonds forest properties): Let \( H \) be an Edmonds forest with vertex set \( W \). Then \( W_0 \) contains all free vertices of \( G \), no edge of \( G \) between \( W \) and \( V \setminus W \) belongs to \( M \), the vertices in \( V \setminus W \) are perfectly matched by \( M \cap \binom{V \setminus W}{2} \), and edges between \( W \) and \( V \setminus W \) start in odd levels of \( H \).
        
        Theorem: Edmonds Matching Algorithm answers correctly if M is a maximum matching in G, and it runs in time polynomial in the size of G.
- - - - Definition: Let \( \mathrm{MOLS}(n) \) denote the maximum number of pairwise orthogonal Latin squares of order \( n \).
        
        Theorem: For every \( n > 1 \), \( \mathrm{MOLS}(n) \le n - 1 \).
        
        Theorem: For every \( k \ge 0 \), \( \mathrm{MOLS}(12k + 10) \ge 2 \).
      - Definition (Orthogonal array): An orthogonal array of order \( n \) and depth \( d \) (OA(n,d)) is a matrix \( M \in {1, \dots, n}^{d \times n} \) such that for all \( 1 \le i < j \le d \) and all \( x, y \in {1, \dots, n} \), there exists a unique \( k \) with \( M_{i,k} = x \) and \( M_{j,k} = y \).
        
        Observation: An OA(n,d) exists if and only if \( \mathrm{MOLS}(n) \ge d-2 \).
        
        Theorem: If OA(n_1,d) and OA(n_2,d) exist, then OA(n_1 n_2,d) exists as well.
        
        Theorem: Let \( n = p_1^{r_1} p_2^{r_2} \cdots p_k^{r_k} \) be the decomposition of \( n \) into powers of distinct primes. Then \( \mathrm{MOLS}(n) \ge \min_{1 \le i \le k} { p_i^{r_i} - 1 } \).
        
        Corollary: If \( n > 2 \) and \( n \not\equiv 2 \pmod{4} \), then \( \mathrm{MOLS}(n) \ge 2 \).
- - - - Theorem: For every graph \( G \), it holds that \( \chi(G) \leq \operatorname{ch}(G) \leq \chi(G) + 1 \).
      - Definition (d-degenerate graph): A graph \( G \) is called d-degenerate if \( G \) and every subgraph \( G' \) of \( G \) satisfy \( \chi(G') \le d \). Moreover, for every d-degenerate graph \( G \), it holds that \( \operatorname{ch}(G) \le d + 1 \).
      - Theorem: If \( G \) is a planar outer-triangulation and \( L \) is a list assignment such that (i) \( |L(u)| = |L(v)| = 1 \) for two adjacent vertices \( u, v \) on the boundary of the outerface with \( L(u) \neq L(v) \), (ii) \( |L(x)| = 3 \) for all other vertices \( x \) on the boundary of the outerface, and (iii) \( |L(y)| = 5 \) for all inner vertices \( y \), then \( G \) is \( L \)-list-colorable.
        
        implies
        
        Theorem (Thomassen): For every planar graph \( G \), it holds that \( \operatorname{ch}(G) \le 5 \).
      - Theorem (Voigt): There exists a planar graph \( G \) such that \( \operatorname{ch}(G) > 4 \).
      - Theorem: If \( G \) is a planar triangle-free graph, then \( \operatorname{ch}(G) \le 4 \).
      - Theorem: If \( G \) is a planar bipartite graph, then \( \operatorname{ch}(G) \le 3 \).
  - - - uses
- - - - implies
        
        Theorem (Ore): Let \( G \) be a graph with \( |V(G)| \ge 3 \) such that \( \deg(u) + \deg(v) \ge |V(G)| \) for any two distinct nonadjacent vertices \( u, v \in V(G) \). Then \( G \) is Hamiltonian.
        
        implies
        
        Theorem (Dirac): Let \( G \) be a graph with \( |V(G)| \ge 3 \) and \( \delta(G) \ge \frac{|V(G)|}{2} \). Then \( G \) is Hamiltonian.
  - - - implies
        
        Theorem (Smith): Every edge of a cubic graph belongs to an even number of Hamiltonian cycles.
- - - - Corollary: If a (v,k,\( \lambda \))-BIBD exists, then \( (v-1) \) is divisible by \( k-1 \), \( v(v-1) \) is divisible by \( k(k-1) \), and \( r > \lambda \).
      - Proposition: If \( (V, B) \) is a symmetric (v,k,\( \lambda \))-BIBD, then \( r = \lambda \frac{v-1}{k-1} = k \) and hence \( k(k-1) = \lambda (v-1) \) (since \( rv = |B|k = vk \)).
    - - Corollary: If a (v,k,\( \lambda \))-BIBD exists, then \( k \le r = \lambda \frac{v-1}{k-1} \).
    - - Theorem: Let \( (V, B) \) be a set system with \( |B| = |V| > 1 \) and let \( A \) be its incidence matrix. (1) If \( (V, B) \) is a symmetric (v,k,\( \lambda \))-BIBD, then (a) \( AA^T = (k-\lambda)I + \lambda J \), (b) \( A^T A = (k-\lambda)I + \lambda J \), (c) \( AJ = kJ \), (d) \( JA = kJ \), (e) \( A \) is regular. (2) If \( A \) is regular and (a) or (b) holds, then \( (V, B) \) is a symmetric (v,k,\( \lambda \))-BIBD (so all (a)-(e) hold).
        
        Corollary (Dual design): If \( (V, B) \) is a symmetric (v,k,\( \lambda \))-BIBD, then the system \( (B, V^*) \) with \( V^* = { v^* : v \in V }, v^* = { B \in B : v \in B } \) is also a symmetric (v,k,\( \lambda \))-BIBD. It is called the dual design of \( (V, B) \).
      - Theorem (Bruck-Ryser-Chowla): Let v,k,\( \lambda \) be parameters of a symmetric (v,k,\( \lambda \))-BIBD and let \( n = k - \lambda \). Then either (1) v is even and n is a perfect square, or (2) v is odd and the Diophantine equation \( z^2 = n x^2 + \lambda \frac{v-1}{2} y^2 \) has a nontrivial integer solution.
        
        Corollary: A finite projective plane of order 6 does not exist.
  - - - Proposition: If \(STS(v_1)\) and \(STS(v_2)\) exist, then an \(STS(v_1 v_2) \)exists as well.
  - - - Corollary: For every \(D = (V, \mathcal{B})\) a \((v,k,\lambda)\)-BIBD \(G_D\) is Hamiltonian.
- - - - Conjecture (Hadamard): Hadamard matrices exist for all \( m \) divisible by 4.
    - - Corollary (Sylvester): Hadamard matrices of order \( 2^k \) exist for all positive integers \( k \).