The monadic theory and the “next world”

Suppose thatV is a model of ZFC andU ∈ V is a topological space or a richer structure for which it makes sense to speak about the monadic theory. LetB be the Boolean algebra of regular open subsets ofU. If the monadic theory ofU allows one to speak in some sense about a family ofκ everywhere dense and almost disjoint sets, then the second-orderV ^B-theory of ϰ is interpretable in the monadicV-theory ofU; this is our Interpretation Theorem. Applying the Interpretation Theorem we strengthen some previous results on complexity of the monadic theories of the real line and some other topological spaces and linear orders. Here are our results about the real line. Letr be a Cohen real overV. The second-orderV[r]-theory of ℵ₀ is interpretable in the monadicV-theory of the real line. If CH holds inV then the second-orderV[r]-theory of the real line is interpretable in the monadicV-theory of the real line. Dedicated to the memory of Abraham Robinson on the tenth anniversary of his death The author thanks the United States-Israel Binational Science Foundation for supporting the research.     

Notes on monadic logic. Part B: Complexity of linear orders in ZFC

In those notes we prove in ZFC: (a) that the monadic theory of linear order (syntactically) interprets and has the same Lowenheim number as second order logic (the interpretation is semantical but not in the “classical” way), (b) a parallel (weaker) result for the monadic logic for completely metrizable spaces. The main results are in §§5, 6. The author would like to thank the United States-Israel Binational Science Foundation for partially supporting this research, and Alice Leonhardt for the beautiful typing. Publication No. 284b.     

Distributive lattices with a decidable monadic second order theory

A class of finite distributive lattices has a decidable monadic second order theory iff (a) the join irreducible elements of its members have a decidable monadic second order theory, and (b) the width of the lattices is bounded. Similar results are obtained for the monadic chain and the monadic antichain theory where quantification is restricted to chains and antichains, resp. Furthermore, there is no (up to finite difference) maximal set of finite distributive lattices with a decidable monadic (chain or antichain, resp.) theory. Received December 6, 2000; accepted in final form May 30, 2002.     

Hall-Littlewood Polynomials and Cohen-Lenstra Heuristics for Jacobians of Random Graphs

Cohen-Lenstra heuristics for Jacobians of random graphs give rise to random partitions. We connect these random partitions to the Hall-Littlewood polynomials of symmetric function theory, and use this connection to give combinatorial proofs of properties of these random partitions. In addition, we use Markov chains to give an algorithm for generating these partitions.     

Logical laws for existential monadic second-order sentences with infinite first-order parts

We consider existential monadic second-order sentences ?X φ(X) about undirected graphs, where ?X is a finite sequence of monadic quantifiers and φ(X) ∈ +_∞ω^ω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.     

Monadic second-order model-checking on decomposable matroids

A notion of branch-width, which generalizes the one known for graphs, can be defined for matroids. We first give a proof of the polynomial time model-checking of monadic second-order formulas on representable matroids of bounded branch-width, by reduction to monadic second-order formulas on trees. This proof is much simpler than the one previously known. We also provide a link between our logical approach and a grammar that allows one to build matroids of bounded branch-width. Finally, we introduce a new class of non-necessarily representable matroids, described by a grammar and on which monadic second-order formulas can be checked in linear time.     

Random walks on graphs with interval weights and precise marginals

We propose a model of random walks on weighted graphs where the weights are interval valued, and connect it to reversible imprecise Markov chains. While the theory of imprecise Markov chains is now well established, this is a first attempt to model reversible chains. In contrast with the existing theory, the probability models that have to be considered are now non-convex. This presents a difficulty in computational sense, since convexity is critical for the existence of efficient optimization algorithms used in the existing models. The second part of the paper therefore addresses the computational issues of the model. The goal is finding sets of weights which maximize or minimize expectations corresponding to multiple steps transition probabilities. In particular, we present a local optimization algorithm and numerically test its efficiency. We show that its application allows finding close approximations of the globally best solutions in reasonable time.     

Orientations of graphs with uncountable chromatic number

Motivated by an old conjecture of P. Erdős and V. Neumann‐Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that, consistently, there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4‐cycle. Next, we prove that several well‐known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement “every graph G of size and chromatic number ω₁ has an orientation D with uncountable dichromatic number” is independent of ZFC. We end the article with several open problems.     

Interpretation of graphs in noncommutative theories of Frechet powers

