On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar point-line systems

[摘要] In earlier work we showed that if G(m, ii) is a bipartite graph with no 4-cycles or 6-cycles, and if m < c(1)n(2) and n < c(2)m(2), then the number of edges e is O((mn)(2/3)). Here me give a more streamlined proof, obtaining some sharp results; fur example, if G has minimum degree at least two then e less than or equal to(3) root 2(mn)(2/3), and this is a tight bound. Furthermore, one may allow O(mn) 6-cycles and still obtain e=O((mn)(2/3)). This leads us to conjecture that, if G(in, n) is the point-line incidence graph of any it points and m lines in the plane, then the number of 6-cycles is O(mn). The main result of this paper is a proof that the number 3-paths in such a graph is O(mn): this is related to the above conjecture. (C) 1997 Academic Press.

[发布日期] 1997-02-01