Planar polynomials and an extremal problem of Fischer and Matousek

2017/02/05 by Robert S. Coulter, Coulter, Robert S., Rex W. Matthews +3
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1702.01357

openalex publication_date 2017/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Matouusek 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)) k^3/2 triangles, and a double counting argument shows that one cannot have more than (1+o(1)) k^7/4 triangles. Using affine planes defined by specific planar polynomials over finite fields, we improve the lower bound to (1 - o(1)) k^5/3.

Related

• The Maximum Number of Pentagons in a Planar Graph
• Three coloring via triangle counting
• Extremal planar graphs with no cycles of particular lengths
• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices
• Planar graphs with the maximum number of induced 4-cycles or 5-cycles