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

.

What is ?  What does it say about ?  Try to calculate some values of and explain.

Crossing number of Kn and Gioan’s Theorem

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

.

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 D₁ and D₂ be two drawing of graph K_n in the plane.  Then one can transform D₁ into D₂ using only -moves.  As a corollary, the crossing number of D₁ and D₂ is 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 -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 .
  Main Theorem [Pach-Rubin-Tardos ’15].  Consider the above set of Jordan curves.  Then the number of crossing points is 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 .  An equivalence relationship can be defined on the nodes of the graph as follows: two nodes and are equivalent if has no perfect matching(!).  

A few interesting open problems

• Does the class of constant-degree expanders have polynomially-long induced paths?
• Planar embedding conjecture — Can every planar graph equipped with an arbitrary shortest-path metric be embedded into L1 with only a constant distortion?  Anastasios Sidiropoulos solves the case when the metric has non-positive curvature; Chekuri et al. proves the case when the graph is O(1)-outerplanar; Chakrabarti et al. proves a natural analogous case when the graph is (K5-e)-free.
• Barnette conjecture (not the one about Hamiltonian cycle) — There is always non-null-homotopic separating simple cycle on every triangulation of an orientable surface of genus g greater than 3.  

Weakly (?) digest

• “Tight lower bound for the channel assignment problem” by Arkadiusz Socała:  No time algorithm to the channel assignment problem assuming ETH.
• “Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph” by Viktor Kiss and Lilla Tothmeresz:  Computing the rank of a divisor on a graph is NP-hard.
• “3SUM Hardness in (Dynamic) Data Structures” by Tsvi Kopelowitz, Seth Pettie, and Ely Porat.
• “Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles” by Christian Wulff-Nilsen.
• “Social choice, computational complexity, Gaussian geometry, and Boolean functions” by Ryan O’Donnell.

Complexity of reachability problem on surface graphs

Directed reachability problem on surface graphs can be solved in poly-time and sub-linear space (!).  See the survey by Vinodchandran Variyam.  

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.