# Antisymmetry Definition in SageMath for DiGraphs

135 views

### Samuel Lubliner

Mar 11, 2024, 5:24:20 PMMar 11
to sage-support
I've been exploring the concept of antisymmetry in DiGraphs within SageMath and noticed a discrepancy between the standard mathematical definition of an antisymmetric relation and SageMath's implementation for DiGraphs. I'm looking for some clarification or insight into this observation.

The standard definition of antisymmetry in a relation R states:
if aRb and bRa, then a=b.

In contrast, Sage seems to interpret antisymmetry for DiGraphs in a way that emphasizes the absence of reciprocal paths, which is more restrictive.

To illustrate, I ran a few tests within a SageCell to understand how antisymmetric() behaves with different graph configurations:

A graph with a loop and no reciprocal edges, which should be antisymmetric:
```
DiGraph([(1, 2), (3, 1), (1, 1)], loops=True).antisymmetric()  # Expected True, Returns True
```

A graph with a direct reciprocal relationship (1,2) and (2,1), clearly violating antisymmetry:
```
DiGraph([(1, 2), (2, 1), (3, 1), (1, 1)], loops=True).antisymmetric()  # Expected False, Returns False
```

This third example is interesting because, under the standard mathematical definition, antisymmetry focuses on direct reciprocal relations between pairs of elements, not the existence of a path between vertices. Therefore, a cycle does not inherently violate antisymmetry unless there are direct reciprocal edges between any two vertices in the graph.
```
DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)]).antisymmetric() # Expected True, Returns False
```

Is SageMath's antisymmetric() method intentionally designed to consider the broader structure of the graph by evaluating paths rather than just direct edges to determine antisymmetry? It would be great to get some clarification on this and understand the rationale behind SageMath's implementation choice.

### Dima Pasechnik

Mar 11, 2024, 6:20:05 PMMar 11
On Mon, Mar 11, 2024 at 9:24 PM Samuel Lubliner <samlu...@gmail.com> wrote:
I've been exploring the concept of antisymmetry in DiGraphs within SageMath and noticed a discrepancy between the standard mathematical definition of an antisymmetric relation and SageMath's implementation for DiGraphs. I'm looking for some clarification or insight into this observation.

The standard definition of antisymmetry in a relation R states:
if aRb and bRa, then a=b.

In contrast, Sage seems to interpret antisymmetry for DiGraphs in a way that emphasizes the absence of reciprocal paths, which is more restrictive.

To illustrate, I ran a few tests within a SageCell to understand how antisymmetric() behaves with different graph configurations:

A graph with a loop and no reciprocal edges, which should be antisymmetric:
```
DiGraph([(1, 2), (3, 1), (1, 1)], loops=True).antisymmetric()  # Expected True, Returns True
```

A graph with a direct reciprocal relationship (1,2) and (2,1), clearly violating antisymmetry:
```
DiGraph([(1, 2), (2, 1), (3, 1), (1, 1)], loops=True).antisymmetric()  # Expected False, Returns False
```

This third example is interesting because, under the standard mathematical definition, antisymmetry focuses on direct reciprocal relations between pairs of elements, not the existence of a path between vertices. Therefore, a cycle does not inherently violate antisymmetry unless there are direct reciprocal edges between any two vertices in the graph.
```
DiGraph([(1, 2), (2, 3), (3, 4), (4, 1)]).antisymmetric() # Expected True, Returns False
```

you can check the docs, and see that Sage, essentially, calls directed acyclic graphs antisymmetric.
I.e. if there is a path from x to y then there is no path from y to x (assuming x!=y)

A graph represents an antisymmetric relation if the existence of a path
from a vertex `x` to a vertex `y` implies that there is not a path from
`y` to `x` unless `x = y`.

that's a more interesting, mathematically, definition, than mere absense of loops of length 2.

Is SageMath's antisymmetric() method intentionally designed to consider the broader structure of the graph by evaluating paths rather than just direct edges to determine antisymmetry? It would be great to get some clarification on this and understand the rationale behind SageMath's implementation choice.

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

### Hellen Colman

Mar 15, 2024, 6:08:34 PMMar 15
to sage-support
Dima,

Thank you for taking the time to answer the question posted by my student Samuel.

