uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
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

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

#### Other links

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

GoogleGoogle Scholar
Total: 167 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
doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 512 hits
CiteExportLink to record
Permanent link

Direct link
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