Transitive Relations on Finite Sets of Size n

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Relations
Click For Summary
SUMMARY

The discussion centers on the enumeration of transitive binary relations on finite sets of size n. It establishes that there is no direct formula available for calculating the number of such relations. Participants referenced a resource from Inria that provides further insights into the topic, specifically focusing on posets and their properties.

PREREQUISITES
  • Understanding of binary relations
  • Familiarity with transitive properties in mathematics
  • Basic knowledge of finite set theory
  • Awareness of partially ordered sets (posets)
NEXT STEPS
  • Research the properties of transitive relations in depth
  • Explore the concept of partially ordered sets (posets)
  • Study combinatorial enumeration techniques
  • Investigate advanced topics in set theory related to finite sets
USEFUL FOR

Mathematicians, computer scientists, and students studying discrete mathematics or combinatorics who are interested in the properties and enumeration of relations on finite sets.

Dragonfall
Messages
1,023
Reaction score
5
How many transitive binary relations are there on a finite set of size n?
 
Physics news on Phys.org
There's no direct formula to calculate that, as far as I know. See http://algo.inria.fr/csolve/posets.pdf for some details.
 
Last edited by a moderator:

Similar threads

Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
485
Undergrad Formalizing infinity sets
  • · Replies 3 ·
Replies
3
Views
394
MHB Give a set and a relation that satisfies the properties
  • · Replies 10 ·
Replies
10
Views
2K
MHB Equivalence Relations: Solving & Proving Reflexivity, Symmetry & Transitivity
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad When does ## { n \choose k } ## represent set of lists?
  • · Replies 20 ·
Replies
20
Views
2K
Undergrad Supremum of a set, relations and order
  • · Replies 35 ·
2
Replies
35
Views
5K
Undergrad The set of nonzero values of pmf is at most countable
  • · Replies 3 ·
Replies
3
Views
4K
Undergrad If symmetric then transitive relation
  • · Replies 4 ·
Replies
4
Views
2K
Graduate The Blessings of Dimensionality and Hilbert's 6th Problem
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad How to determine if a set is a semiring or a ring?
  • · Replies 2 ·
Replies
2
Views
4K