On the Typical Structure of Graphs in a Monotone Property

Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{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 i...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2014-08, Vol.21 (3), p.P3.34
Main Authors: Janson, Svante, Uzzell, Andrew J.
Format: Article
Language:English
Subjects:
Graph limits
Monotone properties
Structure of graphs
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c258t-2a05918d95c775e49b064051bbb78f6c28a33d7316cffb890a4e27d5e1c0da043
cites
container_end_page
container_issue 3
container_start_page P3.34
container_title The Electronic journal of combinatorics
container_volume 21
creator Janson, Svante
Uzzell, Andrew J.
description Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{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 $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close to being a balanced $r$-partite graph.
doi_str_mv 10.37236/4266
format article
fullrecord <record><control><sourceid>swepub_cross</sourceid><recordid>TN_cdi_swepub_primary_oai_DiVA_org_uu_233011</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>oai_DiVA_org_uu_233011</sourcerecordid><originalsourceid>FETCH-LOGICAL-c258t-2a05918d95c775e49b064051bbb78f6c28a33d7316cffb890a4e27d5e1c0da043</originalsourceid><addsrcrecordid>eNpNkMtKAzEARYMoWGv_IRt3juYxeS1L1SpUKljdhiST2JE6GZIMMn9ftSKu7l2cexcHgBlGV1QQyq9rwvkRmGAkRCUV4cf_-ik4y_kdIUyUYhOg1h0sWw83Y986s4PPJQ2uDMnDGOAymX6bYdtBAx9jF0vsPHxKsfepjOfgJJhd9rPfnIKXu9vN4r5arZcPi_mqcoTJUhGDmMKyUcwJwXytLOI1YthaK2TgjkhDaSMo5i4EKxUytSeiYR471BhU0ym4PPzmT98PVvep_TBp1NG0-qZ9neuY3vQwaEIpwvgLvzjgLsWckw9_A4z0jx79rYfuAc3YVaM</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>On the Typical Structure of Graphs in a Monotone Property</title><source>Freely Accessible Science Journals - check A-Z of ejournals</source><creator>Janson, Svante ; Uzzell, Andrew J.</creator><creatorcontrib>Janson, Svante ; Uzzell, Andrew J.</creatorcontrib><description>Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{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 $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close to being a balanced $r$-partite graph.</description><identifier>ISSN: 1077-8926</identifier><identifier>ISSN: 1097-1440</identifier><identifier>EISSN: 1077-8926</identifier><identifier>DOI: 10.37236/4266</identifier><language>eng</language><subject>Graph limits ; Monotone properties ; Structure of graphs</subject><ispartof>The Electronic journal of combinatorics, 2014-08, Vol.21 (3), p.P3.34</ispartof><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c258t-2a05918d95c775e49b064051bbb78f6c28a33d7316cffb890a4e27d5e1c0da043</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,27924,27925</link.rule.ids><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-233011$$DView record from Swedish Publication Index$$Hfree_for_read</backlink></links><search><creatorcontrib>Janson, Svante</creatorcontrib><creatorcontrib>Uzzell, Andrew J.</creatorcontrib><title>On the Typical Structure of Graphs in a Monotone Property</title><title>The Electronic journal of combinatorics</title><description>Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{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 $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close to being a balanced $r$-partite graph.</description><subject>Graph limits</subject><subject>Monotone properties</subject><subject>Structure of graphs</subject><issn>1077-8926</issn><issn>1097-1440</issn><issn>1077-8926</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2014</creationdate><recordtype>article</recordtype><recordid>eNpNkMtKAzEARYMoWGv_IRt3juYxeS1L1SpUKljdhiST2JE6GZIMMn9ftSKu7l2cexcHgBlGV1QQyq9rwvkRmGAkRCUV4cf_-ik4y_kdIUyUYhOg1h0sWw83Y986s4PPJQ2uDMnDGOAymX6bYdtBAx9jF0vsPHxKsfepjOfgJJhd9rPfnIKXu9vN4r5arZcPi_mqcoTJUhGDmMKyUcwJwXytLOI1YthaK2TgjkhDaSMo5i4EKxUytSeiYR471BhU0ym4PPzmT98PVvep_TBp1NG0-qZ9neuY3vQwaEIpwvgLvzjgLsWckw9_A4z0jx79rYfuAc3YVaM</recordid><startdate>20140828</startdate><enddate>20140828</enddate><creator>Janson, Svante</creator><creator>Uzzell, Andrew J.</creator><scope>AAYXX</scope><scope>CITATION</scope><scope>ADTPV</scope><scope>AOWAS</scope><scope>DF2</scope></search><sort><creationdate>20140828</creationdate><title>On the Typical Structure of Graphs in a Monotone Property</title><author>Janson, Svante ; Uzzell, Andrew J.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c258t-2a05918d95c775e49b064051bbb78f6c28a33d7316cffb890a4e27d5e1c0da043</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2014</creationdate><topic>Graph limits</topic><topic>Monotone properties</topic><topic>Structure of graphs</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Janson, Svante</creatorcontrib><creatorcontrib>Uzzell, Andrew J.</creatorcontrib><collection>CrossRef</collection><collection>SwePub</collection><collection>SwePub Articles</collection><collection>SWEPUB Uppsala universitet</collection><jtitle>The Electronic journal of combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Janson, Svante</au><au>Uzzell, Andrew J.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>On the Typical Structure of Graphs in a Monotone Property</atitle><jtitle>The Electronic journal of combinatorics</jtitle><date>2014-08-28</date><risdate>2014</risdate><volume>21</volume><issue>3</issue><spage>P3.34</spage><pages>P3.34-</pages><issn>1077-8926</issn><issn>1097-1440</issn><eissn>1077-8926</eissn><abstract>Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{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 $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close to being a balanced $r$-partite graph.</abstract><doi>10.37236/4266</doi></addata></record>
fulltext fulltext
identifier ISSN: 1077-8926
ispartof The Electronic journal of combinatorics, 2014-08, Vol.21 (3), p.P3.34
issn 1077-8926
1097-1440
1077-8926
language eng
recordid cdi_swepub_primary_oai_DiVA_org_uu_233011
source Freely Accessible Science Journals - check A-Z of ejournals
subjects Graph limits
Monotone properties
Structure of graphs
title On the Typical Structure of Graphs in a Monotone Property
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T08%3A58%3A21IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-swepub_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=On%20the%20Typical%20Structure%20of%20Graphs%20in%20a%20Monotone%20Property&rft.jtitle=The%20Electronic%20journal%20of%20combinatorics&rft.au=Janson,%20Svante&rft.date=2014-08-28&rft.volume=21&rft.issue=3&rft.spage=P3.34&rft.pages=P3.34-&rft.issn=1077-8926&rft.eissn=1077-8926&rft_id=info:doi/10.37236/4266&rft_dat=%3Cswepub_cross%3Eoai_DiVA_org_uu_233011%3C/swepub_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c258t-2a05918d95c775e49b064051bbb78f6c28a33d7316cffb890a4e27d5e1c0da043%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true