Pigeonhole Principle and Equivalence Classes

Question

Let $A$ be a finite set with $n \geq 4$ elements and let $\rho$ be an equivalence relation on $A$. Suppose that there are exactly four equivalence classes: $C_1, C_2, C_3, C_4$. Moreover we know that $\mid C_1\mid = \mid C_2\mid = 1$. Let $a \in A$ be a fixed element that we know is in $C_3$.

What is the maximum number of ordered pairs $(x,y) \in \rho$ in which $a$ can occur $(a=x, a=y, a=x=y$)?

I'm iffy on equivalence classes, so in your answer could you help explain that as well. I'd appreciate the thought process behind solving this problem rather than just the answer since I want to learn how to do this.

Answer 1

$\left|\left\{ \left(x,y\right)\in\rho\mid x=a\right\} \right|=\left|\left\{ \left(x,y\right)\in\rho\mid y=a\right\} \right|=|C_3|$ and $\left|\left\{ \left(x,y\right)\in\rho\mid x=a\right\} \cap\left\{ \left(x,y\right)\in\rho\mid y=a\right\} \right|=\left|\left\{ a,a\right\} \right|=1$

This leads to $\left|\left\{ \left(x,y\right)\in\rho\mid x=a\vee y=a\right\} \right|=2|C_3|-1$

addendum:

Denoting $P=\left\{ \left(x,y\right)\in\rho\mid x=a\right\} $ and $Q=\left\{ \left(x,y\right)\in\rho\mid y=a\right\} $ you want to find $\left|P\cup Q\right|$.

Note that $P\cap Q=\left\{ \left(a,a\right)\right\} $ so that $\left|P\cap Q\right|=1$

Note that $\left(x,y\right)\in P\iff x=a\wedge y\in C_{3}$ telling us that $\left|P\right|=\left|C_{3}\right|$. Actually $P=\{a\}\times C_3$.

Note that $\left(x,y\right)\in Q\iff x\in C_{3}\wedge y=a$ telling us that $\left|Q\right|=\left|C_{3}\right|$. Actually $Q=C_3\times\{a\}$.

So we end up with $\left|P\cup Q\right|=\left|P\right|+\left|Q\right|-\left|P\cap Q\right|=\left|C_{3}\right|+\left|C_{3}\right|-1=2\left|C_{3}\right|-1$

Answer 2

If each element is considered as a vertex in graph, and each ordered pair as a directed edge, then each equivalence class will look like a clique(complete graph) in this graph.

Since a is in C3, it can only have relation with elements of C3. In a complete directed graph, max no. of edges from a vertex = 2(n-1) + 1 self loop.(self loop since reflexive)

Thus your answer is $2*(|C3|-1)+1 = 2*|C3|-1$.

Answer 3

The question does not have enough information to apply pigeonhole principle.