Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

The complexity of recursive constraint satisfaction problems

We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through finitely branching recursive trees or recursive binary trees. There are a large number of results in the literature on the complexity of the problem of finding an infinite path through a recursive tree. Our main result allows us to automatically transfer such results to give equivalent results about the complexity of the problem of finding a solution to a recursive constraint satisfaction problem.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

A condition for assured 3-face-colorability of infinite plane graphs with a given spanning tree

Given an infinite leafless tree drawn on the plane, we ask whether or not one can add edges between the vertices of the tree obtaining a non-3-face-colorable graph. We formulate a condition conjectured to be necessary and sufficient for this to be possible. We prove that this condition is indeed necessary and sufficient for trees with maximal degree 3, and that it is sufficient for general trees. In particular, we prove that every infinite plane graph with a spanning binary tree is 3-face-colorable.     

Locally Quadratic Modules and Minuscule Representations

We give a new, geometric proof of a theorem by Timmesfeld showing that for simple Chevalley groups, abstract modules where all roots act quadratically are direct sums of minuscule representations. Our proof is uniform, treats finite and infinite fields on an equal footing, and includes Lie rings.     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

On the deque conjecture for the splay algorithm

Splay is a simple, efficient algorithm for searching binary search trees, devised by Sleator and Tarjan, that reorganizes the tree after each search by means of rotations. An open conjecture of Sleator and Tarjan states that Splay is, in essence, the fastest algorithm for processing any sequence of search operations on a binary search tree, using only rotations to reorganize the tree. Tarjan proved a basic special case of this conjecture, called theScanning Theorem, and conjectured a more general special case, called theDeque Conjecture. The Deque Conjecture states that Splay requires linear time to process sequences of deque operations on a binary tree. We prove the following results:

1. Almost tight lower and upper bounds on the maximum numbers of occurrences of various types of right rotations in a sequence of right rotations performed on a binary tree. In particular, the lower bound for right 2-turns refutes Sleator's Right Turn Conjecture.
2. A linear times inverse Ackerman upper bound for the Deque Conjecture. This bound is derived using the above upper bounds.
3. Two new proofs of the Scanning Theorem, one, a simple potential-based proof that solves Tarjan's problem of finding a potential-based proof for the theorem, the other, an inductive proof that generalizes the theorem.

     

Local Convergence of Large Critical Multi-type Galton–Watson Trees and Applications to Random Maps

We show that large critical multi-type Galton–Watson trees, when conditioned to be large, converge locally in distribution to an infinite tree which is analogous to Kesten’s infinite monotype Galton–Watson tree. This is proven when we condition on the number of vertices of one fixed type, and with an extra technical assumption if we count at least two types. We then apply these results to study local limits of random planar maps, showing that large critical Boltzmann-distributed random maps converge in distribution to an infinite map.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

Computable Ramsey’s theorem for pairs needs infinitely many $$\Pi ^0_2$$ sets

In Ramsey’s Theorem and Recursion Theory, Theorem 4.2, Jockusch proved that for any computable k-coloring of pairs of integers, there is an infinite \(\Pi ^0_2\) homogeneous set. The proof used a countable collection of \(\Pi ^0_2\) sets as potential infinite homogeneous sets. In a remark preceding the proof, Jockusch stated without proof that it can be shown that there is no computable way to prove this result with a finite number of \(\Pi ^0_2\) sets. We provide a proof of this claim, showing that there is no computable way to take an index for an arbitrary computable coloring and produce a finite number of indices of \(\Pi ^0_2\) sets with the property that one of those sets will be homogeneous for that coloring. While proving this result, we introduce n-trains as objects with useful combinatorial properties which can be used as approximations to infinite \(\Pi ^0_2\) sets.     

The 2D‐directed spanning forest is almost surely a tree

We consider the Directed Spanning Forest (DSF) constructed as follows: given a Poisson point process N on the plane, the ancestor of each point is the nearest vertex of N having a strictly larger abscissa. We prove that the DSF is actually a tree. Contrary to other directed forests of the literature, no Markovian process can be introduced to study the paths in our DSF. Our proof is based on a comparison argument between surface and perimeter from percolation theory. We then show that this result still holds when the points of N belonging to an auxiliary Boolean model are removed. Using these results, we prove that there is no bi‐infinite paths in the DSF. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Steiner triple systems satisfying the 4-vertex condition

