Supersaturation problem for color-critical graphs
<p dir="ltr">The <i>Turán function</i> ex ( <i>n , F</i> ) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2017
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513522150408192 |
|---|---|
| author | Oleg Pikhurko (23277277) |
| author2 | Zelealem B. Yilma (23275579) |
| author2_role | author |
| author_facet | Oleg Pikhurko (23277277) Zelealem B. Yilma (23275579) |
| author_role | author |
| dc.creator.none.fl_str_mv | Oleg Pikhurko (23277277) Zelealem B. Yilma (23275579) |
| dc.date.none.fl_str_mv | 2017-01-20T12:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1016/j.jctb.2016.12.001 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/Supersaturation_problem_for_color-critical_graphs/31446055 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Mathematical sciences Applied mathematics Pure mathematics Extremal graph theory Removal lemma Supersaturation Turán function |
| dc.title.none.fl_str_mv | Supersaturation problem for color-critical graphs |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">The <i>Turán function</i> ex ( <i>n , F</i> ) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine<i> h </i><sub><em>F</em></sub><i> </i>( <i>n , q </i>) , the minimum number of copies of F that a graph with n vertices and ex ( <i>n , F</i> ) + <i>q</i> edges can have. We determine <i>h F</i> ( <i>n , q </i>) asymptotically when F is color-critical (that is, F contains an edge whose deletion reduces its chromatic number) and <i>q</i> = o ( n<sup>2</sup> ) . Determining the exact value of h F ( <i>n , q </i>) seems rather difficult. For example, let c 1 be the limit superior of q / n for which the extremal structures are obtained by adding some q edges to a maximum F-free graph. The problem of determining c 1 for cliques was a well-known question of Erdős that was solved only decades later by Lovász and Simonovits. Here we prove that c 1 > 0 for every color-critical F. Our approach also allows us to determine c 1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.</p><h2 dir="ltr">Other Information</h2><p dir="ltr">Published in: Journal of Combinatorial Theory, Series B<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1016/j.jctb.2016.12.001" target="_blank">https://dx.doi.org/10.1016/j.jctb.2016.12.001</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_2f5cbe33ca6fc056acab096a7390c422 |
| identifier_str_mv | 10.1016/j.jctb.2016.12.001 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/31446055 |
| publishDate | 2017 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | Supersaturation problem for color-critical graphsOleg Pikhurko (23277277)Zelealem B. Yilma (23275579)Mathematical sciencesApplied mathematicsPure mathematicsExtremal graph theoryRemoval lemmaSupersaturationTurán function<p dir="ltr">The <i>Turán function</i> ex ( <i>n , F</i> ) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine<i> h </i><sub><em>F</em></sub><i> </i>( <i>n , q </i>) , the minimum number of copies of F that a graph with n vertices and ex ( <i>n , F</i> ) + <i>q</i> edges can have. We determine <i>h F</i> ( <i>n , q </i>) asymptotically when F is color-critical (that is, F contains an edge whose deletion reduces its chromatic number) and <i>q</i> = o ( n<sup>2</sup> ) . Determining the exact value of h F ( <i>n , q </i>) seems rather difficult. For example, let c 1 be the limit superior of q / n for which the extremal structures are obtained by adding some q edges to a maximum F-free graph. The problem of determining c 1 for cliques was a well-known question of Erdős that was solved only decades later by Lovász and Simonovits. Here we prove that c 1 > 0 for every color-critical F. Our approach also allows us to determine c 1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.</p><h2 dir="ltr">Other Information</h2><p dir="ltr">Published in: Journal of Combinatorial Theory, Series B<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1016/j.jctb.2016.12.001" target="_blank">https://dx.doi.org/10.1016/j.jctb.2016.12.001</a></p>2017-01-20T12:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1016/j.jctb.2016.12.001https://figshare.com/articles/journal_contribution/Supersaturation_problem_for_color-critical_graphs/31446055CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/314460552017-01-20T12:00:00Z |
| spellingShingle | Supersaturation problem for color-critical graphs Oleg Pikhurko (23277277) Mathematical sciences Applied mathematics Pure mathematics Extremal graph theory Removal lemma Supersaturation Turán function |
| status_str | publishedVersion |
| title | Supersaturation problem for color-critical graphs |
| title_full | Supersaturation problem for color-critical graphs |
| title_fullStr | Supersaturation problem for color-critical graphs |
| title_full_unstemmed | Supersaturation problem for color-critical graphs |
| title_short | Supersaturation problem for color-critical graphs |
| title_sort | Supersaturation problem for color-critical graphs |
| topic | Mathematical sciences Applied mathematics Pure mathematics Extremal graph theory Removal lemma Supersaturation Turán function |