135 views

Skip to first unread message

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:

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:

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.

Mar 11, 2024, 6:20:05 PMMar 11

to sage-s...@googlegroups.com

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)

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/88c4e8f1-f04d-4010-91b4-39fdd8a403f8n%40googlegroups.com.

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:

*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.

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

My student Sam did read carefully the documentation that is why he discovered that Sage is using

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 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.

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.

Mar 16, 2024, 8:42:23 AMMar 16

to sage-s...@googlegroups.com

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>

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)"

)

commit 0e4f3807f2a18b3a03f47ad35d0aae1c06058fc0

Author: Jason Grout <jason...@creativetrax.com>

Date: Tue Sep 25 18:46:29 2007 -0500

graphs: added transitive_closure() and antisymmetric().

Author: Jason Grout <jason...@creativetrax.com>

Date: Tue Sep 25 18:46:29 2007 -0500

graphs: added transitive_closure() and antisymmetric().

[...]

+ def transitive_closure(self):

+ r"""

+ Modifies a graph to be its transitive closure and returns the

+ modified graph.

+ 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.

[...]

+ 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.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/8b537b0f-d1bb-41eb-95f6-33c8a2c4c3d6n%40googlegroups.com.

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

to sage-s...@googlegroups.com

This is now https://github.com/sagemath/sage/issues/37618

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.

"path_antisymmetric()" instead of "antisymmetric_relation()"

"edge_antisymmetric()" instead of "antisymmetric_graph()"

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.

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

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

1) copy antisymmetric() to antisymmetric_relation(); deprecate antisymmetric();

introduce antisymmetric_graph(), to mean the standard definition as Hellen points at.

"edge_antisymmetric()" instead of "antisymmetric_graph()"

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()

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 anantisymmetric relationif ... "

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 aboutrelationorgraph(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.

"path_antisymmetric()" instead of "antisymmetric_relation()"

"edge_antisymmetric()" instead of "antisymmetric_graph()"

how about "arc_antisymmetric" instead of "edge_antisymmetic"

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

Dima

Mar 18, 2024, 6:49:57 PMMar 18

to sage-support

Yes, sounds good.

Mar 18, 2024, 7:48:19 PMMar 18

to sage-support

On Monday 18 March 2024 at 06:45:17 UTC-7 Hellen Colman wrote:

"A graph represents anantisymmetric relationif ... "

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

Ah, indeed! The person must have been interested in transitive relations and probably thought of the transitive relation represented by a digraph. It does make sense to represent a transitive relation by only a partial graph whose transitive closure gives the relation of interest. So the routine as-is could be documented as "a graph represents a transitive relation that is antisymmetric if ...". Then it's a question if the other meaning is worthwhile to have available as well. That splits the change into a simple bugfix by updating the documentation and a possible new feature (including renaming of methods, if desired)

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu