Change search
ReferencesLink to record
Permanent link

Direct link
A limit law of almost l-partite graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics. (Mathematical logic)
2013 (English)In: Journal of Symbolic Logic (JSL), ISSN 0022-4812, E-ISSN 1943-5886, Vol. 78, no 3, 911-936 p.Article in journal (Refereed) Published
Abstract [en]

For integers l >= 1, d >= 0 we study (undirected) graphs with vertices 1,..., n such that the vertices can be partitioned into l parts such that every vertex has at most d neighbours in its own part. The set of all such graphs is denoted P-n (l, d). We prove a labelled first-order limitlaw, i.e., for every first-order sentence phi, the proportion of graphs in P-n (l, d) that satisfy phi converges as n -> infinity. By combining this result with a result of Hundack, Promel and Steger [12] we also prove that if 1 <= s(1) <=...<= s(1) are integers, then Forb(A(I),s(1),...,s(l)) has alabelled first-order limit law, where Forb (A(I),s(1),...,s(l)) denotes the set of all graphs with vertices 1,..., n, for some n, in which there is no subgraph isomorphic to the complete (l + 1)-partite graph with parts of sizes 1, S-1,..., S-l. In the course of doing this we also prove that there exists a first-order formula depending only on l and d, such that the proportion of g e P (I, d) with the following property approaches 1 as n ->infinity: there is a unique partition of {1,..., n} into l parts such that every vertex has at most d neighbours in its own part, and this partition, viewed as an equivalence relation, is defined by xi.

Place, publisher, year, edition, pages
Association for Symbolic Logic , 2013. Vol. 78, no 3, 911-936 p.
Keyword [en]
Finite model theory, limit law, random graph, forbidden subgraph
National Category
Algebra and Logic
Research subject
URN: urn:nbn:se:uu:diva-207925DOI: 10.2178/jsl.7803110ISI: 000324845100011OAI: diva2:650350
Available from: 2013-09-20 Created: 2013-09-20 Last updated: 2013-10-28Bibliographically approved

Open Access in DiVA

almost_l-partite_graphs(527 kB)63 downloads
File information
File name FULLTEXT01.pdfFile size 527 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Koponen, Vera
By organisation
Department of Mathematics
In the same journal
Journal of Symbolic Logic (JSL)
Algebra and Logic

Search outside of DiVA

GoogleGoogle Scholar
Total: 63 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 225 hits
ReferencesLink to record
Permanent link

Direct link