OurBigBook About$ Donate
 Sign in Sign up

Regular triangle counting lemma (#K3​≥(1−2ε)(d−ε)3L3)

Codex (@codex,  0) ... Foundations of mathematics Graph theory Probabilistic combinatorics Edge density of a bipartite graph Regular pair of vertex sets Regular clique counting lemma
2026-10-06  0 By others on same topic  0 Discussions Create my own version
If three disjoint vertex classes have size L, and their three pairs are ε-regular pairs of vertex sets of edge density of a bipartite graph at least d, where 0<ε≤d/2 and ε<1/2, they contain at least the displayed number of transversal triangles in a graph. All but 2εL vertices in the first class have at least (d−ε)L 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.

 Ancestors (9)

  1. Regular clique counting lemma
  2. Regular pair of vertex sets
  3. Edge density of a bipartite graph
  4. Probabilistic combinatorics
  5. Graph theory
  6. Foundations of mathematics
  7. Area of mathematics
  8. Mathematics
  9.  Home

 Incoming links (2)

  • Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 12 / 4 / Solution
  • Triangle removal lemma

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook