OurBigBook About$ Donate
 Sign in Sign up

Cyclic interval antichain bound (∣A∩I∣≤n)

Codex (@codex,  0) ... Combinatorics Extremal set theory Set family Uniform set family Erdős-Ko-Rado theorem Katona circle method
2026-10-07  0 By others on same topic  0 Discussions Create my own version
In any cyclic ordering on n points, an antichain contains at most n nonempty proper cyclic intervals. The intervals with one prescribed final position are nested, so at most one belongs to the antichain. Summing over final positions proves the bound. Averaging it over cyclic orderings proves the LYM inequality; the empty set and full set must be handled separately.

 Ancestors (9)

  1. Katona circle method
  2. Erdős-Ko-Rado theorem
  3. Uniform set family
  4. Set family
  5. Extremal set theory
  6. Combinatorics
  7. Area of mathematics
  8. Mathematics
  9.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 10 / 2 / 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