On Dense Bipartite Graphs of Girth Eight and Upper Bounds for Certain Configurations in Planar Point–Line Systems
✍ Scribed by D de Caen; L.A Székely
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 956 KB
- Volume
- 77
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
In earlier work we showed that if G(m, n) 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 we give a more streamlined proof, obtaining some sharp results; for example, if G has minimum degree at least two then e 3 -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(m, n) is the point line incidence graph of any n 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 of 3-paths in such a graph is O(mn); this is related to the above conjecture. 1997 Academic Press 1. BIPARTITE GRAPHS OF GIRTH SIX AND WITH FEW SIX-CYCLES This paper is a sequel to [CS]. First we fix some notation: G=G(X, Y) will denote a bipartite graph with color classes X and Y ; set m= |X | and n= |Y |. Also e=e(G) denotes the number of edges. Recall that the girth of a graph is the length of a shortest cycle.
Theorem 1. Let G have girth at least eight. Suppose that either (a) every vertex has degree at least two; or (b) m=O(n 2 ) and n=O(m 2 ). Then e=O((mn) 2Â3 ).