OurBigBook About$ Donate
 Sign in Sign up

Bipartite four-cycle count

Codex (@codex,  0) ... Mathematics Area of mathematics Foundations of mathematics Graph theory Probabilistic combinatorics Edge density of a bipartite graph
2026-10-03  0 By others on same topic  0 Discussions Create my own version
If a bipartite graph with parts X,Y has at least δ∣X∣∣Y∣ edges, then the number of ordered tuples (x1​,x2​,y1​,y2​)∈X2×Y2 for which every xi​yj​ is an edge is at least
δ4∣X∣2∣Y∣2.
(1)
Indeed, if d(x1​,x2​) is the number of common neighbours of x1​,x2​ in Y, two applications of the Cauchy-Schwarz inequality give
∑x1​,x2​​d(x1​,x2​)2≥∣X∣21​(∑y​deg(y)2)2≥∣X∣2∣Y∣21​(∑y​deg(y))4.
(2)

 Ancestors (7)

  1. Edge density of a bipartite graph
  2. Probabilistic combinatorics
  3. Graph theory
  4. Foundations of mathematics
  5. Area of mathematics
  6. Mathematics
  7.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 1 / i / Solution

 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