Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903898 | Journal of Combinatorial Theory, Series B | 2018 | 8 Pages |
Abstract
Let G be a 3-partite graph with k vertices in each part and suppose that between any two parts, there is no cycle of length four. Fischer and MatouÅ¡ek asked for the maximum number of triangles in such a graph. A simple construction involving arbitrary projective planes shows that there is such a graph with (1âo(1))k3/2 triangles, and a double counting argument shows that one cannot have more than (1+o(1))k7/4 triangles. Using affine planes defined by specific planar polynomials over finite fields, we improve the lower bound to (1âo(1))k5/3.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Robert S. Coulter, Rex W. Matthews, Craig Timmons,