A limit law of almost ll-partite graphs

preprint2013arXivOpen access

Abstract

For integers l≥2l \geq 2, d≥1d \geq 1 we study (undirected) graphs with vertices 1,...,n1, ..., n such that the vertices can be partitioned into ll parts such that every vertex has at most dd neighbours in its own part. The set of all such graphs is denoted $\mbP_n(l,d)$. We prove a labelled first-order limit law, i.e., for every first-order sentence φφ, the proportion of graphs in $\mbP_n(l,d)$ that satisfy φφ converges as n→∞n \to \infty. By combining this result with a result of Hundack, Prömel and Steger \cite{HPS} we also prove that if 1≤s1≤...≤sl1 \leq s_1 \leq ... \leq s_l are integers, then $\mb{Forb}(\mcK_{1, s_1, ..., s_l})$ has a labelled first-order limit law, where $\mb{Forb}(\mcK_{1, s_1, ..., s_l})$ denotes the set of all graphs with vertices 1,...,n1, ..., n, for some nn, in which there is no subgraph isomorphic to the complete (l+1)(l+1)-partite graph with parts of sizes 1,s1,...,sl1, s_1, ..., s_l. In the course of doing this we also prove that there exists a first-order formula ξξ (depending only on ll and dd) such that the proportion of $\mcG \in \mbP_n(l,d)$ with the following property approaches 1 as n→∞n \to \infty: there is a unique partition of {1,...,n}\{1, ..., n\} into ll parts such that every vertex has at most dd neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by ξξ.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.