Return to Question

added 10 characters in body

view source

edited Dec 14 2011 at 15:24

Given a set $A$ of subsets of ${1, \ldots n}$ which is closed under taking subsets, let $X(A)$ be the corresponding simplicial complex, i.e. simplices of $X(A)$ are elements of the set $\bar A$, and gluing is induced by containment of subsets)

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of ${1,\ldots, n}$, closed under taking subsets.

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of ${1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$?)

Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of $n$ alone. Please note that the size of the input can be exponential in $n$.

In principle the input $A$ and $B$ might consist of $2^n$, 2^n$ subsets, so this is a lower bound for the problem, because the algorithm needs to read the input.

On the other hand the trivial algorithm of checking each permutation takes at most $\mathcal O(2^n\cdot n!)$ steps.

deleted 861 characters in body

view source

edited Dec 14 2011 at 15:18

Łukasz Grabowski
2,771●5●16

One can obviously express instances of

In principle the graph isomorphism problem as instances input might consist of the problem above, by considering 1-dimensional simplicial complex. So one shouldn'h hope for an algorithm which takes less than $2^{\mathcal O(\sqrt{n\cdot log(n)}})$ steps in the worst case (2^n$, so this is a lower bound taken from wikipedia).

Conversely, one can also express instances of for the problem above as graph isomorphism problem, by adding additional vertex for each face, and joining the vertices of the given face with because the additional vertex (and perhaps doing something funny with this vertex as to assure that graph isomorphism must map additional vertices corresponding to k-dimensional faces in one graph to additional vertices corresponding algorithm needs to k-dimensional faces in read the other graph)input.This produces a graph which can have as many as $2^n+n$ vertices, so this leads to an

On the other hand the trivial algorithm with running time bounded by of checking each permutation takes at most $2^{\mathcal O(\sqrt{2^n\cdot n\cdot log(2)}})$. Of course it's not clear if this algorithm really is so bad, as the resulting graphs are very special\mathcal O(2^n\cdot n!)$ steps.

clarification

view source

edited Dec 14 2011 at 15:01

Łukasz Grabowski
2,771●5●16

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of ${1,\ldots, n}$, closed under taking subsets.

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of ${1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$?)

One can obviously express instances of the graph isomorphism problem as instances of the problem above, by considering 1-dimensional simplicial complex. So one shouldn'h hope for an algorithm which takes less than $2^{\mathcal O(\sqrt{n\cdot log(n)}})$ steps in the worst case (bound taken from wikipedia).

Conversely, one can also express instances of the problem above as graph isomorphism problem, by adding additional vertex for each face, and joining the vertices of the given face with the additional vertex (and perhaps doing something funny with this vertex as to assure that graph isomorphism must map additional vertices corresponding to k-dimensional faces in one graph to additional vertices corresponding to k-dimensional faces in the other graph). This produces a graph which can have as many as $2^n+n$ vertices, so this leads to an algorithm with running time bounded by $2^{\mathcal O(\sqrt{2^n\cdot n\cdot log(2)}})$. Of course it's not clear if this algorithm really is so bad, as the resulting graphs are very special.

deleted 48 characters in body

view source

edited Dec 14 2011 at 14:14

Łukasz Grabowski
2,771●5●16

Given a set $A$ of subsets of ${1, \ldots n}$ which is closed under taking subsets, let $X(A)$ be the corresponding simplicial complex"generated" by $A$, , i.e. simplices of $X(A)$ are elements of the set $\bar A$, and the set $\bar A$ gluing is the smallest set of subsets of ${1,\ldots, n}$ which contains all elements induced by containment of $A$ and is closed under taking subsetsand intersections.)

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of ${1,\ldots, n}$, closed under taking subsets.

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of ${1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$)X(B)$?)

Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of $n$ alone.

view source

asked Dec 14 2011 at 12:50

Łukasz Grabowski
2,771●5●16

algorithms for comparing two simplicial complexes

Given a set $A$ of subsets of ${1, \ldots n}$ let $X(A)$ be the simplicial complex "generated" by $A$, i.e. simplices of $X(A)$ are elements of the set $\bar A$, and the set $\bar A$ is the smallest set of subsets of ${1,\ldots, n}$ which contains all elements of $A$ and is closed under taking subsets and intersections.

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of ${1,\ldots, n}$

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of ${1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$)

Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of $n$ alone.