Triangles in C5-free graphs and hypergraphs of girth six

Beka Ergemlidze; Abhishek Methuku

doi:10.1002/jgt.22723

Triangles in C₅-free graphs and hypergraphs of girth six

Research output: Contribution to journal › Article › peer-review

Abstract

We introduce a new approach and prove that the maximum number of triangles in a (Formula presented.) -free graph on (Formula presented.) vertices is at most (Formula presented.) We show a connection to (Formula presented.) -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced- (Formula presented.) -free and (Formula presented.) -free graph.

Original language	English (US)
Pages (from-to)	26-39
Number of pages	14
Journal	Journal of Graph Theory
Volume	99
Issue number	1
Early online date	Jul 26 2021
DOIs	https://doi.org/10.1002/jgt.22723
State	Published - Jan 2022
Externally published	Yes

Keywords

Berge hypergraphs
generalized Turán
triangles

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Online availability

10.1002/jgt.22723License: CC BY

Library availability

Discover UIUC Full Text

Cite this

@article{e51898b41b044395bcf439ca716949c6,

title = "Triangles in C5-free graphs and hypergraphs of girth six",

abstract = "We introduce a new approach and prove that the maximum number of triangles in a (Formula presented.) -free graph on (Formula presented.) vertices is at most (Formula presented.) We show a connection to (Formula presented.) -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced- (Formula presented.) -free and (Formula presented.) -free graph.",

keywords = "Berge hypergraphs, generalized Tur{\'a}n, triangles",

author = "Beka Ergemlidze and Abhishek Methuku",

note = "We thank the anonymous referees for their careful reading of our paper and for their helpful comments. The research of the authors was partially supported by the National Research, Development and Innovation Office—NKFIH, grant K116769. The research of the second author was also partially supported by the EPSRC grant number EP/S00100X/1 (A. Methuku).",

year = "2022",

month = jan,

doi = "10.1002/jgt.22723",

language = "English (US)",

volume = "99",

pages = "26--39",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Triangles in C5-free graphs and hypergraphs of girth six

AU - Ergemlidze, Beka

AU - Methuku, Abhishek

N1 - We thank the anonymous referees for their careful reading of our paper and for their helpful comments. The research of the authors was partially supported by the National Research, Development and Innovation Office—NKFIH, grant K116769. The research of the second author was also partially supported by the EPSRC grant number EP/S00100X/1 (A. Methuku).

PY - 2022/1

Y1 - 2022/1

N2 - We introduce a new approach and prove that the maximum number of triangles in a (Formula presented.) -free graph on (Formula presented.) vertices is at most (Formula presented.) We show a connection to (Formula presented.) -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced- (Formula presented.) -free and (Formula presented.) -free graph.

AB - We introduce a new approach and prove that the maximum number of triangles in a (Formula presented.) -free graph on (Formula presented.) vertices is at most (Formula presented.) We show a connection to (Formula presented.) -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced- (Formula presented.) -free and (Formula presented.) -free graph.

KW - Berge hypergraphs

KW - generalized Turán

KW - triangles

UR - http://www.scopus.com/inward/record.url?scp=85111654907&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85111654907&partnerID=8YFLogxK

U2 - 10.1002/jgt.22723

DO - 10.1002/jgt.22723

M3 - Article

AN - SCOPUS:85111654907

SN - 0364-9024

VL - 99

SP - 26

EP - 39

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -