For fixed and positive density threshold , sufficiently regular pairwise dense bipartite graphs between disjoint equal-sized vertex classes contain at least transversal cliques, for some . A greedy embedding maintains common neighbourhoods and discards the small set of vertices with atypical degrees into them. The constants depend only on .
If three disjoint vertex classes have size , and their three pairs are -regular pairs of vertex sets of edge density of a bipartite graph at least , where and , they contain at least the displayed number of transversal triangles in a graph. All but vertices in the first class have at least neighbours in both other classes. Regularity between those two neighbour sets supplies the third edge. This strengthens a mere triangle embedding lemma for regular pairs to a cubic lower count.

Articles by others on the same topic (0)

There are currently no matching articles.