Finitely forcible graphons with an almost arbitrary structure

A basic result from the theory of quasirandom graphs, due to Andrew Thomason, is that if is a graph with vertices and density , and if the number of 4-cycles in is approximately , then resembles a random graph of the same density. In particular, between any two sets and of vertices the number of edg...

Full description

Saved in:
Bibliographic Details
Published in:Discrete analysis 2020
Main Authors: Noel, Jonathan, Kral, Daniel, Lovasz, Laszlo Miklos, Sosnovec, Jakub
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page
container_issue
container_start_page
container_title Discrete analysis
container_volume
creator Noel, Jonathan
Kral, Daniel
Lovasz, Laszlo Miklos
Sosnovec, Jakub
description A basic result from the theory of quasirandom graphs, due to Andrew Thomason, is that if is a graph with vertices and density , and if the number of 4-cycles in is approximately , then resembles a random graph of the same density. In particular, between any two sets and of vertices the number of edges is approximately . (Here, “approximately” means "to within a small fraction of , so the statement is non-trivial only for sets and that are not too small.)
doi_str_mv 10.19086/da.12058
format article
fullrecord <record><control><sourceid>doaj_cross</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_6bbd95587d8a46e98ac58e44cc79d7c0</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_6bbd95587d8a46e98ac58e44cc79d7c0</doaj_id><sourcerecordid>oai_doaj_org_article_6bbd95587d8a46e98ac58e44cc79d7c0</sourcerecordid><originalsourceid>FETCH-LOGICAL-c290t-ca0f3bcfb4adb3c23b452e08faf19ac21f20407079157fd524a90abf497a934c3</originalsourceid><addsrcrecordid>eNpNkM1KAzEYRYMoWLQL32C2LqZ--ZkmWbiQYrVQcKPr8OWvTZl2SpIifXtLK-LqXu7icDmEPFCYUA1q-uRxQhl06oqMGNey5ZTp63_9loxL2QAAA8oF0yPyPE-7VEN_bOKQXbJ9aFYZ9-thV5rvVNcN7hrst0OpDWabasZ8bErNB1cPOdyTm4h9CePfvCNf89fP2Xu7_HhbzF6WrWMaausQIrcuWoHecse4FR0LoCJGqtExGhkIkCA17WT0HROoAW0UWqLmwvE7srhw_YAbs89pe7phBkzmPAx5ZTDX5PpgptZ63XVKeoViGrRC16kghHNSe-ngxHq8sFweSskh_vEomLNG49GcNfIfnONlbQ</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Finitely forcible graphons with an almost arbitrary structure</title><source>ROAD: Directory of Open Access Scholarly Resources</source><creator>Noel, Jonathan ; Kral, Daniel ; Lovasz, Laszlo Miklos ; Sosnovec, Jakub</creator><creatorcontrib>Noel, Jonathan ; Kral, Daniel ; Lovasz, Laszlo Miklos ; Sosnovec, Jakub ; University of Victoria</creatorcontrib><description>A basic result from the theory of quasirandom graphs, due to Andrew Thomason, is that if is a graph with vertices and density , and if the number of 4-cycles in is approximately , then resembles a random graph of the same density. In particular, between any two sets and of vertices the number of edges is approximately . (Here, “approximately” means "to within a small fraction of , so the statement is non-trivial only for sets and that are not too small.)</description><identifier>ISSN: 2397-3129</identifier><identifier>EISSN: 2397-3129</identifier><identifier>DOI: 10.19086/da.12058</identifier><language>eng</language><publisher>Diamond Open Access Journals</publisher><ispartof>Discrete analysis, 2020</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,4024,27923,27924,27925</link.rule.ids></links><search><creatorcontrib>Noel, Jonathan</creatorcontrib><creatorcontrib>Kral, Daniel</creatorcontrib><creatorcontrib>Lovasz, Laszlo Miklos</creatorcontrib><creatorcontrib>Sosnovec, Jakub</creatorcontrib><creatorcontrib>University of Victoria</creatorcontrib><title>Finitely forcible graphons with an almost arbitrary structure</title><title>Discrete analysis</title><description>A basic result from the theory of quasirandom graphs, due to Andrew Thomason, is that if is a graph with vertices and density , and if the number of 4-cycles in is approximately , then resembles a random graph of the same density. In particular, between any two sets and of vertices the number of edges is approximately . (Here, “approximately” means "to within a small fraction of , so the statement is non-trivial only for sets and that are not too small.)</description><issn>2397-3129</issn><issn>2397-3129</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><sourceid>DOA</sourceid><recordid>eNpNkM1KAzEYRYMoWLQL32C2LqZ--ZkmWbiQYrVQcKPr8OWvTZl2SpIifXtLK-LqXu7icDmEPFCYUA1q-uRxQhl06oqMGNey5ZTp63_9loxL2QAAA8oF0yPyPE-7VEN_bOKQXbJ9aFYZ9-thV5rvVNcN7hrst0OpDWabasZ8bErNB1cPOdyTm4h9CePfvCNf89fP2Xu7_HhbzF6WrWMaausQIrcuWoHecse4FR0LoCJGqtExGhkIkCA17WT0HROoAW0UWqLmwvE7srhw_YAbs89pe7phBkzmPAx5ZTDX5PpgptZ63XVKeoViGrRC16kghHNSe-ngxHq8sFweSskh_vEomLNG49GcNfIfnONlbQ</recordid><startdate>2020</startdate><enddate>2020</enddate><creator>Noel, Jonathan</creator><creator>Kral, Daniel</creator><creator>Lovasz, Laszlo Miklos</creator><creator>Sosnovec, Jakub</creator><general>Diamond Open Access Journals</general><scope>AAYXX</scope><scope>CITATION</scope><scope>DOA</scope></search><sort><creationdate>2020</creationdate><title>Finitely forcible graphons with an almost arbitrary structure</title><author>Noel, Jonathan ; Kral, Daniel ; Lovasz, Laszlo Miklos ; Sosnovec, Jakub</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c290t-ca0f3bcfb4adb3c23b452e08faf19ac21f20407079157fd524a90abf497a934c3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Noel, Jonathan</creatorcontrib><creatorcontrib>Kral, Daniel</creatorcontrib><creatorcontrib>Lovasz, Laszlo Miklos</creatorcontrib><creatorcontrib>Sosnovec, Jakub</creatorcontrib><creatorcontrib>University of Victoria</creatorcontrib><collection>CrossRef</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>Discrete analysis</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Noel, Jonathan</au><au>Kral, Daniel</au><au>Lovasz, Laszlo Miklos</au><au>Sosnovec, Jakub</au><aucorp>University of Victoria</aucorp><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Finitely forcible graphons with an almost arbitrary structure</atitle><jtitle>Discrete analysis</jtitle><date>2020</date><risdate>2020</risdate><issn>2397-3129</issn><eissn>2397-3129</eissn><abstract>A basic result from the theory of quasirandom graphs, due to Andrew Thomason, is that if is a graph with vertices and density , and if the number of 4-cycles in is approximately , then resembles a random graph of the same density. In particular, between any two sets and of vertices the number of edges is approximately . (Here, “approximately” means "to within a small fraction of , so the statement is non-trivial only for sets and that are not too small.)</abstract><pub>Diamond Open Access Journals</pub><doi>10.19086/da.12058</doi><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2397-3129
ispartof Discrete analysis, 2020
issn 2397-3129
2397-3129
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_6bbd95587d8a46e98ac58e44cc79d7c0
source ROAD: Directory of Open Access Scholarly Resources
title Finitely forcible graphons with an almost arbitrary structure
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-01T08%3A33%3A07IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-doaj_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Finitely%20forcible%20graphons%20with%20an%20almost%20arbitrary%20structure&rft.jtitle=Discrete%20analysis&rft.au=Noel,%20Jonathan&rft.aucorp=University%20of%20Victoria&rft.date=2020&rft.issn=2397-3129&rft.eissn=2397-3129&rft_id=info:doi/10.19086/da.12058&rft_dat=%3Cdoaj_cross%3Eoai_doaj_org_article_6bbd95587d8a46e98ac58e44cc79d7c0%3C/doaj_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c290t-ca0f3bcfb4adb3c23b452e08faf19ac21f20407079157fd524a90abf497a934c3%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