uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
• apa
• ieee
• modern-language-association
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
A limit law of almost l-partite graphs
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen. (Mathematical logic)
2013 (Engelska)Ingår i: Journal of Symbolic Logic (JSL), ISSN 0022-4812, E-ISSN 1943-5886, Vol. 78, nr 3, s. 911-936Artikel i tidskrift (Refereegranskat) 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.

##### Ort, förlag, år, upplaga, sidor
Association for Symbolic Logic , 2013. Vol. 78, nr 3, s. 911-936
##### Nyckelord [en]
Finite model theory, limit law, random graph, forbidden subgraph
##### Nationell ämneskategori
Algebra och logik
Matematik
##### Identifikatorer
ISI: 000324845100011OAI: oai:DiVA.org:uu-207925DiVA, id: diva2:650350

#### Open Access i DiVA

##### Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 527 kBChecksumma SHA-512
Typ fulltextMimetyp application/pdf

#### Övriga länkar

Förlagets fulltext

Koponen, Vera

#### Sök vidare i DiVA

Koponen, Vera
##### Av organisationen
Matematiska institutionen
##### I samma tidskrift
Journal of Symbolic Logic (JSL)
##### I ämnet
Algebra och logik

#### Sök vidare utanför DiVA

Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.
doi
urn-nbn

#### Altmetricpoäng

doi
urn-nbn
Totalt: 508 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
• apa
• ieee
• modern-language-association
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf