Finite Playground

Three group-unrelated representation theorems

A representation theorem in general means a canonical way of expressing a class of objects using another class of objects, usually more fundamental or easier to grasp.  Beside the well-known group representation theory, which concerns about viewing (finite or Lie) groups as matrices, here are three lesser known (to me!) representation theorems.

Birkhoff’s Representation Theorem.  Every distributive lattice is isomorphic to a sublattice of the power set lattice of some set.

Riesz–Markov–Kakutani Representation Theorem.  Any positive linear functional on the space of compactly supported continuous functions on a locally compact Hausdorff space can be viewed as integration against a measure.

Kapovich-Millson Universality Theorem.  Any compact smooth manifold is diffeomorphic to a component of the configuration space of some planar linkage.

Random stuff, 2016-01-08

Doing some random readings, also trying to revive the blog :(

• Conjecture [Thomas].  For any t, any sufficiently large t-connected graph with no $K_t$-minor can be made planar by removing exactly t-5 vertices.
The case when t=6 has been proven. [Kawarabayashi-Norine-Thomas-Wollan ’12]
• In a subgraph-closed graph family, having polynomial expansion is equivalent to having sublinear separator.  [Dvořák-Norine ’15]
• Richter-Thomassen Conjecture, now Pach-Rubin-Tardos Theorem, states that the total number of intersections between n pairwise intersecting Jordan curves in the plane, no three pass through the same point, is at least $(1-o(1))n^2$.
Main Theorem [Pach-Rubin-Tardos ’15].  Consider the above set of Jordan curves.  Then the number of crossing points is $\Omega(\log\log n)^{1/8}$ times the number of touching points, those that are the only intersection between two Jordan curves.
• Further results on arc and bar k-visibility graphs by Sawhney and Weed, 2016.
• Minimum cut of directed planar graphs in O(n log log n) time by Mozes, Nikolaev, Nussbaum, and Weimann, 2015.
• The weakly simple polygon result has been extended to geometric intersection numbers. [Despré-Lazarus ’15]

Perfect matching equivalence

There are so many things can be written…

Anyway, the following observation is really interesting; details can be found in the book “matching theory” by Lovasz and Plummer.

Consider a general graph $G$.  An equivalence relationship can be defined on the nodes of the graph as follows: two nodes $x$ and $y$ are equivalent if $G-x-y$ has no perfect matching(!).

Hindman’s Theorem

While reading the posts on ultrafilters by Terry Tao [1,2], I find the following result interesting:

Hindman’s theorem (a special case).  Suppose we color the natural numbers using k colors.  Then there exists a color c and an infinite set S, all colored with c, such that every finite sum of over S has color c as well.

Also, this theorem is claimed to be rather unpleasant to prove if we insist on not using ultrafilters.

Compilation of basic results related to regular language

* Results related to Pumping Lemma

Theorem.  A language $L$ accepted by a DFA $A$ of $n$ states is

1. nonempty if and only if $A$ accepts a sentence of length less lean $n$.
2. infinite if and only if $A$ accepts a sentence of length $\ell$ with $n \le \ell < 2n$.

The union of the following languages, $L_1 \cup L_2$, is non-regular, but nevertheless it cannot be proven using pumping lemma.

$L_1 = \{u_1 v_1 w v_2 u_2 : u_1,u_2,v_1,v_2,w \in [4]^*,$ and either $v_1=w$, $v_1=w$, or $v_2=v_2\}$

$L_2 = \{w : w\in [4]^*,$ and precisely $1/7$ of symbols in $w$ are 3’s $\}$

* Regular languages are precisely constant-space languages

Theorem.  A regular language can be recognized by a two-way read-only Turing machine.

Proof sketch.  Record the configuration of each time we first visit the $i$-th cell.  Define a finite automaton to simulate the same behavior.

Theorem.  $\textsc{Space}(o(\log\log n))$ is the same as $\textsc{Space}(1)$, both are the class of regular languages.  That is, having an algorithm that uses $o(\log\log n)$-space is equal to not using any space.

Proof sketch.  If a Turing machine uses $s(n)$ space, there are $2^{O(s(n))}$ possible configurations and $2^{2^{O(s(n))}}$ possible crossing sequences.  If $s(n) = o(\log\log n)$ then there are two crossing sequences that are the same, and we can further shorten a shortest string accepted by the machine by the following lemma:

Lemma.  Let $M$ be a machine and $x$ be the input.  Suppose two crossing sequence $C_i$ and $C_j$ are equal; then by removing the substring of $x$ from index $i+1$ to $j-i$ (assume $i < j$), we get another string that is accepted by the machine $M$.

The following language is non-regular but can be decided in $O(\log\log n)$ space:

$L = \{\#(0)_2\#(1)_2\# \ldots \#(2^k-1)_2\# : k \ge 0\}$,

where $(i)_2$ is the binary representation of $i$.

* Generating function of regular language

For a given language $L \subseteq \Sigma^*$,

$S_L(z) = \sum_{n\ge 0} |L \cap \Sigma^n| z^n$

is the generating function of $L$.  Using analytic combinatorics we can prove the following useful facts.

Theorem.  For a regular language $L$, the generating function $S_L(z)$ is rational.

Theorem.  Let $A=(Q,\Sigma,\delta,q_0,F)$ be a finite automaton of a language $L$.  Then the generating function of $L$ is the following rational function determined under matrix form

$S_L(z) = [q_0]^T(I-z[\delta])^{-1}[F]$,

where $[\delta](i,j) = | \{$ number of different labels between $q_i$ and $q_j \}|$; $[q_0]$ and $[F]$ as characteristic vectors.

* Minimizing finite automata

Brzozowski’s algorithm use only power set construction $\textsc{Power}$ and edge reversal $\textsc{Rev}$.  One can observe that reversing edges of a DFA gives an NFA of the reverse language.  Then the power set construction gives a minimum DFA.  This algorithm takes exponential time in the worst case.

Hopcroft’s algorithm is the fastest algorithm known; runs in $O(n \log n)$ time.  Try to partition the states using the Myhill-Nerode equivalence relation.

* Relation with $AC^0$

Theorem.  $\mathsf{REG}$ and $\mathsf{AC}^0$ are incomparable.

Proof.  Parity is not in $\mathsf{AC}^0$.  Palindrome/addition/$\{ww : w \in \Sigma^*\}$ are not regular.