Ask Your Question

merluza's profile - activity

2019-11-05 15:51:16 -0500 received badge  Organizer (source)
2019-11-05 15:28:50 -0500 asked a question maximizing sum over feasible set of vectors

Let $[5]$ be the set of the first 5 positive integers. We let $\underline{\alpha} =(\alpha_A)_{A\neq \emptyset, A\subseteq [5]}$ consist of a vector with $31$ real entries, where each $\alpha_A$ is associated with a subset $A \subseteq [5]$.

Define $\displaystyle OBJ(\underline{\alpha})=\sum_{A\subseteq [5], A\neq \emptyset} \alpha_A \log(|A|)$, $\quad \displaystyle v(\underline{\alpha})=\sum_{A\subseteq [5], A\neq \emptyset} \alpha_A$, $\quad$ and $\quad \displaystyle E(\underline{\alpha})=\sum_{ {A,B}: A\cap B\neq \emptyset} \alpha_A \alpha_B$, where the sum for $E(\underline{\alpha})$ is taken over all unordered pairs of disjoint nonempty sets $A$ and $B$, where $A, B \subseteq [5]$.

Also define $FEAS(1/4)$ to be the set of all such vectors $\underline{\alpha}$ with nonnegative real entries such that $v(\underline{\alpha})=1$ and $E(\underline{\alpha})\geq 1/4$.

I want to learn how to program the following optimization problem: $$\displaystyle OPT(1/4):=\max_{\underline{\alpha} \in FEAS(1/4)} OBJ(\underline{\alpha})$$

I was told that I can do this in SageMath. I have some basic knowledge of how to use Sage. How could I create the set $FEAS(1/4)$? I think that from there I may be able to figure out how to maximize $OBJ(\underline{\alpha})$ over this set.

2019-11-05 12:25:39 -0500 commented question How to create 31-tuples with nonnegative entries that sum to 1

My apologies, I just edited my post. The entries are real and nonnegative.

2019-11-05 11:54:26 -0500 asked a question How to create 31-tuples with nonnegative entries that sum to 1

Hello. I would like to know how to create all 31-tuples (sequence of 31 numbers) whose entries are real, nonnegative, and sum up to one. One such kind of tuple would be one where exactly one of the 31 entries is 1 and all of the other remaining 30 entries are 0.

How could I ask Sage to do this?

Thank you.

2019-06-23 13:13:07 -0500 received badge  Self-Learner (source)
2019-06-23 13:13:07 -0500 received badge  Teacher (source)
2019-06-23 12:11:49 -0500 answered a question find all matchings in a graph

I found another way! Given a graph $G$, ask Sage to create its line graph and then from there find all of the independent sets in the line graph. The independent sets in the line graph are precisely the matchings in the original graph. Here is the code for finding the matchings in $K_{4,5}$:

from sage.graphs.independent_sets import IndependentSets
B45=graphs.CompleteBipartiteGraph(4,5)
L_B45=B45.line_graph()
M=[x for x in IndependentSets(L_B45)]
2019-06-21 22:22:40 -0500 commented question find all matchings in a graph

Thank you for your comment. Yes, I was aware that Sage can compute the matching polynomial of a graph, which is why I am surprised that it cannot list the matching themselves if it can count them.

What I am trying to figure out now is the following: Given a the edge set E of a graph, how can I get Sage to give me all possible subsets of E which contain pairs with completely distinct entries, i.e., a matching.

2019-06-21 17:05:51 -0500 asked a question find all matchings in a graph

Given a graph $G$, is it possible to ask Sage to generate all possible matchings of $G$? I know that G.matching() gives a maximum matching of $G$ and I also know that Sage has an iterator which finds all perfect matchings of $G$.

If no command exists which asks Sage to give me all possible matchings of $G$, does anyone have an idea of how to write a program to ask Sage to do this?

2019-04-14 13:51:33 -0500 commented answer return lists that do not share all of the same elements

I am not creating the lists. I am running an iterator and Sage gives me lists. I want it to return lists with distinct elements.

2019-04-14 11:19:37 -0500 asked a question return lists that do not share all of the same elements

I am having Sage generate an array of lists for me, but I do not want it to give me the lists that have all of the same elements. For example, if Sage gives me

[1 2 3 4]

[2 3 4 1]

[1 3 4 2]

I only want Sage to give me [1 2 3 4]. I want to create a new array with these non-repeated lists. How do I do that? Thank you!

2019-04-13 18:37:28 -0500 asked a question Find copy of subgraph and check if graph induced by neighborhood of particular vertex is bipartite

I asked Sage to generate all graphs on 7 vertices and 12 edges with clique number 4 using the command

