Ask Your Question

guillermo's profile - activity

2021-08-17 05:22:35 +0100 commented answer Nontrivial edge cuts

Hi @tmontell, Thank you for your comments. But I need to process a large number of graphs, and so this is impractical.

2021-08-15 11:00:54 +0100 edited question Nontrivial edge cuts

Nontrivial edge cuts Hi there, I wonder how I can produce nontrivial edge cuts in a graph. An edge cut is trivial is al

2021-08-15 10:44:54 +0100 received badge  Teacher (source)
2021-08-15 07:21:54 +0100 answered a question How do I get the inverse of an element in a finite field GF(p)?

In addition to the previous answers, you could simply write inverse_mod(a,7).

2021-08-15 07:19:36 +0100 asked a question Nontrivial edge cuts

Nontrivial edge cuts Hi there, I wonder how I can produce nontrivial edge cuts in a graph. An edge cut is trivial is al

2021-02-11 15:50:02 +0100 received badge  Notable Question (source)
2020-07-24 09:37:20 +0100 commented answer Shelling order of a simplicial polytope

@jipilab, thank you very much. For some reason, I had overlooked the function boundary_complex!

2020-07-23 08:17:08 +0100 asked a question Shelling order of a simplicial polytope

Hi there,

In sage a simplicial complex C has a function "is_shellable" that could return a shelling order of the facets of C. I assume that every facet of C, a maximal face, has dimension d-1 and that C is pure, every face of C is contained in a facet. The dimension of a complex is the dimension of a facet.

A simplicial d-dimensional polytope P is a simplicial (d-1)-dimensional complex C.P is a Polyhedron in sage. Suppose I have a realisation of P in R^d, coordinates of all its vertices. Is there a reasonable direct way to make use of the function "is_shellable" to obtain a shelling order of a P?

Thank you in advance, and regards, Guillermo

2019-11-06 20:17:20 +0100 received badge  Popular Question (source)
2019-10-25 20:12:13 +0100 received badge  Nice Question (source)
2019-10-22 11:42:20 +0100 asked a question About algorithm for testing whether a point is in a V-polyhedron

Hi there,

I have two questions and I wonder if any of you may know the answer.

1 What algorithm does sage use to test whether a given point is in a polyhedron, namely in the function polyhedron.contains()?

  1. Is there a difference in the algorithm according to whether the V-polyhedron is a V-polytope or is unbounded?

Thank you, and best regards, Guillermo

2019-09-12 11:03:17 +0100 received badge  Popular Question (source)
2019-08-28 12:48:23 +0100 received badge  Nice Question (source)
2018-05-24 02:05:53 +0100 commented answer A linkage problem

Thank you very much Sebastien. The method disjoint_routed_paths was what I was after.

I believe the problem with your code is that, once you have the k-sets L and R, you need to permute one of them, say L, to consider all the possible pairings for these two sets.

Regards, Guillermo

2018-05-23 02:22:11 +0100 commented question A linkage problem

Hi Dan,

Thank you for your comment. I have explained the problem a bit more.

Regards, Guillermo

2018-05-23 02:21:42 +0100 commented answer A linkage problem

HI Sebastien,

Thank you for your code. I fail to understand how this solve the linkage problem. I have explained the problem a bit more.

Regards, Guillermo

2018-05-22 13:44:14 +0100 asked a question A linkage problem

Hi there,

I wonder how I can use Sage to solve the following problem, without implementing a full-blown backtracking.

Let $G$ be an undirected simple graph with at least $2k$ vertices. The graph $G$ would need to be $2k-1$-vertex-connected for the problem to hope to have a solution, but this is perhaps beside the point. Let $X$ be a set of $2k$ distinct vertices $s_1,...,s_k,t_1,...,t_k$ of G. Pair these $2k$ vertices arbitrarily into k pairs $(s_i,t_i)$. The pair $(s_i,t_i)$ means that the vertex $s_i$ has been paired with the vertex $t_i$. This pairing doesn't altered the graph $G$ in any way. The problem consists of finding k pairwise vertex-disjoint paths between $s_i$ and $t_i$ for each i, or returns that it is not possible to do so.

A graph for which you can find the $k$ vertex-disjoint paths for any possible set $X$ is called $k$-linked.

Let me give you an example. Suppose I take the 3-cube graph. I am gonna see it as a graph of the polytope 3-cube because the image is better.

