ON DENSE BIPARTITE GRAPHS OF GIRTH-8 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 n o 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 pr oof, obtaining some sharp results; fur example, if G has minimum degre e at least two then e less than or equal to(3) root 2(mn)(2/3), and th is is a tight bound. Furthermore, one may allow O(mn) 6-cycles and sti ll 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 th e 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): th is is related to the above conjecture. (C) 1997 Academic Press.