g7_4=[g for g in graphs.nauty_geng('7 12') if g.clique_number()==4]

Next I defined a graph H as follows:

H=graphs.CompleteGraph(4)
H.add_edges([(4,0), (4,1), (4,5)])

For every induced isomorphic copy H' of H in each graph g in g7_4 I want Sage to find out if the subgraph induced by the neighborhood of the isomorphic copy in H' of the vertex labeled 4 in H is bipartite or not.

The issue here is that I want to target the vertex in H' that plays the role of 4 in H, but I can't figure out how to do that.

Here is my feeble attempt:

for g in g7_4:
 for p in g.subgraph_search_iterator(H,induced=True):  #for each induced isomorphic copy of H in g
     N=p.subgraph(Set(H.neighbors(4)))   #let N be subgraph induced by neighborhood of 4 (vertex from H)
     if not N.is_bipartite():
          print(g7_4.index(g), 'bipartite')
     else:
          print(g7_4.index(g), 'not bipartite')

Please help me with my code! I am still new to Sage. Thank you!

2019-04-05 14:37:27 -0500 asked a question if statements with is_bipartite()

Say I define a graph G in Sage. Then I can ask Sage to tell me whether or not G is bipartite by typing G.is_bipartite()

Sage will tell me either True or False. Now say that I want Sage to indicate whether or not G is bipartite by showing me the graph G if it is bipartite or by not showing it to me if it is not bipartite. I want to write something along the lines of

if G.is_bipartite(): show(G)

I get an error, and it is probably because I am not telling it exactly what I want to do as I mentioned above. How do I do this? If showing me the graph is not possible, maybe I can ask Sage to print a 1 if it is bipartite and to print a 0 otherwise. Thank you in advance!

2019-04-03 19:32:10 -0500 received badge  Supporter (source)
2019-04-03 18:13:39 -0500 received badge  Editor (source)
2019-04-03 18:13:14 -0500 asked a question Maximize nonlinear function with linear constraints

I would like to have Sage maximize 60 * 5^{x0} *4^{x1} * 3^{x2}, where x0, x1, x2 are nonnegative integers such that

x0+x1+x2=2k-3 and x1+2*x2 >= 3k-3,

where k is any nonnegative integer such that 3<= k <=20. I would like to create a loop so that Sage does this for me for each of these values of k.

I know that Sage has a tool called minimize_constrained, but I can't find a tool called "maximize_constrained". Please help! Thank you in advance :-)

2019-03-31 21:14:58 -0500 commented answer Create program to find which graphs contain specific subgraph

Thank you!! You are a lifesaver! I was unaware of subgraph_search_iterator tool, this is wonderful.

2019-03-31 13:02:03 -0500 commented answer Create program to find which graphs contain specific subgraph

Thank you for your help. Would you also happen to know how I can ask Sage to give me graphs in g10 that also satisfy the condition that every vertex in a 4-clique has degree at least 6?

2019-03-30 12:56:30 -0500 asked a question Create program to find which graphs contain specific subgraph

Hello, I am pretty new to Sage, and am discovering all the wonderful things it can do. I know how to ask Sage to generate a list of graphs that satisfy particular properties. To do this I "call" a program named "nauty". For example, if I would like to generate all graphs with 10 vertices, 25 edges, and clique number 4 I type the following:

sage: g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]

Now say that I want to check which of these graphs contain a particular subgraph. For example, say I want to know which one of these graphs contain a 5-cycle. How can I ask Sage to go through the list of graphs in g10 and tell me this information?

Thank you in advance!

2019-03-29 15:33:04 -0500 received badge  Scholar (source)
2019-03-29 15:32:22 -0500 asked a question Building Graphs with Specific Properties Using Sage

I would like to use Sage to build graphs with particular properties. I know how to call a program called "nauty" to ask Sage to generate, for example, all graphs on 8 vertices with 16 edges with clique number 4. However, I would like to add more properties.

Is it possible to have Sage generate all graphs with clique number 4 so that all vertices that are contained in a 4-clique satisfy a minimum degree condition? Or is it in general possible to have a particular subset of vertices satisfy a degree condition?

Thank you.

2019-02-01 14:44:50 -0500 received badge  Student (source)
2019-02-01 07:24:51 -0500 asked a question Checking that all values in an array satisfy an inequality

I would like to know how to check element-wise that every entry in an array is less than or equal to a particular number. It would seem that something like this would require a loop, but I am not sure. Could someone help me? Thank you in advance

2019-02-01 07:24:51 -0500 asked a question Checking that all values in an array satisfy an inequality

I would like to know how to check element-wise that every entry in an array is less than or equal to a particular number. It would seem that something like this would require a loop, but I am not sure. Could someone help me? Thank you in advance