uu.seUppsala University Publications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
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, p. 911-936Article 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, p. 911-936
##### Keywords [en]
Finite model theory, limit law, random graph, forbidden subgraph
##### National Category
Algebra and Logic
Mathematics
##### Identifiers
ISI: 000324845100011OAI: oai:DiVA.org:uu-207925DiVA, id: diva2:650350
Available from: 2013-09-20 Created: 2013-09-20 Last updated: 2017-12-06Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 527 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Publisher's full text

Koponen, Vera

#### Search in DiVA

Koponen, Vera
##### By organisation
Department of Mathematics
##### In the same journal
Journal of Symbolic Logic (JSL)
##### On the subject
Algebra and Logic

#### Search outside of DiVA

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
doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 512 hits

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf