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.     

An axiom system for the weak monadic second order theory of two successors

A compelte axiom system for the weak monadic second order theory of two successor functions, W2S, is presented. The axiom system consists, roughly, of the generalized Peano axioms and of an inductive definition of the finite sets. For the proof, methods of J. R. Buchi and J. Doner are used to obtain a new decision procedure for W2S, whose proofs are easily formalized. Different finiteness axioms are discussed. This paper was written while the author was visiting at Purdue University, and appeared first as Report CSD TR-56, Purdue University, 1971.     

Interpreting the monadic second order theory of one successor in expansions of the real line

We give sufficient conditions for a first order expansion of the real line to define the standard model of the monadic second order theory of one successor. Such an expansion does not satisfy any of the combinatorial tameness properties defined by Shelah, such as NIP or even NTP₂. We use this to deduce the first general results about definable sets in NTP₂ expansions of (R,<, +).     

Infinite spectra in the first order theory of graphs

The psectrum Spec(A) of a sentenceA is, roughly, the set of those a for whichA has a threshold function at or nearp=n ^–a . Examples are given ofA with infinite spectra and with spectra of order type ⁱ for arbitraryi.     

Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false

In 2001, J.-M. Le Bars disproved the zero-one law (that says that every sentence from a certain logic is either true asymptotically almost surely (a.a.s.), or false a.a.s.) for existential monadic second order sentences (EMSO) on undirected graphs. He proved that there exists an EMSO sentence ? such that $\mathsf{P}(G_n??)$ does not converge as $n\to \infty$ (here, the probability distribution is uniform over the set of all graphs on the labeled set of vertices $\{1,\dots ,n\}$). In the same paper, he conjectured that, for EMSO sentences with 2 first order variables, the zero-one law holds. In this paper, we disprove this conjecture.     

First-order and monadic properties of highly sparse random graphs

A random graph is said to obey the (monadic) zero–one k-law if, for any property expressed by a first-order formula (a second-order monadic formula) with a quantifier depth of at most k, the probability of the graph having this property tends to either zero or one. It is well known that the random graph G(n, n^–α) obeys the (monadic) zero–one k-law for any k ∈ ? and any rational α > 1 other than 1 + 1/m (for any positive integer m). It is also well known that the random graph does not obey both k-laws for the other rational positive α and sufficiently large k. In this paper, we obtain lower and upper bounds on the largest at which both zero–one k-laws hold for α = 1 + 1/m.     

Spectra of short monadic sentences about sparse random graphs

A random graph G(n, p) is said to obey the (monadic) zero–one k-law if, for any monadic formula of quantifier depth k, the probability that it is true for the random graph tends to either zero or one. In this paper, following J. Spencer and S. Shelah, we consider the case p = n ^?α. It is proved that the least k for which there are infinitely many α such that a random graph does not obey the zero–one k-law is equal to 4.     

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.     

Existential monadic second order logic on random rooted trees

We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton–Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).     

Random perfect graphs

We investigate the asymptotic structure of a random perfect graph P_n sampled uniformly from the set of perfect graphs on vertex set . Our approach is based on the result of Prömel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number and clique number is close to a concentrated distribution L(n) which plays an important role in our generation method. We also prove that the probability that P_n contains any given graph H as an induced subgraph is asymptotically 0 or or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon .     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

Random interval graphs

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number of customers arriving during a busy period, while the size K of the largest clique (which for interval graphs is equal to the chromatic number) corresponds to the maximum number of customers in the system during a busy period. We obtain the following results for both the M/D/∞ and the M/M/∞ models, with arrival rate λ per mean service time. The expected number of vertices is e^λ, and the distribution of the N/e^λ converges pointwise to an exponential distribution with mean 1 as λ tends to infinity. This implies that the distribution of log N−λ converges pointwise to a distribution with mean −γ (where γ is Euler's constant) and variance π²/6. The size K of the largest clique falls in the interval [eλ−2 log λ, eλ+1] with probability tending to 1 as λ tends to infinity. Thus the distribution of the ratio K/log N converges pointwise to that of the constant e, in contrast to the situation for random graphs generated by unbiased coin flips, in which the distribution of K/log N converges pointwise to that of the constant 2/log 2. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 361–380, 1998     

Random interval graphs

In this paper we introduce a notion ofrandom interval graphs: the intersection graphs of real, compact intervals whose end points are chosen at random. We establish results about the number of edges, degrees, Hamiltonicity, chromatic number and independence number of almost all interval graphs.     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

Convergence of probabilities for the second order monadic properties of a random mapping

We prove that the probability of each second order monadic property of a random mapping u_n converges as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 277–295, 1997     

Random walks on graphs

In this paper the following Markov chains are considered: the state space is the set of vertices of a connected graph, and for each vertex the transition is always to an adjacent vertex, such that each of the adjacent vertices has the same probability. Detailed results are given on the expectation of recurrence times, of first-entrance times, and of symmetrized first-entrance times (called commuting times). The problem of characterizing all connected graphs for which the commuting time is constant over all pairs of adjacent vertices is solved almost completely.