Geodesic
Sharp bounds for decomposing graphs into edges and triangles
Adam Blumenthal1 ; Bernard Lidický1 ; Oleg Pikhurko2 ; Yanitsa Pehova2 ; Florian Pfender3 ; Jan Volec4 ; Adam Blumenthal ; Bernard Lidický ; Oleg Pikhurko ; Yanitsa Pehova ; Florian Pfender ; Jan Volec
1Department of Mathematics, Iowa State University, Ames, IA, USA
2Mathematics Institute, University of Warwick, Coventry, UK
3Department of Mathematical and Statistical Sciences, University of Colorado Denver, USA
4Mathematics and Science Center, Atlanta, USA
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 463-468 
Adam Blumenthal; Bernard Lidický; Oleg Pikhurko; Yanitsa Pehova; Florian Pfender; Jan Volec; Adam Blumenthal; Bernard Lidický; Oleg Pikhurko; Yanitsa Pehova; Florian Pfender; Jan Volec. Sharp bounds for decomposing graphs into edges and triangles. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 463-468. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a16/
@article{AMUC_2019_88_3_a16,
     author = {Adam Blumenthal and Bernard Lidick\'y and Oleg Pikhurko and Yanitsa Pehova and Florian Pfender and Jan Volec and Adam Blumenthal and Bernard Lidick\'y and Oleg Pikhurko and Yanitsa Pehova and Florian Pfender and Jan Volec},
     title = { Sharp bounds for decomposing graphs into edges and triangles},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {463--468},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a16/}
}
TY  - JOUR
AU  - Adam Blumenthal
AU  - Bernard Lidický
AU  - Oleg Pikhurko
AU  - Yanitsa Pehova
AU  - Florian Pfender
AU  - Jan Volec
AU  - Adam Blumenthal
AU  - Bernard Lidický
AU  - Oleg Pikhurko
AU  - Yanitsa Pehova
AU  - Florian Pfender
AU  - Jan Volec
TI  - Sharp bounds for decomposing graphs into edges and triangles
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 463
EP  - 468
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a16/
ID  - AMUC_2019_88_3_a16
ER  - 
%0 Journal Article
%A Adam Blumenthal
%A Bernard Lidický
%A Oleg Pikhurko
%A Yanitsa Pehova
%A Florian Pfender
%A Jan Volec
%A Adam Blumenthal
%A Bernard Lidický
%A Oleg Pikhurko
%A Yanitsa Pehova
%A Florian Pfender
%A Jan Volec
%T Sharp bounds for decomposing graphs into edges and triangles
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 463-468
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a16/
%F AMUC_2019_88_3_a16

Voir la notice de l'article provenant de la source Comenius University

Let pi3(G) be the minimum of twice the number of edges plus three times the number of triangles over all edge-decompositions of G into copies of K2 and K3. We are interested in the value of pi3(n), the maximum of pi3(G) over graphs G with n vertices. This specific extremal function was first studied by Gyori and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320], who showed that pi3(n)<9n2/16. In a recent advance on this problem, Kral, Lidicky, Martins and Pehova [arXiv:1710:08486] proved via flag algebras that pi3(n)<(1/2+o(1))n2, which is tight up to the o(1) term. We extend their proof by giving the exact value of pi3(n) for large n, and we show that Kn and Kn/2,n/2 are the only extremal examples.