Skip to content
DraconiticResearch
Search Sources API
186,546 studies31 sourcesUpdated 20 min ago
PreprintCC BY 4.0arXiv

On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts

  • Chunqiu Fang
  • Rongxing Xu
Open at sourcePDFDOICite

Abstract

Let G be a $3$-partite graph with k vertices in each part such that the bipartite graph induced by any two parts contains no cycle of length four. Fischer and Matoušek [J. Combin. Theory Ser. A, 2001] asked for the maximum number of triangles in such a graph. They obtained the lower bound (1−o(1))k3/2 and the upper bound k7/4+O(k3/2). Coulter, Matthews and Timmons [J. Combin. Theory Ser. B, 2018] later constructed such graphs using planar polynomials over finite fields and improved the lower bound to (1−o(1))k5/3. In this note, we use a new triple of planar polynomials and further improve the lower bound to (1−o(1))k17/10.

Related

  1. On the minimum number of triangles in balanced tripartite graphs with large minimum degree
    Chunqiu Fang, Rongxing Xu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. The maximum number of triangles in regular graphs
    Ya-Hong Chen, Shi-Cai Gong, Changhong Lu +2
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The maximum number of Hamiltonian cycles in tournaments
    Alexander Divoux, Shouda Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Bounds on the maximum number of limit cycles of piecewise linear Lienard systems II. The discontinuous case
    Hebai Chen, Jie Jin, Shu Li +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsDynamical systemsarXiv
  5. Bounds on the maximum number of limit cycles of piecewise linear Lienard systems I. The continuous case
    Shiyu Cai, Hebai Chen, Jie Jin +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{fang2026maximum,
  title = {{On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts}},
  author = {Chunqiu Fang and Rongxing Xu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.06594},
  eprint = {2609.06594},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.06594},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts
AU  - Chunqiu Fang
AU  - Rongxing Xu
PY  - 2026
DA  - 2026/09/06
PB  - arXiv
DO  - 10.48550/arxiv.2609.06594
UR  - https://arxiv.org/abs/2609.06594
AB  - Let G be a $3$-partite graph with k vertices in each part such that the bipartite graph induced by any two parts contains no cycle of length four. Fischer and Matoušek [J. Combin. Theory Ser. A, 2001] asked for the maximum number of triangles in such a graph. They obtained the lower bound (1−o(1))k^3/2 and the upper bound k^7/4+O(k^3/2). Coulter, Matthews and Timmons [J. Combin. Theory Ser. B, 2018] later constructed such graphs using planar polynomials over finite fields and improved the lower bound to (1−o(1))k^5/3. In this note, we use a new triple of planar polynomials and further improve the lower bound to (1−o(1))k^17/10.
ER  -