GENERALIZED ON COMPLEXITY OF SET OF BIPARTITE GRAPHS AND APPLICATIONS

Abstract

In this present paper The complexity x_c(P) of a P is the minimum number of facets of a that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let G be the convex hull of the sets of G. Since G is perfect, it is easy to see that nxc(G)  n + m. We improve both of these bounds. For the upper bound, we show that xc(G) is O(), which is an improvement when G has quadratically many edges. For the lower bound, we prove that xc(G) is Ω(log n) when G is the incidence graph of a finite projective plane. We also provide the obvious upper and lower bounds are both essentially fixed.