Mixing
Efficient algorithm for calculating flag products
$begingroup$
This concerns flag algebras. I am wondering if there exists an efficient algorithm for calculating the below quantity. Before we can use semidefinite programming to find bounds on Turan densities, we should (as listed at the bottom of 1.3 in Andrej Grzesik's thesis) find the quantity $mathbb{E}_{theta in mathbf{Theta}_{H}}[d(F_{1}, F_{2}; (H, theta))]$ for $H in mathcal{F}_{l}^{0}$.
For example, the case where we have a 1-vertex type and are considering embeddings into graphs on 3-vertex graphs is shown below (also from Grzesik's paper):
I am wondering if there is an efficient way to calculate this quantity. There seem to be "hard" computations here: calculating over all possible embeddings $theta$ of the type into the unlabelled graph $H$, and calculating the joint density $d(F_{1}, F_{2}; (H, theta))$.
The example above is "easy" since joining each pair of flags together results in a graph which is exactly the size of our "$H$", and there are only three possible embeddings of the 1-vertex into the 3-vertex graph (not up to isomorphism).
Later in Grzesik's paper, he calculates these quantities for the following flags:
on $K_{3}$-free 5-vertex graphs. If we try the same tactic of "listing all possible embeddings" of the 3-vertex type into the 5-vertex graph, since our flags are now far more complicated than the flags in the former case, I'd imagine we run into a lot of trouble (lots of isomorphisms that are hard to catch in code, as a thought).
I believe Razborov calls these quantities "normalizing factors", and he gives an algebraic formula for the normalizing factor on the "identity flag" $1_{sigma}$. Is there an algorithm to perform these computations? Is this quantity the one I should be calculating?
EDIT: I should also add that I plan on doing this calculation with Sage; I don't think there is a function in Sage which calculates graph densities given a subset of vertices which are fixed, but I would love to be wrong.
graph-theory algebraic-graph-theory
asked Jan 31 at 18:51
RichardRichard
497
$endgroup$
add a comment |
$begingroup$
This concerns flag algebras. I am wondering if there exists an efficient algorithm for calculating the below quantity. Before we can use semidefinite programming to find bounds on Turan densities, we should (as listed at the bottom of 1.3 in Andrej Grzesik's thesis) find the quantity $mathbb{E}_{theta in mathbf{Theta}_{H}}[d(F_{1}, F_{2}; (H, theta))]$ for $H in mathcal{F}_{l}^{0}$.
For example, the case where we have a 1-vertex type and are considering embeddings into graphs on 3-vertex graphs is shown below (also from Grzesik's paper):
I am wondering if there is an efficient way to calculate this quantity. There seem to be "hard" computations here: calculating over all possible embeddings $theta$ of the type into the unlabelled graph $H$, and calculating the joint density $d(F_{1}, F_{2}; (H, theta))$.
The example above is "easy" since joining each pair of flags together results in a graph which is exactly the size of our "$H$", and there are only three possible embeddings of the 1-vertex into the 3-vertex graph (not up to isomorphism).
Later in Grzesik's paper, he calculates these quantities for the following flags:
on $K_{3}$-free 5-vertex graphs. If we try the same tactic of "listing all possible embeddings" of the 3-vertex type into the 5-vertex graph, since our flags are now far more complicated than the flags in the former case, I'd imagine we run into a lot of trouble (lots of isomorphisms that are hard to catch in code, as a thought).
I believe Razborov calls these quantities "normalizing factors", and he gives an algebraic formula for the normalizing factor on the "identity flag" $1_{sigma}$. Is there an algorithm to perform these computations? Is this quantity the one I should be calculating?
EDIT: I should also add that I plan on doing this calculation with Sage; I don't think there is a function in Sage which calculates graph densities given a subset of vertices which are fixed, but I would love to be wrong.
graph-theory algebraic-graph-theory
asked Jan 31 at 18:51
RichardRichard
497
$endgroup$
add a comment |
$begingroup$
This concerns flag algebras. I am wondering if there exists an efficient algorithm for calculating the below quantity. Before we can use semidefinite programming to find bounds on Turan densities, we should (as listed at the bottom of 1.3 in Andrej Grzesik's thesis) find the quantity $mathbb{E}_{theta in mathbf{Theta}_{H}}[d(F_{1}, F_{2}; (H, theta))]$ for $H in mathcal{F}_{l}^{0}$.
For example, the case where we have a 1-vertex type and are considering embeddings into graphs on 3-vertex graphs is shown below (also from Grzesik's paper):
I am wondering if there is an efficient way to calculate this quantity. There seem to be "hard" computations here: calculating over all possible embeddings $theta$ of the type into the unlabelled graph $H$, and calculating the joint density $d(F_{1}, F_{2}; (H, theta))$.
The example above is "easy" since joining each pair of flags together results in a graph which is exactly the size of our "$H$", and there are only three possible embeddings of the 1-vertex into the 3-vertex graph (not up to isomorphism).
Later in Grzesik's paper, he calculates these quantities for the following flags:
on $K_{3}$-free 5-vertex graphs. If we try the same tactic of "listing all possible embeddings" of the 3-vertex type into the 5-vertex graph, since our flags are now far more complicated than the flags in the former case, I'd imagine we run into a lot of trouble (lots of isomorphisms that are hard to catch in code, as a thought).
I believe Razborov calls these quantities "normalizing factors", and he gives an algebraic formula for the normalizing factor on the "identity flag" $1_{sigma}$. Is there an algorithm to perform these computations? Is this quantity the one I should be calculating?
EDIT: I should also add that I plan on doing this calculation with Sage; I don't think there is a function in Sage which calculates graph densities given a subset of vertices which are fixed, but I would love to be wrong.
graph-theory algebraic-graph-theory
asked Jan 31 at 18:51
RichardRichard
497
$endgroup$
This concerns flag algebras. I am wondering if there exists an efficient algorithm for calculating the below quantity. Before we can use semidefinite programming to find bounds on Turan densities, we should (as listed at the bottom of 1.3 in Andrej Grzesik's thesis) find the quantity $mathbb{E}_{theta in mathbf{Theta}_{H}}[d(F_{1}, F_{2}; (H, theta))]$ for $H in mathcal{F}_{l}^{0}$.
For example, the case where we have a 1-vertex type and are considering embeddings into graphs on 3-vertex graphs is shown below (also from Grzesik's paper):
I am wondering if there is an efficient way to calculate this quantity. There seem to be "hard" computations here: calculating over all possible embeddings $theta$ of the type into the unlabelled graph $H$, and calculating the joint density $d(F_{1}, F_{2}; (H, theta))$.
The example above is "easy" since joining each pair of flags together results in a graph which is exactly the size of our "$H$", and there are only three possible embeddings of the 1-vertex into the 3-vertex graph (not up to isomorphism).
Later in Grzesik's paper, he calculates these quantities for the following flags:
on $K_{3}$-free 5-vertex graphs. If we try the same tactic of "listing all possible embeddings" of the 3-vertex type into the 5-vertex graph, since our flags are now far more complicated than the flags in the former case, I'd imagine we run into a lot of trouble (lots of isomorphisms that are hard to catch in code, as a thought).
I believe Razborov calls these quantities "normalizing factors", and he gives an algebraic formula for the normalizing factor on the "identity flag" $1_{sigma}$. Is there an algorithm to perform these computations? Is this quantity the one I should be calculating?
EDIT: I should also add that I plan on doing this calculation with Sage; I don't think there is a function in Sage which calculates graph densities given a subset of vertices which are fixed, but I would love to be wrong.
graph-theory algebraic-graph-theory
graph-theory algebraic-graph-theory
asked Jan 31 at 18:51
RichardRichard
497
asked Jan 31 at 18:51
RichardRichard
497
edited Jan 31 at 19:11
Richard
asked Jan 31 at 18:51
RichardRichard
497
asked Jan 31 at 18:51
RichardRichard
497
asked Jan 31 at 18:51
RichardRichard
497
497
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We should distinguish between two relevant quantities:
- The coefficient of $H$ in the product $F_1 cdot F_2$, where $F_1, F_2$ are $sigma$-flags on $k_1, k_2$ vertices and $H$ is a $sigma$-flag on $k_1+k_2-|sigma|$ vertices.
- The coefficient of $H$ in the average $[![F]!]_sigma$, where $F$ is a $sigma$-flag and $H$ the underlying graph. This is what Razborov calls the "normalizing factor" $q_sigma(F)$.
In your multiplication table, you are doing both operations at once. This is not uncommon in papers, since it often gives us the values we are actually interested in, but it makes it harder to see what happens.
(As a side note, I should mention that I am just going to discuss graphs and some of this may be false or meaningless for more general flag algebras.)
If you look at typical objective functions in a flag algebra semidefinite program, they are a $max$ of many terms. (For example, see the expression which takes up most of p. 20 in Grzesik.) Computing one of those terms directly would be obnoxious, but mostly we don't have to do that. Instead, we do a bunch of easy computations, each one of which contributes to a few of the terms, and then we combine everything we've got.
Coefficients in multiplication
As far as multiplication goes, both of your examples are actually fairly easy: the difficulty of multiplying $sigma$-flags on $k$ vertices scales primarily with $k-|sigma|$. So, although there are many $sigma_i$-flags in the calculation for Erdős's pentagon problem (and you wouldn't want to do them all by hand), each calculation is short and they are all very similar.
There are two steps to multiplication: first, we find all the $sigma$-flags that appear in the product, and second, we find their coefficients.
For the first step, although we could just enumerate all possible $sigma$-flags of the right size, there is a shortcut, using "don't-care" edges. Embed the two $sigma$-flags in a $sigma$-flag with $|sigma|+k_1+k_2$ additional vertices, so that $sigma$ with the first $k_1$ vertices forms $F_1$ and $sigma$ with the last $k_2$ vertices forms $F_2$. Between the first $k_1$ and last $k_2$ additional vertices, put "don't-care" edges that could either be present or absent. Then try all possibilities for those edges.
For example, when multiplying together 
and 
, the $sigma_2$-flags appearing in the product are all forms of 
, where the dashed edge is a don't-care edge that could appear or not appear. The two $sigma_2$-flags that have this property are 
and 
.
For the second step, we compute the density Grzesik calls $d(F_1,F_2,H;theta)$: the probability that if we pick two $sigma$-flags of the right size from $H$, disjoint outside the vertices of $sigma$, the first will be $F_1$ and the second will be $F_2$. In this case, both for and , the density is $frac12$. There are two ways to pick two $sigma_0$-flag with $4$ vertices out of : you pick which non-$sigma_0$ vertex goes in the first flag, and which non-$sigma_0$ vertex goes in the second flag. Either way, one will be and one will be , but it matters which one is which: you have a $frac12$ chance of getting them in the right order. The same calculation goes for . Therefore
$cdot$$= dfrac12$$+dfrac12$.
In fact, whenever you multiply together distinct $sigma$-flags on $|sigma|+1$ vertices, you'll get two flags with coefficients of $frac12$, by the exact same reasoning. Whenever you square a $sigma$-flag on $|sigma|+1$ vertices, you'll get two flags with coefficients of $1$. However, the $frac12$ term washes out in applications: if you're computing $mathbf{x}^{mathsf T}Pmathbf x$ where $mathbf x$ is a vector of $sigma$-flags, then each product of distinct flags will occur twice (as $x_i p_{ij} x_j$ and as $x_j p_{ji} x_i$) while the square of each flag will only occur once (as $x_i p_{ii} x_i$).
For a more complicated example, consider the product of the two possible graphs on $2$ vertices: "edge" and "non-edge". Here, the flags ($4$-vertex graphs) appearing in the product are all those represented by the diagram 
with four don't-care edges. With repetition, there would be $16$ such graphs, but there are only $7$ distict ones: 
, 
, 
, 
, 
, 
, and 
.
For each of these flags, we should compute the coefficient. This is the probability that if we choose a pair of vertices ${a,b}$ (in $binom 42$ ways) and another disjoint pair of vertices ${c,d}$ (in $binom 22$ ways) then $ab$ will be an edge and $cd$ will not be. So just check all $binom 42 binom 22$ choices for all $7$ flags, getting
$dfrac16$$+dfrac13$$+dfrac12$$+dfrac12$$+dfrac16$$+dfrac13$$+dfrac16$.
As a sanity check, if $mathbf x$ is the vector of all $n$ possible $sigma$-flags on $|sigma|+k$ vertices, then each $sigma$-flag on $|sigma|+2k$ vertices should appear among the $n^2$ products $(x_i x_j)_{i,j=1}^n$ with a total coefficient of $1$.
Finally, I should note that in many applications, we are considering a subset of all graphs (for example, all triangle-free graphs). In that case, some of the flags in these computations may vanish, because they contain a forbidden subgraph.
Normalizing factors
In almost all cases, the only averaging operator we use is $[![cdot]!]_sigma$, going from $sigma$-flags to graphs. So I'll just talk about this one.
Here, the good news is that the graph $H$ we get as a result of $[![F]!]_sigma$ is fixed: it is the underlying graph of $F$, where we just forget about $sigma$. Only the coefficient needs calculating.
To compute the coefficient, we consider all injections $theta : {1, 2, dots, |sigma|} to V(H)$, and count the fraction of them that actually produce a $sigma$-flag isomorphic to $F$.
For example, if we normalize , then we get the graph 
, which is isomorphic to $K_{2,3}$. An injection $theta$ gives us $F$ iff $theta(1), theta(3)$ degree-$2$ vertices and $theta(2)$ is a degree-$3$ vertex, which happens with probability $frac35 cdot frac24 cdot frac23 = frac15$, so the normalizing factor is $frac15$.
Computational considerations
Disclaimer: I have never actually attempted to implement flag algebra computations in software. But if we look at what is necessary, the main thing is checking for isomorphism of many small graphs (and flags).
There are well-known tools for checking for isomorphism: nauty and bliss are two that come to mind. They are easy to adapt to checking for flag isomorphism, because that matches how graph isomorphism checkers already work. They can all check for isomorphisms of colored graphs, in which each vertex is assigned a color; two colored graphs are isomorphic if there is a bijection respecting both graph structure and color of vertices. If you assign each vertex of $sigma$ its own color, and use a final color on the non-$sigma$ vertices, you get a test for isomorphisms of $sigma$-flags.
(Essentially, the reason that graph isomorphism tools do this is that they work by starting with a partition of the vertex set of a graph into "different-looking" vertices, and refine it until all vertices that are in principle distinguishable have been put in different classes of the partition. Having this partition restricts the number of bijections we need to check for being isomorphisms. This also explains why highly symmetric graphs are a worst case for graph isomorphism.)
Also, you will not need to deal with very large graphs in flag algebra computations: the number of possible flags blows up too quickly for that to become a problem. So checking for flag isomorphism by brute force is not as terrible an option as it may seem. (Although special tools may well be faster anyway, assuming that Sage can efficiently interface with them.)
Finally, all of these calculations can be done using tools such as Flagmatic.
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
$endgroup$
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3095299%2fefficient-algorithm-for-calculating-flag-products%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We should distinguish between two relevant quantities:
- The coefficient of $H$ in the product $F_1 cdot F_2$, where $F_1, F_2$ are $sigma$-flags on $k_1, k_2$ vertices and $H$ is a $sigma$-flag on $k_1+k_2-|sigma|$ vertices.
- The coefficient of $H$ in the average $[![F]!]_sigma$, where $F$ is a $sigma$-flag and $H$ the underlying graph. This is what Razborov calls the "normalizing factor" $q_sigma(F)$.
In your multiplication table, you are doing both operations at once. This is not uncommon in papers, since it often gives us the values we are actually interested in, but it makes it harder to see what happens.
(As a side note, I should mention that I am just going to discuss graphs and some of this may be false or meaningless for more general flag algebras.)
If you look at typical objective functions in a flag algebra semidefinite program, they are a $max$ of many terms. (For example, see the expression which takes up most of p. 20 in Grzesik.) Computing one of those terms directly would be obnoxious, but mostly we don't have to do that. Instead, we do a bunch of easy computations, each one of which contributes to a few of the terms, and then we combine everything we've got.
Coefficients in multiplication
As far as multiplication goes, both of your examples are actually fairly easy: the difficulty of multiplying $sigma$-flags on $k$ vertices scales primarily with $k-|sigma|$. So, although there are many $sigma_i$-flags in the calculation for Erdős's pentagon problem (and you wouldn't want to do them all by hand), each calculation is short and they are all very similar.
There are two steps to multiplication: first, we find all the $sigma$-flags that appear in the product, and second, we find their coefficients.
For the first step, although we could just enumerate all possible $sigma$-flags of the right size, there is a shortcut, using "don't-care" edges. Embed the two $sigma$-flags in a $sigma$-flag with $|sigma|+k_1+k_2$ additional vertices, so that $sigma$ with the first $k_1$ vertices forms $F_1$ and $sigma$ with the last $k_2$ vertices forms $F_2$. Between the first $k_1$ and last $k_2$ additional vertices, put "don't-care" edges that could either be present or absent. Then try all possibilities for those edges.
For example, when multiplying together and , the $sigma_2$-flags appearing in the product are all forms of , where the dashed edge is a don't-care edge that could appear or not appear. The two $sigma_2$-flags that have this property are and .
For the second step, we compute the density Grzesik calls $d(F_1,F_2,H;theta)$: the probability that if we pick two $sigma$-flags of the right size from $H$, disjoint outside the vertices of $sigma$, the first will be $F_1$ and the second will be $F_2$. In this case, both for and , the density is $frac12$. There are two ways to pick two $sigma_0$-flag with $4$ vertices out of : you pick which non-$sigma_0$ vertex goes in the first flag, and which non-$sigma_0$ vertex goes in the second flag. Either way, one will be and one will be , but it matters which one is which: you have a $frac12$ chance of getting them in the right order. The same calculation goes for . Therefore
$cdot$$= dfrac12$$+dfrac12$.
In fact, whenever you multiply together distinct $sigma$-flags on $|sigma|+1$ vertices, you'll get two flags with coefficients of $frac12$, by the exact same reasoning. Whenever you square a $sigma$-flag on $|sigma|+1$ vertices, you'll get two flags with coefficients of $1$. However, the $frac12$ term washes out in applications: if you're computing $mathbf{x}^{mathsf T}Pmathbf x$ where $mathbf x$ is a vector of $sigma$-flags, then each product of distinct flags will occur twice (as $x_i p_{ij} x_j$ and as $x_j p_{ji} x_i$) while the square of each flag will only occur once (as $x_i p_{ii} x_i$).
For a more complicated example, consider the product of the two possible graphs on $2$ vertices: "edge" and "non-edge". Here, the flags ($4$-vertex graphs) appearing in the product are all those represented by the diagram with four don't-care edges. With repetition, there would be $16$ such graphs, but there are only $7$ distict ones: , , , , , , and .
For each of these flags, we should compute the coefficient. This is the probability that if we choose a pair of vertices ${a,b}$ (in $binom 42$ ways) and another disjoint pair of vertices ${c,d}$ (in $binom 22$ ways) then $ab$ will be an edge and $cd$ will not be. So just check all $binom 42 binom 22$ choices for all $7$ flags, getting
$dfrac16$$+dfrac13$$+dfrac12$$+dfrac12$$+dfrac16$$+dfrac13$$+dfrac16$.
As a sanity check, if $mathbf x$ is the vector of all $n$ possible $sigma$-flags on $|sigma|+k$ vertices, then each $sigma$-flag on $|sigma|+2k$ vertices should appear among the $n^2$ products $(x_i x_j)_{i,j=1}^n$ with a total coefficient of $1$.
Finally, I should note that in many applications, we are considering a subset of all graphs (for example, all triangle-free graphs). In that case, some of the flags in these computations may vanish, because they contain a forbidden subgraph.
Normalizing factors
In almost all cases, the only averaging operator we use is $[![cdot]!]_sigma$, going from $sigma$-flags to graphs. So I'll just talk about this one.
Here, the good news is that the graph $H$ we get as a result of $[![F]!]_sigma$ is fixed: it is the underlying graph of $F$, where we just forget about $sigma$. Only the coefficient needs calculating.
To compute the coefficient, we consider all injections $theta : {1, 2, dots, |sigma|} to V(H)$, and count the fraction of them that actually produce a $sigma$-flag isomorphic to $F$.
For example, if we normalize , then we get the graph , which is isomorphic to $K_{2,3}$. An injection $theta$ gives us $F$ iff $theta(1), theta(3)$ degree-$2$ vertices and $theta(2)$ is a degree-$3$ vertex, which happens with probability $frac35 cdot frac24 cdot frac23 = frac15$, so the normalizing factor is $frac15$.
Computational considerations
Disclaimer: I have never actually attempted to implement flag algebra computations in software. But if we look at what is necessary, the main thing is checking for isomorphism of many small graphs (and flags).
There are well-known tools for checking for isomorphism: nauty and bliss are two that come to mind. They are easy to adapt to checking for flag isomorphism, because that matches how graph isomorphism checkers already work. They can all check for isomorphisms of colored graphs, in which each vertex is assigned a color; two colored graphs are isomorphic if there is a bijection respecting both graph structure and color of vertices. If you assign each vertex of $sigma$ its own color, and use a final color on the non-$sigma$ vertices, you get a test for isomorphisms of $sigma$-flags.
(Essentially, the reason that graph isomorphism tools do this is that they work by starting with a partition of the vertex set of a graph into "different-looking" vertices, and refine it until all vertices that are in principle distinguishable have been put in different classes of the partition. Having this partition restricts the number of bijections we need to check for being isomorphisms. This also explains why highly symmetric graphs are a worst case for graph isomorphism.)
Also, you will not need to deal with very large graphs in flag algebra computations: the number of possible flags blows up too quickly for that to become a problem. So checking for flag isomorphism by brute force is not as terrible an option as it may seem. (Although special tools may well be faster anyway, assuming that Sage can efficiently interface with them.)
Finally, all of these calculations can be done using tools such as Flagmatic.
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
$endgroup$
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
add a comment |
$begingroup$
We should distinguish between two relevant quantities:
- The coefficient of $H$ in the product $F_1 cdot F_2$, where $F_1, F_2$ are $sigma$-flags on $k_1, k_2$ vertices and $H$ is a $sigma$-flag on $k_1+k_2-|sigma|$ vertices.
- The coefficient of $H$ in the average $[![F]!]_sigma$, where $F$ is a $sigma$-flag and $H$ the underlying graph. This is what Razborov calls the "normalizing factor" $q_sigma(F)$.
In your multiplication table, you are doing both operations at once. This is not uncommon in papers, since it often gives us the values we are actually interested in, but it makes it harder to see what happens.
(As a side note, I should mention that I am just going to discuss graphs and some of this may be false or meaningless for more general flag algebras.)
If you look at typical objective functions in a flag algebra semidefinite program, they are a $max$ of many terms. (For example, see the expression which takes up most of p. 20 in Grzesik.) Computing one of those terms directly would be obnoxious, but mostly we don't have to do that. Instead, we do a bunch of easy computations, each one of which contributes to a few of the terms, and then we combine everything we've got.
Coefficients in multiplication
As far as multiplication goes, both of your examples are actually fairly easy: the difficulty of multiplying $sigma$-flags on $k$ vertices scales primarily with $k-|sigma|$. So, although there are many $sigma_i$-flags in the calculation for Erdős's pentagon problem (and you wouldn't want to do them all by hand), each calculation is short and they are all very similar.
There are two steps to multiplication: first, we find all the $sigma$-flags that appear in the product, and second, we find their coefficients.
For the first step, although we could just enumerate all possible $sigma$-flags of the right size, there is a shortcut, using "don't-care" edges. Embed the two $sigma$-flags in a $sigma$-flag with $|sigma|+k_1+k_2$ additional vertices, so that $sigma$ with the first $k_1$ vertices forms $F_1$ and $sigma$ with the last $k_2$ vertices forms $F_2$. Between the first $k_1$ and last $k_2$ additional vertices, put "don't-care" edges that could either be present or absent. Then try all possibilities for those edges.
For example, when multiplying together and , the $sigma_2$-flags appearing in the product are all forms of , where the dashed edge is a don't-care edge that could appear or not appear. The two $sigma_2$-flags that have this property are and .
For the second step, we compute the density Grzesik calls $d(F_1,F_2,H;theta)$: the probability that if we pick two $sigma$-flags of the right size from $H$, disjoint outside the vertices of $sigma$, the first will be $F_1$ and the second will be $F_2$. In this case, both for and , the density is $frac12$. There are two ways to pick two $sigma_0$-flag with $4$ vertices out of : you pick which non-$sigma_0$ vertex goes in the first flag, and which non-$sigma_0$ vertex goes in the second flag. Either way, one will be and one will be , but it matters which one is which: you have a $frac12$ chance of getting them in the right order. The same calculation goes for . Therefore
$cdot$$= dfrac12$$+dfrac12$.
In fact, whenever you multiply together distinct $sigma$-flags on $|sigma|+1$ vertices, you'll get two flags with coefficients of $frac12$, by the exact same reasoning. Whenever you square a $sigma$-flag on $|sigma|+1$ vertices, you'll get two flags with coefficients of $1$. However, the $frac12$ term washes out in applications: if you're computing $mathbf{x}^{mathsf T}Pmathbf x$ where $mathbf x$ is a vector of $sigma$-flags, then each product of distinct flags will occur twice (as $x_i p_{ij} x_j$ and as $x_j p_{ji} x_i$) while the square of each flag will only occur once (as $x_i p_{ii} x_i$).
For a more complicated example, consider the product of the two possible graphs on $2$ vertices: "edge" and "non-edge". Here, the flags ($4$-vertex graphs) appearing in the product are all those represented by the diagram with four don't-care edges. With repetition, there would be $16$ such graphs, but there are only $7$ distict ones: , , , , , , and .
For each of these flags, we should compute the coefficient. This is the probability that if we choose a pair of vertices ${a,b}$ (in $binom 42$ ways) and another disjoint pair of vertices ${c,d}$ (in $binom 22$ ways) then $ab$ will be an edge and $cd$ will not be. So just check all $binom 42 binom 22$ choices for all $7$ flags, getting
$dfrac16$$+dfrac13$$+dfrac12$$+dfrac12$$+dfrac16$$+dfrac13$$+dfrac16$.
As a sanity check, if $mathbf x$ is the vector of all $n$ possible $sigma$-flags on $|sigma|+k$ vertices, then each $sigma$-flag on $|sigma|+2k$ vertices should appear among the $n^2$ products $(x_i x_j)_{i,j=1}^n$ with a total coefficient of $1$.
Finally, I should note that in many applications, we are considering a subset of all graphs (for example, all triangle-free graphs). In that case, some of the flags in these computations may vanish, because they contain a forbidden subgraph.
Normalizing factors
In almost all cases, the only averaging operator we use is $[![cdot]!]_sigma$, going from $sigma$-flags to graphs. So I'll just talk about this one.
Here, the good news is that the graph $H$ we get as a result of $[![F]!]_sigma$ is fixed: it is the underlying graph of $F$, where we just forget about $sigma$. Only the coefficient needs calculating.
To compute the coefficient, we consider all injections $theta : {1, 2, dots, |sigma|} to V(H)$, and count the fraction of them that actually produce a $sigma$-flag isomorphic to $F$.
For example, if we normalize , then we get the graph , which is isomorphic to $K_{2,3}$. An injection $theta$ gives us $F$ iff $theta(1), theta(3)$ degree-$2$ vertices and $theta(2)$ is a degree-$3$ vertex, which happens with probability $frac35 cdot frac24 cdot frac23 = frac15$, so the normalizing factor is $frac15$.
Computational considerations
Disclaimer: I have never actually attempted to implement flag algebra computations in software. But if we look at what is necessary, the main thing is checking for isomorphism of many small graphs (and flags).
There are well-known tools for checking for isomorphism: nauty and bliss are two that come to mind. They are easy to adapt to checking for flag isomorphism, because that matches how graph isomorphism checkers already work. They can all check for isomorphisms of colored graphs, in which each vertex is assigned a color; two colored graphs are isomorphic if there is a bijection respecting both graph structure and color of vertices. If you assign each vertex of $sigma$ its own color, and use a final color on the non-$sigma$ vertices, you get a test for isomorphisms of $sigma$-flags.
(Essentially, the reason that graph isomorphism tools do this is that they work by starting with a partition of the vertex set of a graph into "different-looking" vertices, and refine it until all vertices that are in principle distinguishable have been put in different classes of the partition. Having this partition restricts the number of bijections we need to check for being isomorphisms. This also explains why highly symmetric graphs are a worst case for graph isomorphism.)
Also, you will not need to deal with very large graphs in flag algebra computations: the number of possible flags blows up too quickly for that to become a problem. So checking for flag isomorphism by brute force is not as terrible an option as it may seem. (Although special tools may well be faster anyway, assuming that Sage can efficiently interface with them.)
Finally, all of these calculations can be done using tools such as Flagmatic.
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
$endgroup$
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
add a comment |
$begingroup$
We should distinguish between two relevant quantities:
- The coefficient of $H$ in the product $F_1 cdot F_2$, where $F_1, F_2$ are $sigma$-flags on $k_1, k_2$ vertices and $H$ is a $sigma$-flag on $k_1+k_2-|sigma|$ vertices.
- The coefficient of $H$ in the average $[![F]!]_sigma$, where $F$ is a $sigma$-flag and $H$ the underlying graph. This is what Razborov calls the "normalizing factor" $q_sigma(F)$.
In your multiplication table, you are doing both operations at once. This is not uncommon in papers, since it often gives us the values we are actually interested in, but it makes it harder to see what happens.
(As a side note, I should mention that I am just going to discuss graphs and some of this may be false or meaningless for more general flag algebras.)
If you look at typical objective functions in a flag algebra semidefinite program, they are a $max$ of many terms. (For example, see the expression which takes up most of p. 20 in Grzesik.) Computing one of those terms directly would be obnoxious, but mostly we don't have to do that. Instead, we do a bunch of easy computations, each one of which contributes to a few of the terms, and then we combine everything we've got.
Coefficients in multiplication
As far as multiplication goes, both of your examples are actually fairly easy: the difficulty of multiplying $sigma$-flags on $k$ vertices scales primarily with $k-|sigma|$. So, although there are many $sigma_i$-flags in the calculation for Erdős's pentagon problem (and you wouldn't want to do them all by hand), each calculation is short and they are all very similar.
There are two steps to multiplication: first, we find all the $sigma$-flags that appear in the product, and second, we find their coefficients.
For the first step, although we could just enumerate all possible $sigma$-flags of the right size, there is a shortcut, using "don't-care" edges. Embed the two $sigma$-flags in a $sigma$-flag with $|sigma|+k_1+k_2$ additional vertices, so that $sigma$ with the first $k_1$ vertices forms $F_1$ and $sigma$ with the last $k_2$ vertices forms $F_2$. Between the first $k_1$ and last $k_2$ additional vertices, put "don't-care" edges that could either be present or absent. Then try all possibilities for those edges.
For example, when multiplying together and , the $sigma_2$-flags appearing in the product are all forms of , where the dashed edge is a don't-care edge that could appear or not appear. The two $sigma_2$-flags that have this property are and .
For the second step, we compute the density Grzesik calls $d(F_1,F_2,H;theta)$: the probability that if we pick two $sigma$-flags of the right size from $H$, disjoint outside the vertices of $sigma$, the first will be $F_1$ and the second will be $F_2$. In this case, both for and , the density is $frac12$. There are two ways to pick two $sigma_0$-flag with $4$ vertices out of : you pick which non-$sigma_0$ vertex goes in the first flag, and which non-$sigma_0$ vertex goes in the second flag. Either way, one will be and one will be , but it matters which one is which: you have a $frac12$ chance of getting them in the right order. The same calculation goes for . Therefore
$cdot$$= dfrac12$$+dfrac12$.
In fact, whenever you multiply together distinct $sigma$-flags on $|sigma|+1$ vertices, you'll get two flags with coefficients of $frac12$, by the exact same reasoning. Whenever you square a $sigma$-flag on $|sigma|+1$ vertices, you'll get two flags with coefficients of $1$. However, the $frac12$ term washes out in applications: if you're computing $mathbf{x}^{mathsf T}Pmathbf x$ where $mathbf x$ is a vector of $sigma$-flags, then each product of distinct flags will occur twice (as $x_i p_{ij} x_j$ and as $x_j p_{ji} x_i$) while the square of each flag will only occur once (as $x_i p_{ii} x_i$).
For a more complicated example, consider the product of the two possible graphs on $2$ vertices: "edge" and "non-edge". Here, the flags ($4$-vertex graphs) appearing in the product are all those represented by the diagram with four don't-care edges. With repetition, there would be $16$ such graphs, but there are only $7$ distict ones: , , , , , , and .
For each of these flags, we should compute the coefficient. This is the probability that if we choose a pair of vertices ${a,b}$ (in $binom 42$ ways) and another disjoint pair of vertices ${c,d}$ (in $binom 22$ ways) then $ab$ will be an edge and $cd$ will not be. So just check all $binom 42 binom 22$ choices for all $7$ flags, getting
$dfrac16$$+dfrac13$$+dfrac12$$+dfrac12$$+dfrac16$$+dfrac13$$+dfrac16$.
As a sanity check, if $mathbf x$ is the vector of all $n$ possible $sigma$-flags on $|sigma|+k$ vertices, then each $sigma$-flag on $|sigma|+2k$ vertices should appear among the $n^2$ products $(x_i x_j)_{i,j=1}^n$ with a total coefficient of $1$.
Finally, I should note that in many applications, we are considering a subset of all graphs (for example, all triangle-free graphs). In that case, some of the flags in these computations may vanish, because they contain a forbidden subgraph.
Normalizing factors
In almost all cases, the only averaging operator we use is $[![cdot]!]_sigma$, going from $sigma$-flags to graphs. So I'll just talk about this one.
Here, the good news is that the graph $H$ we get as a result of $[![F]!]_sigma$ is fixed: it is the underlying graph of $F$, where we just forget about $sigma$. Only the coefficient needs calculating.
To compute the coefficient, we consider all injections $theta : {1, 2, dots, |sigma|} to V(H)$, and count the fraction of them that actually produce a $sigma$-flag isomorphic to $F$.
For example, if we normalize , then we get the graph , which is isomorphic to $K_{2,3}$. An injection $theta$ gives us $F$ iff $theta(1), theta(3)$ degree-$2$ vertices and $theta(2)$ is a degree-$3$ vertex, which happens with probability $frac35 cdot frac24 cdot frac23 = frac15$, so the normalizing factor is $frac15$.
Computational considerations
Disclaimer: I have never actually attempted to implement flag algebra computations in software. But if we look at what is necessary, the main thing is checking for isomorphism of many small graphs (and flags).
There are well-known tools for checking for isomorphism: nauty and bliss are two that come to mind. They are easy to adapt to checking for flag isomorphism, because that matches how graph isomorphism checkers already work. They can all check for isomorphisms of colored graphs, in which each vertex is assigned a color; two colored graphs are isomorphic if there is a bijection respecting both graph structure and color of vertices. If you assign each vertex of $sigma$ its own color, and use a final color on the non-$sigma$ vertices, you get a test for isomorphisms of $sigma$-flags.
(Essentially, the reason that graph isomorphism tools do this is that they work by starting with a partition of the vertex set of a graph into "different-looking" vertices, and refine it until all vertices that are in principle distinguishable have been put in different classes of the partition. Having this partition restricts the number of bijections we need to check for being isomorphisms. This also explains why highly symmetric graphs are a worst case for graph isomorphism.)
Also, you will not need to deal with very large graphs in flag algebra computations: the number of possible flags blows up too quickly for that to become a problem. So checking for flag isomorphism by brute force is not as terrible an option as it may seem. (Although special tools may well be faster anyway, assuming that Sage can efficiently interface with them.)
Finally, all of these calculations can be done using tools such as Flagmatic.
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
$endgroup$
We should distinguish between two relevant quantities:
- The coefficient of $H$ in the product $F_1 cdot F_2$, where $F_1, F_2$ are $sigma$-flags on $k_1, k_2$ vertices and $H$ is a $sigma$-flag on $k_1+k_2-|sigma|$ vertices.
- The coefficient of $H$ in the average $[![F]!]_sigma$, where $F$ is a $sigma$-flag and $H$ the underlying graph. This is what Razborov calls the "normalizing factor" $q_sigma(F)$.
In your multiplication table, you are doing both operations at once. This is not uncommon in papers, since it often gives us the values we are actually interested in, but it makes it harder to see what happens.
(As a side note, I should mention that I am just going to discuss graphs and some of this may be false or meaningless for more general flag algebras.)
If you look at typical objective functions in a flag algebra semidefinite program, they are a $max$ of many terms. (For example, see the expression which takes up most of p. 20 in Grzesik.) Computing one of those terms directly would be obnoxious, but mostly we don't have to do that. Instead, we do a bunch of easy computations, each one of which contributes to a few of the terms, and then we combine everything we've got.
Coefficients in multiplication
As far as multiplication goes, both of your examples are actually fairly easy: the difficulty of multiplying $sigma$-flags on $k$ vertices scales primarily with $k-|sigma|$. So, although there are many $sigma_i$-flags in the calculation for Erdős's pentagon problem (and you wouldn't want to do them all by hand), each calculation is short and they are all very similar.
There are two steps to multiplication: first, we find all the $sigma$-flags that appear in the product, and second, we find their coefficients.
For the first step, although we could just enumerate all possible $sigma$-flags of the right size, there is a shortcut, using "don't-care" edges. Embed the two $sigma$-flags in a $sigma$-flag with $|sigma|+k_1+k_2$ additional vertices, so that $sigma$ with the first $k_1$ vertices forms $F_1$ and $sigma$ with the last $k_2$ vertices forms $F_2$. Between the first $k_1$ and last $k_2$ additional vertices, put "don't-care" edges that could either be present or absent. Then try all possibilities for those edges.
For example, when multiplying together and , the $sigma_2$-flags appearing in the product are all forms of , where the dashed edge is a don't-care edge that could appear or not appear. The two $sigma_2$-flags that have this property are and .
For the second step, we compute the density Grzesik calls $d(F_1,F_2,H;theta)$: the probability that if we pick two $sigma$-flags of the right size from $H$, disjoint outside the vertices of $sigma$, the first will be $F_1$ and the second will be $F_2$. In this case, both for and , the density is $frac12$. There are two ways to pick two $sigma_0$-flag with $4$ vertices out of : you pick which non-$sigma_0$ vertex goes in the first flag, and which non-$sigma_0$ vertex goes in the second flag. Either way, one will be and one will be , but it matters which one is which: you have a $frac12$ chance of getting them in the right order. The same calculation goes for . Therefore
$cdot$$= dfrac12$$+dfrac12$.
In fact, whenever you multiply together distinct $sigma$-flags on $|sigma|+1$ vertices, you'll get two flags with coefficients of $frac12$, by the exact same reasoning. Whenever you square a $sigma$-flag on $|sigma|+1$ vertices, you'll get two flags with coefficients of $1$. However, the $frac12$ term washes out in applications: if you're computing $mathbf{x}^{mathsf T}Pmathbf x$ where $mathbf x$ is a vector of $sigma$-flags, then each product of distinct flags will occur twice (as $x_i p_{ij} x_j$ and as $x_j p_{ji} x_i$) while the square of each flag will only occur once (as $x_i p_{ii} x_i$).
For a more complicated example, consider the product of the two possible graphs on $2$ vertices: "edge" and "non-edge". Here, the flags ($4$-vertex graphs) appearing in the product are all those represented by the diagram with four don't-care edges. With repetition, there would be $16$ such graphs, but there are only $7$ distict ones: , , , , , , and .
For each of these flags, we should compute the coefficient. This is the probability that if we choose a pair of vertices ${a,b}$ (in $binom 42$ ways) and another disjoint pair of vertices ${c,d}$ (in $binom 22$ ways) then $ab$ will be an edge and $cd$ will not be. So just check all $binom 42 binom 22$ choices for all $7$ flags, getting
$dfrac16$$+dfrac13$$+dfrac12$$+dfrac12$$+dfrac16$$+dfrac13$$+dfrac16$.
As a sanity check, if $mathbf x$ is the vector of all $n$ possible $sigma$-flags on $|sigma|+k$ vertices, then each $sigma$-flag on $|sigma|+2k$ vertices should appear among the $n^2$ products $(x_i x_j)_{i,j=1}^n$ with a total coefficient of $1$.
Finally, I should note that in many applications, we are considering a subset of all graphs (for example, all triangle-free graphs). In that case, some of the flags in these computations may vanish, because they contain a forbidden subgraph.
Normalizing factors
In almost all cases, the only averaging operator we use is $[![cdot]!]_sigma$, going from $sigma$-flags to graphs. So I'll just talk about this one.
Here, the good news is that the graph $H$ we get as a result of $[![F]!]_sigma$ is fixed: it is the underlying graph of $F$, where we just forget about $sigma$. Only the coefficient needs calculating.
To compute the coefficient, we consider all injections $theta : {1, 2, dots, |sigma|} to V(H)$, and count the fraction of them that actually produce a $sigma$-flag isomorphic to $F$.
For example, if we normalize , then we get the graph , which is isomorphic to $K_{2,3}$. An injection $theta$ gives us $F$ iff $theta(1), theta(3)$ degree-$2$ vertices and $theta(2)$ is a degree-$3$ vertex, which happens with probability $frac35 cdot frac24 cdot frac23 = frac15$, so the normalizing factor is $frac15$.
Computational considerations
Disclaimer: I have never actually attempted to implement flag algebra computations in software. But if we look at what is necessary, the main thing is checking for isomorphism of many small graphs (and flags).
There are well-known tools for checking for isomorphism: nauty and bliss are two that come to mind. They are easy to adapt to checking for flag isomorphism, because that matches how graph isomorphism checkers already work. They can all check for isomorphisms of colored graphs, in which each vertex is assigned a color; two colored graphs are isomorphic if there is a bijection respecting both graph structure and color of vertices. If you assign each vertex of $sigma$ its own color, and use a final color on the non-$sigma$ vertices, you get a test for isomorphisms of $sigma$-flags.
(Essentially, the reason that graph isomorphism tools do this is that they work by starting with a partition of the vertex set of a graph into "different-looking" vertices, and refine it until all vertices that are in principle distinguishable have been put in different classes of the partition. Having this partition restricts the number of bijections we need to check for being isomorphisms. This also explains why highly symmetric graphs are a worst case for graph isomorphism.)
Also, you will not need to deal with very large graphs in flag algebra computations: the number of possible flags blows up too quickly for that to become a problem. So checking for flag isomorphism by brute force is not as terrible an option as it may seem. (Although special tools may well be faster anyway, assuming that Sage can efficiently interface with them.)
Finally, all of these calculations can be done using tools such as Flagmatic.
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
answered Feb 3 at 19:39
Misha LavrovMisha Lavrov
48.6k757107
48.6k757107
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
add a comment |
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Thanks for the detailed explanation. I am hesitant to use Flagmatic since I don't understand how it works (at the software/algorithm level as opposed to the math level), and numerous attempts to parse through the code haven't been productive.
$endgroup$
– Richard
Feb 4 at 20:17
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
$begingroup$
Your reason makes sense to me, but I think my answer would have been incomplete if I did not mention Flagmatic :)
$endgroup$
– Misha Lavrov
Feb 4 at 23:53
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3095299%2fefficient-algorithm-for-calculating-flag-products%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
