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.
--
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.
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?
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.
--
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.
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()"
"A graph represents an antisymmetric relation if ... "
It is not saying a graph is antisymmetric, but is introducing a new definition of antisymmetric relation.