6
$\begingroup$

I was trying to write an equation that showed that three elements of a set were all equal to one another without relying on the transitive property.

For some set of elements ${\{A, B, C}\}$, if the transitive property holds then the equation that shows that they are all equal to one another can be written as follows:

$$A=B=C$$

Assuming that the transitive property holds, the relation $A=C$ is implied without being written.

However, if the transitive property does not hold, the shortest way to write this equivalence equation is as follows:

$$A=B=C=A$$

For 3 elements in a set there are only 3 relationships (between two elements) which means the equation above is (one of) the shortest way of representing all the equivalence relationships as it only uses three equal signs.

I was then wondering whether I could write a similar equation for a set of four elements. The shortest one that I could find is the following example:

$$A=B=C=D=A=C=B=D$$

The above equation is a bit problematic as the relation $B=C$ is written twice which means the above equation requires 7 equal signs even though there are only 6 unique relationships between two elements in the set. I don't think it is possible to represent the equation with only 6 equal signs though.

In contrast, I was able to find to find the shortest length for a set of 5 elements as shown below:

$$A=B=C=D=E=A=C=E=B=D=A$$

There are only 10 pairs in the set and the length only uses 10 equal signs thus avoiding any redundant writing.

$$$$

I am pretty sure that all sets with an odd number of elements can be represented without redundancy. I am pretty sure that sets of even numbers greater than 2 require at least one redundant written relationship but am unsure of how much redundant writing is required for even numbers after 4.

Is there a way to determine the necessary amount of redundant writing for the even numbers greater than 2?

$\endgroup$
1
  • 2
    $\begingroup$ If you're allowed quantifiers, the shortest way is $\forall A B \in X. A = B$. If you're allowed to draw in higher dimensions, you can draw an $n$-simplex with elements as vertices and equalities as edges. $\endgroup$ Commented yesterday

2 Answers 2

Reset to default
11
$\begingroup$

The complete graph on a set is a graph whose vertices are the elements of the set and whose edges are unordered pairs of distinct elements from the set. We can interpret each edge as the equality between the elements that form its endpoints; then a chain of equalities is the same as a path on this graph. We want to find a chain that includes all possible equalities between elements of the set; that’s equivalent to finding an Eulerian path on the complete graph.

It’s well known that a connected graph has an Eulerian path if and only if there are at most two vertices with odd degree. In particular, complete graphs on $n$ vertices (for which each vertex has degree $n-1$) always have Eulerian paths when $n$ is odd, but never have Eulerian paths when $n\ge4$ is even.

I think it’s been shown that you can get away with $\frac n2-1$ duplicated edges (equalities) when $n$ is even.

$\endgroup$
1
  • 1
    $\begingroup$ For the "I think it's been shown...": You have n vertices with odd degree and need to reduce that to 2 such vertices. Each duplicated edge can increase by 1 the degree of its 2 ends, so you need $(n-2)/2$ of them. $\endgroup$ Commented 15 hours ago
6
$\begingroup$

I was trying to write an equation that showed that three elements of a set were all equal to one another without relying on the transitive property. ...
However, if the transitive property does not hold, the shortest way to write this equivalence equation is as follows: ...

Note that an equivalence relation is, by definition, reflexive, symmetric and transitive. If the transitive property does not hold, then one no longer has an equivalence relation.

One way to understand the question is to discuss the relation "is not equal to" instead. This relation is not transitive: $a\ne b\ne c$ does not imply $a\ne c$. One can ask for the minimum length of a single chain of inequalities implying $n$ values are all pairwise distinct.

To add some illustrations to the answer by @GregMartin:

A connected graph has an Eulerian trail if and only if the number of odd-degree vertices is either 0 or 2.

The complete graph $K_{2\cdot n+1}$ is connected and has zero odd-degree vertices; hence it has an Eulerian trail. The example below allows writing the chain of inequalities $$ A\ne B\ne C\ne D\ne E\ne A\ne C\ne E\ne B\ne D\ne A $$ (10 inequality tests):

k5

The complete graph $K_{2\cdot n}$ is connected and has $2\cdot n$ odd-degree vertices; it does not have an Eulerian trail for $n>1$. Duplicating one edge (replacing one edge by two parallel edges) can decrease the number of odd-degree vertices by 2; therefore at least $n-1$ edge duplications are needed to get a multigraph with 2 odd-degree vertices. Choose a perfect matching in $K_{2\cdot n}$, and duplicate $n-1$ out of $n$ edges in the matching; the resulting multigraph has $2\cdot n - 2\cdot\left(n-1\right) = 2$ odd-degree vertices, and does have an Eulerian trail. In the example below, the chain of inequalities $$ B \ne A \ne F \ne A \ne C \ne D \ne C \ne B \ne D \ne F \ne B \ne E \ne A \ne D \ne E \ne C \ne F \ne E $$ (17 inequality tests) corresponds to an Eulerian trail in the multigraph with $\frac{6\cdot 5}{2}+2=17$ edges.

k6

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.