User pinying - MathOverflow

Categorical nomenclature

2012-11-26T02:42:56Z

I have a category $C$ and will build a new category $X_C$ out of it as follows. I hope this is a standard construction and that I can find somewhere in the literature its definition and properties worked out. Since I do not know the correct search string despite trying MacLane's book and the nlab, I ask here.

Each object of $X_C$ is a sub-collection $(v_{ij}:c_i \to c_j)$ of morphisms in $C$. The morphisms in $X_C$ between $(v_{ij}:c_i \to c_j)$ and $(w_{k\ell}: d_k \to d_\ell)$ are collections of morphisms $x_{ik} : c_i \to d_k$ of $C$ so that for any quadruple $(i,j,k,\ell)$ the obvious commutation relations hold, namely:

$$ x_{j\ell}u_{ij} = w_{k\ell}x_{ik} \text{ as morphisms }c_i \to d_\ell.$$

What is this $X_C$ called? Thinking topologically, it looks like the "join" of the morphism diagrams, but google says nothing useful about "join categories" and the like.

The motivation is as follows: my category $C$ consists of objects where each morphism represents a distance between source and target. Under certain compatibility conditions on morphisms (the obvious commutation relations), I can find a "witness" object within the desired distance of all objects in a collection. The next step is to see how these witnesses evolve as $C$ itself is transformed. For this I need a way to map compatible object collections to other compatible object collections.

Relating two notions of geometric realization

2012-11-22T03:14:23Z

Let $K$ be an abstract simplicial complex on the (finite) vertex set $V$. The geometric realization $|K|$ is typically defined (see Spanier's book for instance) as the collection of functions $\alpha:V \to \mathbb{R}$ so that (a) the support of each $\alpha$ is a simplex, and (b) the sum $\sum_{v \in V}\alpha(v)$ equals $1$. Now each (closed) simplex $\sigma$ is realized as the collection of $\alpha \in K$ so that $\alpha(v) \neq 0$ implies $v \in \sigma$. From this one knows the star of each simplex.

A simplicial approximation of $f:|K| \to |L|$ is a simplicial map $g:K \to L$ so that $f(\text{star }\sigma) \subset \text{star }g(\sigma)$ for each simplex $\sigma \in K$. It is a standard result that the Piecewise Linear map induced by $g$ is homotopy equivalent to $f$

Now consider the case where $K$ is not abstract, but rather $V$ is an open cover of some topological space $X$. So, each simplex corresponds to an actual topological space, i.e., a non-empty intersection of some finite open sets in $X$. Let's call this $X_\sigma$.

My question is this:

What is the relation between $|K|$ and $X$, more specifically between $|\sigma|$ and $X_\sigma$ for each simplex $\sigma \in K$?

Here is some idea of what type of answer I am hoping for:

In the case where $X$ is paracompact and $V$ is a contractible cover, the nerve theorem applies and I know that $X$ and $|K|$ are homotopy equivalent. But is there a more general relationship between these two notions of realization of which the Nerve theorem is a consequence?

Furthermore, is there some functoriality to the nerve theorem? That is, assume you are given contractible covers $U$ and $V$ of $X$ and $Y$ generating the nerves $K$ and $L$. Given a function $f : X \to Y$ and a simplicial map $g:K \to L$, is there some magic analogoue of the star condition like $f(X_\sigma) \subset Y_{g(\sigma)}$ that makes $g$ induce a map homotopy equivalent to the composite $|K| \to X \to Y \to |L|$ where the maps on the edge come from the nerve theorem and the map in the middle is $f$?

(Heuristic for) Partitioning n-partite weighted graphs into bounded n-cliques

2012-11-13T15:36:07Z

Consider a complete $N$-partite graph $X$ with $X_n$ denoting the $n$-th vertex bin for $1 \leq n \leq N$, where we may assume that each $X_n$ has $k$ vertices for some universal constant $k$. Assume that the edges have positive real weights and also consider a real number $r \geq 0$.

A clique is a collection of $N$ vertices, one from each bin. By completeness of $X$, any two such vertices are connected by an edge. The weight of a clique is defined to be the maximal weight among all edges contained in that clique.

Given $X$ and $r$ as above, is there an efficient algorithm that answers yes if it is possible decompose $X$ into $k$ cliques so that the weight of each clique is less than or equal to $r$, and no if there is no such decomposition?

My question is similar to the one here but I am not looking to minimize the clique weight across all possible decompositions, just to confirm that there is a decomposition satisfying the upper bound of $r$.

Update: Since the problem is unfortunately NP complete (see the answer below),

Are there any known polynomial-time approximations and/or practical heuristics to attack such a problem?

Homotopy of random simplicial complexes

2012-07-07T19:13:02Z

A random graph on $n$ vertices is defined by selectiung the edges according to some probability distribution, the simplest case being the one where the edge between any two vertices exists with probability $p = \frac{1}{2}$. I believe this is the Erdős–Rényi model $G(n,p)$ for generating random graphs.

Similarly, in higher dimensions we can construct random simplicial complexes on $n$ vertices in many ways. One such method is as follows: fix a top dimension $d$, and now define the random simplicial model $S_d(n,p)$ where each $d$ simplex spanning any $d+1$ vertices exists with probability $p$. Some work has been done investigating the homology of such complexes in limiting cases, see for example this paper.

I want to ask

What is known about the properties of the fundamental group (or higher homotopy groups) of random simplicial complexes?

If there is a good reference, that would be enough. I can not find one on google. Thank you for your time.

Comment by Pinying

2012-11-26T02:12:48Z

Thank you. If you have any ideas about the functoriality question, please also write them down. In any case, I will accept this nice answer!

Comment by Pinying

2012-11-22T11:40:36Z

In your pairs $(U,x)$ do you require $x \in U$?

Comment by Pinying

2012-07-08T16:40:33Z

Thank you for the answer.