The basic result of the work is the theorem that if an axiomatizable class K of structures is closed under reduced powers by the Frechet filter and it has a stable noncommutative theory, then the class of all graphs is interpretable in the class K.     

Robinson forcing is not absolute

Robinson (or infinite model theoretic) forcing is studied in the context of set theory. The major result is that infinite forcing, genericity, and related notions are not absolute relative to ZFC. This answers a question of G. Sacks and provides a non-trivial example of a non-absolute notion of model theory. This non-absoluteness phenomenon is shown to be intrinsic to the concept of infinite forcing in the sense that any ZFC-definable set theory, relative to which forcing is absolute, has the flavor of asserting self-inconsistency. More precisely: IfT is a ZFC-definable set theory such that the existence of a standard model ofT is consistent withT, then forcing is not absolute relative toT. For example, if it is consistent that ZFC+ “there is a measureable cardinal” has a standard model then forcing is not absolute relative to ZFC+ “there is a measureable cardinal.” Some consequences: 1) The resultants for infinite forcing may not be chosen “effectively” in general. This answers a question of A. Robinson. 2) If ZFC is consistent then it is consistent that the class of constructible division rings is disjoint from the class of generic division rings. 3) If ZFC is consistent then the generics may not be axiomatized by a single sentence ofL _w/w. In Memoriam: Abraham Robinson     

Random walks and flights over connected graphs and complex networks

Markov chains provide us with a powerful probabilistic tool that allows to study the structure of connected graphs in details. The statistics of events for Markov chains defined on connected graphs can be effectively studied by the method of generalized inverses which we review. The approach is also applicable for directed graphs and interacting networks which share the set of nodes. We discuss a generalization of Lévy flight random walks for large complex networks and study the interplay between the nonlinearity of diffusion process and the topological structure of the network.     

Graph operations characterizing rank-width

Graph complexity measures such as tree-width, clique-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. These algorithms are based on hierarchical decompositions of the considered graphs, and on boundedness conditions on the graph operations that, more or less explicitly, recombine the components of decompositions into larger graphs. Rank-width is defined in a combinatorial way, based on a tree, and not in terms of graph operations. We define operations on graphs that characterize rank-width and help for the construction of Fixed Parameter Tractable algorithms, especially for problems specified in monadic second-order logic.     

Monadic theory of order and topology II

Assuming the Continuum Hypothesis we interpret the theory of the cardinal 2^ℵ ₀ with quantification over the constructible monadic, dyadic, etc. predicates in the monadic (second-order) theory of the real line, in the monadic theory of any other short non-modest chain, in monadic topology of Cantor’s Discontinuum and some other monadic theories. We build monadic sentences defining the real line up to isomorphism under some set-theoretic assumptions. There are some other results.     

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is definable in monadic second-order logic (MSOL). We show that for bounded tree-width these problems are solvable in polynomial time. The same holds for bounded clique width in the cases, where the decomposition, which establishes the bound on the clique-width, can be computed in polynomial time and for problems expressible by monadic second-order formulas without edge set quantification. Such quantifications are allowed in the case of graphs with bounded tree-width. As applications we discuss in detail how this affects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL definable graph properties. Finally, our results are also applicable to SAT and ♯SAT.     

The monadic theory of (ω 2, <) may be complicated

Summary Assume ZFC is consistent then for everyB there is a generic extension of the ground world whereB is recursive in the monadic theory of ₂.The second authro would like to thank the United States — Israel Binational Science Foundation for partially supporting this research. Publ. 411     

图上的随机动力系统及其诱导的马尔可夫链

In this paper,we define a model of random dynamical systems(RDS)on graphs and prove that they are actually homogeneous discrete-time Markov chains.Moreover,a necessary and sufficient condition is obtained for that two state vectors can communicate with each other in a random dynamical system(RDS).     

An Approximate Version of Sidorenko’s Conjecture

A beautiful conjecture of Erdős-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.     

On the axiom of union

In this paper, we study the union axiom of ZFC. After a brief introduction, we sketch a proof of the folklore result that union is independent of the other axioms of ZFC. In the third section, we prove some results in the theory T:= ZFC minus union. Finally, we show that the consistency of T plus the existence of an inaccessible cardinal proves the consistency of ZFC.     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

Notes on monadic logic. part A. Monadic theory of the real line

The second-order theory of the continuum in the Cohen extension of a set-theoretic universe is interpreted in the monadic theory of the real line and may be interpreted in the monadic topology of Cantor’s discontinuum as well.