Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCoding in graphs and linear orderings
363
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
There is a Turing computable embedding $Phi$ of directed graphs $A$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform interpretation; i.e., for all directed graphs $A$, these formulas interpret $A$ in $Phi(G)$. It follows that A is Medvedev reducible to $Phi(A)$ uniformly; i.e., there is a fixed Turing operator that serves for all $A$. We observe that there is a graph $G$ that is not Medvedev reducible to any linear ordering. Hence, $G$ is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $Sigma_2$ formulas. Any graph can be interpreted in a linear ordering using computable $Sigma_3$ formulas. Friedman and Stanley gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{omega_1,omega}$ formulas that, for all $G$, interpret the input graph $G$ in the output linear ordering $L(G)$. Harrison-Trainor and Montalban have also shown this, by a quite different proof.
rate research
Read More
An algebraic linear ordering is a component of the initial solution of a first-order recursion scheme over the continuous categorical algebra of countable linear orderings equipped with the sum operation and the constant 1. Due to a general Mezei-Wright type result, algebraic linear orderings are exactly those isomorphic to the linear ordering of the leaves of an algebraic tree. Using Courcelles characterization of algebraic trees, we obtain the fact that a linear ordering is algebraic if and only if it can be represented as the lexicographic ordering of a deterministic context-free language. When the algebraic linear ordering is a well-ordering, its order type is an algebraic ordinal. We prove that the Hausdorff rank of any scattered algebraic linear ordering is less than $omega^omega$. It follows that the algebraic ordinals are exactly those less than $omega^{omega^omega}$.
We show that, for every linear ordering of $[2]^n$, there is a large subcube on which the ordering is lexicographic. We use this to deduce that every long sequence contains a long monotone subsequence supported on an affine cube. More generally, we prove an analogous result for linear orderings of $[k]^n$. We show that, for every such ordering, there is a large subcube on which the ordering agrees with one of approximately $frac{(k-1)!}{2(ln 2)^k}$ orderings.
Every real is computable from a Martin-Loef random real. This well known result in algorithmic randomness was proved by Kucera and Gacs. In this survey article we discuss various approaches to the problem of coding an arbitrary real into a Martin-Loef random real,and also describe new results concerning optimal methods of coding. We start with a simple presentation of the original methods of Kucera and Gacs and then rigorously demonstrate their limitations in terms of the size of the redundancy in the codes that they produce. Armed with a deeper understanding of these methods, we then proceed to motivate and illustrate aspects of the new coding method that was recently introduced by Barmpalias and Lewis-Pye and which achieves optimal logarithmic redundancy, an exponential improvement over the original redundancy bounds.
This article discusses some recent trends in Ramsey theory on infinite structures. Trees and their Ramsey theory have been vital to these investigations. The main ideas behind the authors recent method of trees with coding nodes are presented, showing how they can be useful both for coding structures with forbidden configurations as well as those with none. Using forcing as a tool for finite searches has allowed the development of Ramsey theory on such trees, leading to solutions for finite big Ramsey degrees of Henson graphs as well as infinite dimensional Ramsey theory of copies of the Rado graph. Possible future directions for applications of these methods are discussed.
Let G be a definably compact group in an o-minimal expansion of a real closed field. We prove that if dim(G X) < dim G for some definable X subset of G then X contains a torsion point of G. Along the way we develop a general theory for so-called G-linear sets, and investigate definable sets which contain abstract subgroups of G.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
