User pinying - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T11:36:42Z http://mathoverflow.net/feeds/user/24958 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114478/categorical-nomenclature Categorical nomenclature Pinying 2012-11-26T02:42:56Z 2012-11-26T06:49:13Z <p>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.</p> <p>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:</p> <p>$$x_{j\ell}u_{ij} = w_{k\ell}x_{ik} \text{ as morphisms }c_i \to d_\ell.$$</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/114131/relating-two-notions-of-geometric-realization Relating two notions of geometric realization Pinying 2012-11-22T03:14:23Z 2012-11-22T12:36:36Z <p>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 (<strong>a</strong>) the support of each $\alpha$ is a simplex, and (<strong>b</strong>) 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.</p> <p>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$</p> <p>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$.</p> <p>My question is this:</p> <blockquote> <p>What is the relation between $|K|$ and $X$, more specifically between $|\sigma|$ and $X_\sigma$ for each simplex $\sigma \in K$?</p> </blockquote> <p>Here is some idea of what type of answer I am hoping for:</p> <p>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? </p> <p>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$?</p> http://mathoverflow.net/questions/112290/heuristic-for-partitioning-n-partite-weighted-graphs-into-bounded-n-cliques (Heuristic for) Partitioning n-partite weighted graphs into bounded n-cliques Pinying 2012-11-13T15:36:07Z 2012-11-14T22:37:01Z <p>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$.</p> <p>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.</p> <blockquote> <p>Given $X$ and $r$ as above, is there an efficient algorithm that answers <strong>yes</strong> if it is possible decompose $X$ into $k$ cliques so that the weight of each clique is less than or equal to $r$, and <strong>no</strong> if there is no such decomposition?</p> </blockquote> <p>My question is similar to the one <a href="http://mathoverflow.net/questions/99752/clique-weight-optimal-matchings-on-n-partite-graphs" rel="nofollow">here</a> 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$.</p> <p><strong>Update:</strong> Since the problem is unfortunately NP complete (see the answer below),</p> <blockquote> <p>Are there any known polynomial-time approximations and/or practical heuristics to attack such a problem?</p> </blockquote> http://mathoverflow.net/questions/101598/homotopy-of-random-simplicial-complexes Homotopy of random simplicial complexes Pinying 2012-07-07T19:13:02Z 2012-07-23T01:42:37Z <p>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 <a href="http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model" rel="nofollow">Erdős–Rényi</a> model $G(n,p)$ for generating random graphs. </p> <p>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 <a href="http://www.math.ias.edu/~mkahle/Betti.pdf" rel="nofollow">this</a> paper.</p> <p>I want to ask</p> <blockquote> <p>What is known about the properties of the fundamental group (or higher homotopy groups) of random simplicial complexes?</p> </blockquote> <p>If there is a good reference, that would be enough. I can not find one on google. Thank you for your time.</p> http://mathoverflow.net/questions/114131/relating-two-notions-of-geometric-realization/114140#114140 Comment by Pinying Pinying 2012-11-26T02:12:48Z 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! http://mathoverflow.net/questions/114131/relating-two-notions-of-geometric-realization/114140#114140 Comment by Pinying Pinying 2012-11-22T11:40:36Z 2012-11-22T11:40:36Z In your pairs $(U,x)$ do you require $x \in U$? http://mathoverflow.net/questions/101598/homotopy-of-random-simplicial-complexes/101626#101626 Comment by Pinying Pinying 2012-07-08T16:40:33Z 2012-07-08T16:40:33Z Thank you for the answer.