Higman asked which block graphs of Steiner triple systems of order v satisfy the 4-vertex condition and left the cases v = 9, 13, 25 unsettled.We give a complete answer to this question by showing that the affine plane of order 3 and the binary projective spaces are the only such systems. The major part of the proof is to show that no block graph of a Steiner triple system of order 25 satisfies the 4-vertex condition.     

The Holmes–Wick theorem on two-weight bounds for higher order commutators revisited

A sufficient condition for the two-weight boundedness of higher order commutators was recently obtained by Holmes and Wick in terms of an intersection of two BMO spaces. We provide an alternative proof, showing that the higher order case can be deduced by a classical Cauchy integral argument from the corresponding first order result of Holmes, Lacey and Wick.     

Arithmetic transfinite induction and recursive well-orderings

A uniform, algebraic proof that every number-theoretic assertion provable in any of the intuitionistic theories T listed below has a well-founded recursive proof tree (demonstraby in T) is given. Thus every such assertion is provable by transfinite induction over some primitive recursive well-ordering. T can be higher order number theory, set theory, or its extensions equiconsistent with large cardinals. It is shown that there is a number-theoretic assertion B(n) (independent of T) with a parameter n such that any primitive recursive linear ordering R on ω for which transfinite induction on R for B(n) is provable in T is in fact a well-ordering.     

Markov approximation and consistent estimation of unbounded probabilistic suffix trees

We consider infinite order chains whose transition probabilities depend on a finite suffix of the past. These suffixes are of variable length and the set of the lengths of all suffix is unbounded. We assume that the probability transitions for each of these suffixes are continuous with exponential decay rate. For these chains, we prove the weak consistency of a modification of Rissanen's algorithm Context which estimates the length of the suffix needed to predict the next symbol, given a finite sample. This generalizes to the unbounded case the original result proved for variable length Markov chains in the seminal paper Rissanen (1983). Our basic tool is the canonical Markov approximation which enables to approximate the chain of infinite order by a sequence of variable length Markov chains of increasing order. Our proof is constructive and we present an explicit decreasing upper bound for the probability of wrong estimation of the length of the current suffix.     

Countable Products of Čech-scattered supercomplete spaces

We prove by using well-founded trees that a countable product of supercomplete spaces, scattered with respect to ech-complete subsets, is supercomplete. This result extends results given in [1], [5], [6], [19], [26] and its proof improves that given in [19].     

A special case of de Branges' theorem on the inverse monodromy problem

We give a new proof of a special case of de Branges' theorem on the inverse monodromy problem: when an associated Riemann surface is of Widom type with Direct Cauchy Theorem. The proof is based on our previous result (with M.Sodin) on infinite dimensional Jacobi inversion and on Levin's uniqueness theorem for conformal maps onto comb-like domains. Although in this way we can not prove de Branges' Theorem in full generality, our proof is rather constructive and may lead to a multi-dimensional generalization. It could also shed light on the structure of invariant subspaces of Hardy spaces on Riemann surfaces of infinite genus.This work was supported by the Austrian Founds zur Förderung der wissenschaftlichen Forschung, project-number P12985-TEC     

Counting trees with random walks

We give a simple proof of Tutte’s matrix-tree theorem, a well-known result providing a closed-form expression for the number of rooted spanning trees in a directed graph. Our proof stems from placing a random walk on a directed graph and then applying the Markov chain tree theorem to count trees. The connection between the two theorems is not new, but it appears that only one direction of the formal equivalence between them is readily available in the literature. The proof we now provide establishes the other direction. More generally, our approach is another example showing that random walks can serve as a powerful glue between graph theory and Markov chain theory, allowing formal statements from one side to be carried over to the other.     

Slim sets of binary trees

A classical problem in phylogenetic tree analysis is to decide whether there is a phylogenetic tree T that contains all information of a given collection P of phylogenetic trees. If the answer is “yes” we say that P is compatible and T displays P. This decision problem is NP-complete even if all input trees are quartets, that is binary trees with exactly four leaves. In this paper, we prove a sufficient condition for a set of binary phylogenetic trees to be compatible. That result is used to give a short and self-contained proof of the known characterization of quartet sets of minimal cardinality which are displayed by a unique phylogenetic tree.