Finite Playground

To verify is human; to prove, divine.

Leave a comment

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.



Leave a comment

MA-SETH is false

Ryan Williams just posted a new paper Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation on ECCC, in which he disproves the MA analog of the Strong Exponential Time Hypothesis (MA-SETH), which is motivated by the paper Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility by Carmosino, Gao, Impagliazzo, Mikhailin, Paturi, and Schneider, proving that assuming Nondeterministic Strong Exponential Time Hypothesis (NSETH) then some problems like 3SUM and APSP cannot be SETH-hard.


Leave a comment

Crossing number of Kn and Gioan’s Theorem

The Harary-Hill Conjecture states that the crossing number of complete graph Kn is

\displaystyle \frac{1}{4} \left\lfloor\frac{n\vphantom{-0}}{2}\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor.

Instead of looking at all possible drawings (which is infinite), we can partition the drawings into classes, depending on the rotation system of the drawing.

The following theorem guarantees us that the crossing number is still well-defined.

Gioan’s Theorem.  Let D1 and D2 be two drawing of graph Kn in the plane.  Then one can transform D1 into Dusing only \Delta-moves.  As a corollary, the crossing number of D1 and Dis the same.

Noted that in general this is not true when the graph is not complete.

Leave a comment

Random stuff, 2016-01-08

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

Leave a comment

A few interesting open problems