Let me just clarify the main point of his question just in case we can still obtain a helpful answer. Essentially the question is: Why is Sage calling "antisymmetric" to a property that is not the standard antisymmetric property?

We would appreciate if anybody has an insight on why is this choice of name since we are writing a user friendly guide to Sage for undergraduate students trying to use Sage in Discrete Math. So far, the paragraph in our book reads as: "We just learned the antisymmetric property for relations, now ask Sage if the following relation satisfies antisymmetric property. Be aware that Sage is not checking for the absence of cycles of length 2 as we just learned, but for the absence of cycles of any length. This is because..." we would like to finish this phrase with a meaningful reason - if we found out why.

The fact that this other property is "more mathematically interesting"  does not seem to justify a change of name. In my field, to check for homotopically equivalent graphs is more interesting than checking for isomorphism. Yet, I don't expect Sage to check if my graphs are homotopically equivalent when I use the is_isomorphic function.

My student Sam did read carefully the documentation that is why he discovered that Sage is using path instead of edge, as in the standard definition of antisymmetric relation in the paragraph quoted:

A graph represents an antisymmetric relation if the existence of a path from a vertex x to a vertex y
implies that there is not a path from y to x unless x=y.

We would like to know why, so it can be incorporated in our book and enlighten next generations of undergraduate students trying to make sense of this documentation.

### Nils Bruin

Mar 15, 2024, 7:51:16 PMMar 15
to sage-support
On Friday 15 March 2024 at 15:08:34 UTC-7 Hellen Colman wrote:
Let me just clarify the main point of his question just in case we can still obtain a helpful answer. Essentially the question is: Why is Sage calling "antisymmetric" to a property that is not the standard antisymmetric property?

I agree that a relation gives rise to a graph, but I wouldn't presume that the standard notion of "antisymmetric" for relations would agree with that on graphs (or even that there would be a property of graphs that is called "antisymmetric).  So if there is something transferable to be learned for for students here it is perhaps that terminology is not perfectly aligned between different areas in mathematics. Given that the word "antisymmetric" is now taken to mean something specific for graphs (I assume whoever did that consulted some graph-theory books), it will have considerable inertia because changing it to something else would break backward compatibility.

If you feel strongly that a change in terminology would be beneficial, you could collect some references corroborating your proposed meaning. If someone else feels strongly enough about preserving the present meaning, they would likely counter with their own set of references. At that point hopefully a consensus would grow, with a (slight) preference for the status quo. If both notions have support, we'd likely look into a way of supporting both; probably by dangling the appropriate adjectives in front of "antisymmetric", like "edge_antisymmetric" and "path_antisymmetric" or something like that.

For your research, you might be interested in an is_homotopically_equivalent method.

### Dima Pasechnik

Mar 16, 2024, 8:42:23 AMMar 16
Dear Hellen, dear Nils,

On Fri, Mar 15, 2024 at 11:51 PM Nils Bruin <nbr...@sfu.ca> wrote:
On Friday 15 March 2024 at 15:08:34 UTC-7 Hellen Colman wrote:
Let me just clarify the main point of his question just in case we can still obtain a helpful answer. Essentially the question is: Why is Sage calling "antisymmetric" to a property that is not the standard antisymmetric property?

I agree that a relation gives rise to a graph, but I wouldn't presume that the standard notion of "antisymmetric" for relations would agree with that on graphs (or even that there would be a property of graphs that is called "antisymmetric).  So if there is something transferable to be learned for for students here it is perhaps that terminology is not perfectly aligned between different areas in mathematics. Given that the word "antisymmetric" is now taken to mean something specific for graphs (I assume whoever did that consulted some graph-theory books), it will have considerable inertia because changing it to something else would break backward compatibility.

I went to look for some references for "antisymmetric graph", and indeed Sage's definition
doesn't agree with what I found:
<https://www.sciencedirect.com/science/article/pii/0012365X75900928> and
<https://arxiv.org/pdf/2208.10727.pdf>

I dug up the original vintage commit where this function was introduced:
(fortunately, with git it's just
git log -S "def antisymmetric(self)"
)
Author: Jason Grout <jason...@creativetrax.com>
Date:   Tue Sep 25 18:46:29 2007 -0500

