Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Sharp bounds for decomposing graphs into edges and triangles

Tools
- Tools
+ Tools

Blumenthal, Adam, Lidický, Bernard, Pehova, Yanitsa, Pfende, Florian, Pikhurko, Oleg and Volec, Jan (2021) Sharp bounds for decomposing graphs into edges and triangles. Combinatorics, Probability and Computing, 30 (2). 271 -287. doi:10.1017/S0963548320000358 ISSN 0963-5483.

[img]
Preview
PDF
WRAP-sharp-bounds-for-decomposing-graphs-into-edges-and-triangles-Pikhurko-2020.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (497Kb) | Preview
[img] PDF
WRAP-sharp-bounds-decomposing-graphs-edges-triangles-Pikhurko-2020.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (1062Kb)
Official URL: http://dx.doi.org/10.1017/S0963548320000358

Request Changes to record.

Abstract

For a real constant α, let π α 3 (G) be the minimum of twice the number of K2’s plus α times the number of K3’s over all edge decompositions of G into copies of K2 and K3, where Kr denotes the complete graph on r vertices. Let π α 3 (n) be the maximum of π α 3 (G) over all graphs G with n vertices. The extremal function π 3 3 (n) was first studied by Gy˝ori and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315– 320]. In a recent progress on this problem, Kr´al’, Lidick´y, Martins and Pehova [Decomposing graphs into edges and triangles, Combin. Prob. Comput. 28 (2019) 465–472] proved via flag algebras that π 3 3 (n) 6 (1/2+o(1))n 2 . We extend their result by determining the exact value of π α 3 (n) and the set of extremal graphs for all α and sufficiently large n. In particular, we show for α = 3 that Kn and the complete bipartite graph K⌊n/2⌋,⌈n/2⌉ are the only possible extremal examples for large n.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH): Decomposition (Mathematics), Graph theory, Triangle, Combinatorial analysis
Journal or Publication Title: Combinatorics, Probability and Computing
Publisher: Cambridge University Press
ISSN: 0963-5483
Official Date: March 2021
Dates:
DateEvent
March 2021Published
12 October 2020Available
4 June 2020Accepted
Volume: 30
Number: 2
Page Range: 271 -287
DOI: 10.1017/S0963548320000358
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access (Creative Commons)
Date of first compliant deposit: 3 August 2020
Date of first compliant Open Access: 16 February 2021
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
DMS-1600390National Science Foundationhttp://dx.doi.org/10.13039/501100008982
DMS-1855653National Science Foundationhttp://dx.doi.org/10.13039/501100008982
648509[ERC] Horizon 2020 Framework Programmehttp://dx.doi.org/10.13039/100010661
DMS-1600483National Science Foundationhttp://dx.doi.org/10.13039/501100008982
DMS-1855622National Science Foundationhttp://dx.doi.org/10.13039/501100008982
306493European Research Councilhttp://dx.doi.org/10.13039/501100000781
EP/K012045/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
RPG2018-424Leverhulme Trusthttp://dx.doi.org/10.13039/501100000275
Marie Skłodowska-Curie grant agreement 800607[ERC] Horizon 2020 Framework Programmehttp://dx.doi.org/10.13039/100010661
Related URLs:
  • Publisher
Open Access Version:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us