# 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.

## 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.

## Cute calculus puzzle

Let

$f(x) = \mathrm{arctan}(x) + \mathrm{arctan}(1/x)$.

What is $\frac{d}{dx}f(x)$?  What does it say about $f(x)$?  Try to calculate some values of $f(x)$ and explain.

## 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.

## 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(!).