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
Forskningsämne
Matematik
Identifikatorer
URN: urn:nbn:se:uu:diva-207925DOI: 10.2178/jsl.7803110ISI: 000324845100011OAI: oai:DiVA.org:uu-207925DiVA, id: diva2:650350
Tillgänglig från: 2013-09-20 Skapad: 2013-09-20 Senast uppdaterad: 2017-12-06Bibliografiskt granskad

Open Access i DiVA

almost_l-partite_graphs(527 kB)162 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 527 kBChecksumma SHA-512
e02f6bf9258cb67d8de71d73e551988507127f4ea8574b53001245825add500e32a8271f8fdb1eed8fc837b28c0156184c7a57c0ce404d4690d2852071e6fa91
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Personposter BETA

Koponen, Vera

Sök vidare i DiVA

Av författaren/redaktören
Koponen, Vera
Av organisationen
Matematiska institutionen
I samma tidskrift
Journal of Symbolic Logic (JSL)
Algebra och logik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 162 nedladdningar
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