[...]
+    def transitive_closure(self):
+        r"""
+        Modifies a graph to be its transitive closure and returns the
+        modified graph.
[...]
+    def antisymmetric(self):
+        r"""
+        Returns True if the relation given by the graph is
+        antisymmetric and False otherwise.
+
+        A graph represents an antisymmetric relation if there being a
+        path from a vertex x to a vertex y implies that there is not a
+        path from y to x unless x=y.
[...]

That is, "antisymmetric" was just a sloppy naming for a different to "antisymmetric graph".

I propose the following course of action:

1) copy antisymmetric() to antisymmetric_relation(); deprecate antisymmetric();
introduce  antisymmetric_graph(), to mean the standard definition as Hellen points at.
2) after the deprecation period, make antisymmetric() a copy of antisymmetric_graph(),
and deprecate the latter
3) after the (2nd) deprecation period, remove antisymmetric_graph()
So in the end, in about 2 years, there will be antisymmetric() - conforming to the standard - and antisymmetric_relation()
- the original code for old antisymmetric()

Cheers
Dima

If you feel strongly that a change in terminology would be beneficial, you could collect some references corroborating your proposed meaning. If someone else feels strongly enough about preserving the present meaning, they would likely counter with their own set of references. At that point hopefully a consensus would grow, with a (slight) preference for the status quo. If both notions have support, we'd likely look into a way of supporting both; probably by dangling the appropriate adjectives in front of "antisymmetric", like "edge_antisymmetric" and "path_antisymmetric" or something like that.

For your research, you might be interested in an is_homotopically_equivalent method.

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.

### Dima Pasechnik

Mar 16, 2024, 8:52:47 AMMar 16

### Hellen Colman

Mar 18, 2024, 9:45:17 AMMar 18
to sage-support
Nils,

Yes, that terminology is not perfectly aligned between different areas in mathematics is a good takeaway we will definitely mention in the book. Thank you!

In this case I understand that we are checking antisymmetric in a graph, but the most confusing part is that the documentation is explicitly stating:

"A graph represents an antisymmetric relation if ... "

It is not saying a graph is antisymmetric, but is introducing a new definition of antisymmetric relation.

I don't think that the issue is about relation or graph (both definitions are for graphs), so I like your suggested names "edge_antisymmetric" and "path_antisymmetric" momentarily because they emphasize the actual distinction, so I would suggest the following change in Dima's course of action:

1) copy antisymmetric() to antisymmetric_relation(); deprecate antisymmetric();
introduce  antisymmetric_graph(), to mean the standard definition as Hellen points at.

2) after the deprecation period, make antisymmetric() a copy of antisymmetric_graph(),
and deprecate the latter

3) after the (2nd) deprecation period, remove antisymmetric_graph()
So in the end, in about 2 years, there will be antisymmetric() - conforming to the standard - and antisymmetric_relation()
- the original code for old antisymmetric()

In the end there will be path_antisymmetric() and just antisymmetric(), both for graphs, where the latter corresponds to graphs representing antisymmetric relations.

### Dima Pasechnik

Mar 18, 2024, 10:07:52 AMMar 18
to sage-support
Hellen,

On Monday, March 18, 2024 at 1:45:17 PM UTC Hellen Colman wrote:
Yes, that terminology is not perfectly aligned between different areas in mathematics is a good takeaway we will definitely mention in the book. Thank you!

In this case I understand that we are checking antisymmetric in a graph, but the most confusing part is that the documentation is explicitly stating:

"A graph represents an antisymmetric relation if ... "

It is not saying a graph is antisymmetric, but is introducing a new definition of antisymmetric relation.

I don't think that the issue is about relation or graph (both definitions are for graphs), so I like your suggested names "edge_antisymmetric" and "path_antisymmetric" momentarily because they emphasize the actual distinction, so I would suggest the following change in Dima's course of action:

1) copy antisymmetric() to antisymmetric_relation(); deprecate antisymmetric();
introduce  antisymmetric_graph(), to mean the standard definition as Hellen points at.

(to me, directed graphs have arcs; edges are pairs of oppositely oriented arcs)

Dima

### Hellen Colman

Mar 18, 2024, 6:49:57 PMMar 18
to sage-support
Yes, sounds good.