P3=polytopes.hypercube(3)

Q3=P3.graph()

Q3.show()

Let me choose 4 vertices arbitrary vertices for my set $X$, say $s_1=(1,1,1)$, $t_1=(-1,-1,1)$, $s_2=(1,-1,1)$ and $t_2=(-1,1,1)$. Pair the vertices as $(s_i,t_i)$. Then we cannot find 2 vertex-disjoint paths, one connecting $s_1$ to $t_1$ and another $s_2$ to $t_2$. However, if I choose $X$ to be $s_1=(1,1,1)$, $t_1=(-1,-1,1)$ and $s_2=(-1,-1,-1)$ and $t_2=(1,1,-1)$ we can.

As an aside this shows that the 3-CubeGraph is not 2-linked.

Hope this is a bit clearer now.

Thank you in advance, and regards, Guillermo

2016-11-16 08:58:04 +0100 commented answer Is it possible to compute the face lattice of a polytope from its vertex-facet incidences?

Hi slelievre,

Thank you for your reply. Sage computes the face lattice of a polytope using Kaibel and Pfetsch's algorithm. So a polytope must be given. However, for you to construct a polytope in Sage you need either vertex coordinates or hyperplane equations; that is, you need a geometric realisation of the polytope.

Vertex-facet incidences is a combinatorial object which doesn't know about a geometric realisation. For instance, the following gives the vertex-facet incidences of the Egyptian pyramid [[4,3,2,1],[4,3,0],[4,2,0],[3,1,0],[2,1,0]], where the [4, 3, 2, 1] are the vertices of one facet.

2016-11-16 01:13:31 +0100 asked a question Is it possible to compute the face lattice of a polytope from its vertex-facet incidences?

HI there,

I wonder if within sage it is possible to compute the face lattice of a polytope from its vertex-facet incidences. There is a known algorithm by Kaibel and Pfetsch (see https://arxiv.org/pdf/math/0106043.pdf), and we wonder if it has already been implemented in Sage.

Thanks, and regards, Guillermo

2016-11-16 01:08:03 +0100 asked a question Is there a way to compute the face lattice of a polytope from its vertex-facet incidences?

HI there,

I wonder if within sage it is possible to compute the face lattice of a polytope from its vertex-facet incidences. There is a known algorithm by Kaibel and Pfetsch (see https://arxiv.org/pdf/math/0106043.pdf), and we wonder if it has already been implemented in Sage.

Thanks, and regards, Guillermo

2016-02-04 00:48:23 +0100 commented answer Randomly generated simple polytopes with given number of vertices

Dear Thierry,

Thank you very much for your response. By "random" I simply mean constructing a polytope is by sampling points on the unit sphere.

My question is however about generating simple polytopes. A simple d-polytope is a polytope in which every vertex is part of precisely d facets, or equivalently, of precisely d edges. The polytopes you generate are most likely not simple; in fact, they are most likely simplicial, that is, every facet is a simplex. While a dual of a simplicial polytope is a simple polytope, I need the number of vertices in the simple polytope not in the simplicial one.

Thank you, once again, and regards, Guillermo

2016-02-04 00:43:31 +0100 received badge  Editor (source)
2016-01-29 00:08:43 +0100 asked a question Randomly generated simple polytopes with given number of vertices

Hi there,

I wonder if there is a way of generating random simple polytopes with a given number of vertices.

EDIT

By "random" I simply mean constructing a polytope by sampling points on the unit sphere.

A simple d-polytope is a d-polytope in which every vertex is part of precisely d facets, or equivalently, of precisely d edges.

Thank you, and regards, Guillermo

2015-08-13 19:13:02 +0100 received badge  Nice Question (source)
2015-08-13 10:28:07 +0100 received badge  Student (source)
2015-08-13 09:57:28 +0100 commented answer Isomorphisms of 2-skeletons of polytopes

Great! Thanks a lot.

2015-08-13 09:57:08 +0100 received badge  Scholar (source)
2015-08-13 09:19:02 +0100 asked a question Isomorphisms of 2-skeletons of polytopes

Hi there,

We are interested in checking whether the 2-skeletons of two distinct polytopes are isomorphic (as posets). We understand that we can get the face_lattice of each of the polytope, but we don't know who to produce a poset which contains the 2-skeleton for each polytope so that we can use the function is_isomorphic for posets?

Thank you in advance, and regards, Guillermo