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
On the Typical Structure of Graphs in a Monotone Property
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2014 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 21, no 3, p. P3.34-Article in journal (Refereed) Published
Abstract [en]

Given a graph property P, it is interesting to determine the typical structure of graphs that satisfy P. In this paper, we consider monotone properties, that is, properties that are closed under taking subgraphs. Using results from the theory of graph limits, we show that if P is a monotone property and r is the largest integer for which every r-colorable graph satisfies P, then almost every graph with P is close to being a balanced r-partite graph.

Place, publisher, year, edition, pages
2014. Vol. 21, no 3, p. P3.34-
Keywords [en]
Graph limits, Monotone properties, Structure of graphs
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-233011ISI: 000341119300002OAI: oai:DiVA.org:uu-233011DiVA, id: diva2:754179
Available from: 2014-10-09 Created: 2014-09-29 Last updated: 2017-12-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Janson, SvanteUzzell, Andrew J.

Search in DiVA

By author/editor
Janson, SvanteUzzell, Andrew J.
By organisation
Department of Mathematics
In the same journal
The Electronic Journal of Combinatorics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 395 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