User thorny - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T00:40:23Z http://mathoverflow.net/feeds/user/2368 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70127/stable-singularities-of-smooth-map-mathbb-r3-to-mathbb-r4/70224#70224 Answer by Thorny for Stable singularities of smooth map $\mathbb R^3\to \mathbb R^4$ Thorny 2011-07-13T13:35:17Z 2011-07-13T13:35:17Z <p>The codimension of $\Sigma^2$-points in the source for a codimension $k$ map is $2(k+2)$, in this case that's $6>3$, so you only get combinations of Morin and regular points. From the Morins, the cusp has codimension $2(k+1)=4$, so you have no cusps either and need to keep track only of the regular points (codimension $k=1$ in the target) and fold points (canonical form $(x,y,z) \mapsto (x^2,xy,y,z)$, codimension $2k+1=3$ in the target). So, you have the regular points with multiplicity 1 to 4, the fold curves and fold curves intersecting transversally a regular "branch", and that's all. What you wrote does not look like a stable singularity to me.</p> http://mathoverflow.net/questions/36061/probability-of-outcomes-algorithm/36062#36062 Answer by Thorny for Probability of Outcomes Algorithm Thorny 2010-08-19T07:24:52Z 2010-08-19T07:24:52Z <p>Dynamic programming (and/or Stackoverflow) is your friend. You can easily calculate the probabilities of all the outcomes of the first coin flip, and you can easily move from the probabilities of all the outcomes of the first n coin flips to the probabilities of all the outcomes of the first n+1 coin flips (it's a linear transformation).</p> http://mathoverflow.net/questions/32477/smallest-area-shape-that-covers-all-unit-length-curve/32490#32490 Answer by Thorny for Smallest area shape that covers all unit length curve Thorny 2010-07-19T13:13:22Z 2010-07-19T13:13:22Z <p>Reportedly R. Norwood, G. Poole, M. Laidacker: The Worm Problem of Leo Moser, Discrete &amp; Computational Geometry 7 (1992), 153-162. has an example of area $\sqrt{3}/12+\pi/24$ (a 60 degree sector of a circle with two triangular "wings"), and this was the best known in 1999.</p> http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an/30767#30767 Answer by Thorny for In a graph, is it always possible to construct a set of cycle bases, with each and every edge Is shared by at most 2 cycle bases? Thorny 2010-07-06T12:38:13Z 2010-07-06T12:38:13Z <p>Consider the complete graph on 7 vertices. It has 21 edges, so any set of cycles that utilizes each edge at most twice has size at most 42/3=14. But the cycle space of the graph has dimension 21-7+1=15, so you cannot have a basis with the requested property.</p> http://mathoverflow.net/questions/29807/binary-sequences-of-length-2n/29889#29889 Answer by Thorny for Binary Sequences of Length 2n Thorny 2010-06-29T09:42:59Z 2010-06-29T10:22:56Z <p>Given the symmetry between 0 and 1 past the end of the first "run" of n equal digits, it does not matter whether we count zeros or ones after a "run" of n zeros. That is, if we only count zeros after n zeros and ones after n ones, we should get $n\binom{2n}{n}$. This count is the total number of excess (over n) digits in all the bit patterns of length 2n, and these are split evenly between zeros and ones, denote by $S=\sum_{k=0}^{n}k\binom{2n}{n+k}$ this half-count.</p> <p>We have $\binom{2n}{n+k}(n+k) = \binom{2n}{n+k-1}(n-k+1)$ -- both are the number of partitions of 2n elements into sets of size n+k-1, n-k and 1. Hence $$S+\sum_{k=0}^{n} n\binom{2n}{n+k} = \sum_{k=0}^{n} \binom{2n}{n+k}(n+k) = \sum_{k-1=-1}^{n-1} \binom{2n}{n+(k-1)}(n-(k-1)) =$$ $$= \sum_{k-1=-1}^{n} \binom{2n}{n+(k-1)}(n-(k-1)) = \binom{2n}{n-1}(n+1) + \sum_{k=0}^{n} n\binom{2n}{n+k} - S$$ and we have $2S=(n+1)\binom{2n}{n-1} = n\binom{2n}{n}$ as required.</p> <p>This is essentially counting all zeros in the patterns which have an excess of zeros with weight -1 and all ones in the patterns which have at least as many ones as zeros with weight +1, and noticing that we get $n\binom{2n}{n}$ by straight counting (only the n+n patterns are not pairwise annihilated with their complementary sequence) on one hand and $2S$ on the other hand (we can pair a bit pattern with a selected majority digit with a pattern with a selected minority digit and count each excess majority digit twice in doing so).</p> http://mathoverflow.net/questions/28299/vertex-connectivity-of-random-graphs/28366#28366 Answer by Thorny for Vertex connectivity of random graphs? Thorny 2010-06-16T09:16:29Z 2010-06-16T09:16:29Z <p>The expected connectivity cannot be higher than the expected minimal degree, which jumps to roughly $pn$ after getting into the range $p>>\frac{\log n}{n}$. On the other hand, sloppily counting potential clusters of size $m &lt; n/2$ that have boundaries of less than $k$ vertices gives a probability of $\binom{n}{m}\binom{n-m}{k}(1-p)^{m(n-m-k)}$, which is for $k &lt; &lt; n$ decreasing in $m$ up to $m\approx \frac{n-k}{2}$ and increasing after that value, so we can get an estimate by considering only $m=1$ (checking for vertices with at most $k$ neighbours) and $m=\frac{n}{2}$: $$\binom{n}{n/2}\binom{n/2}{k}(1-p)^{n(n-2k)/4} &lt; exp(n \log 2+k \log n - pn(n-2k)/4) &lt;$$ $$&lt; exp(n \log 2 - pn(\frac{n}{4}-\frac{k}{2}-\log n)) &lt; exp(-\frac{n \log n}{4} + n \log 2 +2(\log n)^2),$$ this latter number tending to $0$ fast enough to ignore it. So, the expected connectivity is the expected minimal degree and is roughly $pn$ once $p$ exceeds $\log n/n$. Do you need the behaviour of expected connectivity specifically in this region?</p> http://mathoverflow.net/questions/27032/pushing-convex-bodies-together/27038#27038 Answer by Thorny for Pushing convex bodies together Thorny 2010-06-04T12:04:45Z 2010-06-04T12:10:05Z <p>The sets $\{ (A(t),t)|t\in \mathbb{R} \} \subset \mathbb{R}^4$ and $\{ (B(t),t)|t\in \mathbb{R} \} \subset \mathbb{R}^4$ are convex, their intersection $K$ is a bounded convex set, and $f(t)$ is the volume of the slice of $K$ at height $t$. By Brunn-Minkowski inequality, this is log-concave, so definitely unimodal.</p> http://mathoverflow.net/questions/26655/oriented-cobordism-rings/26678#26678 Answer by Thorny for Oriented Cobordism Rings Thorny 2010-06-01T07:45:22Z 2010-06-01T07:45:22Z <p>I would also recommend Wall's <a href="http://www.jstor.org/stable/1970136" rel="nofollow">Determination of the cobordism ring</a> as a more primary source, it also contains the fact that all torsion is of order 2.</p> http://mathoverflow.net/questions/24347/combination-with-replacement/24348#24348 Answer by Thorny for Combination with replacement Thorny 2010-05-12T08:17:24Z 2010-05-12T08:17:24Z <p>You are counting samples that actually contain repetitions too few times. E.g. the sample that consists of the same object has to be counted as 1 possibility and you count it as 1/k!.</p> http://mathoverflow.net/questions/21649/how-to-prove-that-w-1ew-1dete/21654#21654 Answer by Thorny for How to prove that w_1(E)=w_1(detE) ? Thorny 2010-04-17T09:36:36Z 2010-04-17T09:36:36Z <p>$E \oplus det E$ is orientable (its structure group $O(n)$ is represented in $SO(n+1)$), so its $w_1$ vanishes; and $w_1(E \oplus det E) = w_1(E) + w_1(det E)$.</p> http://mathoverflow.net/questions/20730/about-dense-orbits-on-dynamical-systems/20736#20736 Answer by Thorny for About dense orbits on dynamical systems Thorny 2010-04-08T14:48:54Z 2010-04-08T14:48:54Z <p>Take $M=\mathbb{R} / \mathbb{Z}$, $T(x)=x+\alpha$ for some $\alpha$. If $\alpha$ is irrational, all orbits will be dense. Set $p=0$, then the set $A$ can be made to be infinite by choosing an $\alpha$ that can be approximated well: choose $\alpha$ from $B_1(\delta-2\cdot 10^{-k_1})$ for some $k_1$, then modify it at most by $10^{-k_1}$to make $10^{k_1} \alpha -[10^{k_1} \alpha] \in B_{10^{k_1}}(\delta-2 \cdot 10^{-k_2})$ and repeat ad infinitum.</p> http://mathoverflow.net/questions/17960/google-question-in-a-country-in-which-people-only-want-boys/17966#17966 Answer by Thorny for Google question: In a country in which people only want boys Thorny 2010-03-12T10:23:33Z 2010-03-12T10:23:33Z <p>Another way to look at the "official" solution is to notice that for statistical purposes it does not matter which couple gets the next child. You "request" children from the couples in whatever manner you want, you always get a 1:1 expected ratio in boys and girls, regardless of the pattern in which you choose the next couple to produce another child.</p> http://mathoverflow.net/questions/15804/when-does-a-probability-measure-take-all-values-in-the-unit-interval/15807#15807 Answer by Thorny for When does a probability measure take all values in the unit interval? Thorny 2010-02-19T11:04:20Z 2010-02-22T08:17:31Z <p>This is a property of $\mu$, not that of $\mathcal A$, and it is called being atomless. It is equivalent to not having sets $A \in \mathcal A$ of positive measure such that for all $B \in \mathcal A$, $B \subseteq A$ the measure $\mu(B)$ is either 0 or $\mu(A)$.</p> <p>edit: <a href="http://en.wikipedia.org/wiki/Atom%5F%28measure%5Ftheory%29" rel="nofollow">Wikipedia article</a>, complete with the proof of the property you describe from atomlessness.</p> <p>edit: yup, the comments are right and I'm wrong. The precise condition for finite measures composed entirely of atoms to have full range is $a_n \leq \sum_{j>n} a_j$ - it is clearly necessary as $a_n-\varepsilon$ has to be produced somehow, and the greedy algorithm shows sufficiency.</p> http://mathoverflow.net/questions/14964/estimate-population-size-based-on-repeated-observation/14988#14988 Answer by Thorny for Estimate population size based on repeated observation Thorny 2010-02-11T10:18:14Z 2010-02-11T10:18:14Z <p>Maximum likelihood estimate is the smallest $n$ for which $$\left( 1+\frac{1}{n} \right)^k \leq \frac{n}{n-k+1},$$ that gives a value of $n$ asymptotically equal to $\frac{k^2}{2}$, consistently with the Birthday Paradox. Not sure whether an unbiased estimate would be better for any practical purpose; maybe you do have an a priori distribution for which a Bayesian estimate makes sense?</p> http://mathoverflow.net/questions/14264/an-integral-arising-in-statistics2/14265#14265 Answer by Thorny for An integral arising in statistics(2) Thorny 2010-02-05T13:47:27Z 2010-02-05T13:47:27Z <p>For $K=1$ your arc passes through the pole of the function $\frac{exp(ixy)}{1+y^2} = \frac{exp(ixy)}{2i}\left(\frac{1}{y-i}-\frac{1}{y+i}\right)$, so you don't get a sensible value (the discontinuity of the integrand is asymptotically $\frac{c}{t}$ for $t$ around $0$).</p> http://mathoverflow.net/questions/13972/shortest-key-for-the-monte-carlo-lock-of-smullyan/14127#14127 Answer by Thorny for Shortest Key for the Monte Carlo Lock of Smullyan Thorny 2010-02-04T09:43:35Z 2010-02-05T11:58:32Z <p>Edited in recognition of closed-mindedness.</p> <p><s>My brute force search shows no keys shorter than 10. Here are the only keys of length 10 and 11 respectively:</p> <p>RVLVQRVLVQ VRLVQVRLVQ</p> <p>VLRVQVLRVQQ VLVRQVLVRQQ</p> <p>Curiously, there are no keys of length 12. </s></p> <p>The only word of length 7 that does not crash under iteration is RRQRRQQ, and it evolves unboundedly. There are 74 words of length 8 that grow to over 30 letters, I think none of them cycles, and there are two eventually cycling words, one you gave and the other its pair RQVRLVQQ. The first time an odd period greater than 1 appears is at length 12, these are the originating words (all end up with period 3):</p> <p>RQQVLLRLVQQQ</p> <p>RLQVLLRLVQQQ</p> <p>RQLVLLLRVQQQ</p> <p>RQVLLLVLRQQQ</p> <p>RQLVLLLVRQQQ</p> <p>RQLVLLLRVLQQ</p> <p>RQVLLLVLRLQQ</p> <p>RQLVLLLVRLQQ</p> <p>RQLLVLLRLVQQ</p> <p>RQVLLLVQQRQQ</p> <p>RQVLLLVLQRQQ</p> <p>RQLVLLLVQRQQ</p> http://mathoverflow.net/questions/14129/describing-sun-c/14131#14131 Answer by Thorny for Describing $SU(n,C)$ Thorny 2010-02-04T10:31:06Z 2010-02-04T10:31:06Z <p>Think of $SU(n)$ as the space of orthonormed bases in $C^n$ with the additional property of the determinant being equal to $1$ out of all the unit length complex numbers. Then fixing one of the vectors restricts the others to the orthogonal hyperplane and the additional requirement remains intact for some parametrization of said hyperplane. In the coordinate system defined by such a base, all the others with the same first vector differ only by a matrix of the form $1 \oplus A$ with some $A \in SU(n-1)$.</p> <p>It does sound too much like a homework question to me though.</p> http://mathoverflow.net/questions/13813/construction-of-the-stiefel-whitney-and-chern-classes/13814#13814 Answer by Thorny for Construction of the Stiefel-Whitney and Chern Classes Thorny 2010-02-02T10:47:42Z 2010-02-02T10:47:42Z <p>The easy way of comparing those is to check that they both satisfy the axioms and then use the unicity of the characteristic classes. The splitting lemma (every vector bundle can be pulled back from a sum of line bundles with a map that induces an injective map in cohomology) makes unicity trivial.</p> <p>As to the second question, vector bundles' total spaces are homotopically equivalent to their bases. Maybe you meant Thom spaces? In this latter case, you get $G_{n-1}$ from $\gamma_n$, and this is one of the ways to calculate the cohomology ring of $G_n$.</p> http://mathoverflow.net/questions/12097/cobordisms-of-bundles/12179#12179 Answer by Thorny for Cobordisms of bundles? Thorny 2010-01-18T08:41:15Z 2010-01-18T08:46:55Z <p>I'll assume you're talking about principal G-bundles. These are classified by maps into $BG$, the base of the universal $G$-bundle, so if we have bundles classified by $f:E \to BG$ and $g:F \to BG$, you are looking for a bordism between $f$ and $g$ - whether there exists a $h : W \to BG$ connecting these classifying maps. So there is a bundle cobordism between the two bundles iff the bordism classes of $f$ and $g$ in $\mathfrak{N}n(BG)$ coincide, and if they do coincide, then the choice of $W$ is parametrized by the bordism group $\mathfrak{N}_{n+1}(BG)$. I don't know an algorithmic way to obtain the class $[f]$ from $E$, but there is a splitting $\mathfrak{N}_n(BG) = \oplus H_j(BG) \otimes \mathfrak{N}_{n-j}$ which can help identify some bundles' classes.</p> http://mathoverflow.net/questions/11641/measure-between-the-counting-measure-and-the-lebegue-measure/11642#11642 Answer by Thorny for Measure between the counting measure and the Lebegue measure Thorny 2010-01-13T09:22:18Z 2010-01-13T09:22:18Z <p>Hausdorff measures of dimensions between 0 and 1 are a continuous spectrum of examples.</p> http://mathoverflow.net/questions/11521/what-is-affine-invariant-used-in-computer-vision/11527#11527 Answer by Thorny for What is affine invariant used in computer vision? Thorny 2010-01-12T11:13:50Z 2010-01-12T11:13:50Z <p>The ratio of areas of $ABC$ and $ACD$ is the ratio in which the line $AC$ divides the segment $BD$ (and it is the ratio of the heights of $B$ and $D$ over $AC$ respectively). This later ratio is affine invariant as affine transformations preserve length ratios on any line. Do make sure that your points don't collapse onto a single line though.</p> http://mathoverflow.net/questions/10864/efficiently-sampling-points-from-an-integer-lattice/10904#10904 Answer by Thorny for Efficiently sampling points from an integer lattice. Thorny 2010-01-06T10:00:20Z 2010-01-06T10:00:20Z <p>Is your weight convex or concave? Your property 1) is self-contradictory.</p> <p>In the concave case, you can just take a uniform, polynomial size sample from your simplex and select your point from this selection based on the actual weights.</p> <p>In the convex case, the same algorithm works if the average of $w$ is comparable to the maximum (both can be obtained in polynomial time by taking a uniform sample and by local descent respectively). If that is not the case, then you can test the same property for the projection of $w$ onto one of the facets of $\mathcal L$. If this projection has the required property, you sample from that facet according to the projected weight and then sample from the fiber over the selected point according to $w$ if the property still does not hold, you take an $n-2$ dimensional face etc. When you get down to vertices, you already know that $w$ is concentrated around the vertices of $\mathcal L$ and can find neighbourhoods of them containing almost all of the weight and having the property of the average of $w$ being comparable to the maximum of $w$ within these neighbourhoods (choose the entire $L$ and repeatedly shrink it by a factor of $1-\frac{1}{poly}$ and test the condition). From those neighbourhoods, choose one according to their total weight, and within the chosen one, take a polynomial size uniform sample and sample according to $w$ from within it.</p> http://mathoverflow.net/questions/9551/concentration-of-measure-for-gaussian-inner-products/9602#9602 Answer by Thorny for Concentration of measure for gaussian inner products Thorny 2009-12-23T08:47:02Z 2009-12-23T08:47:02Z <p>If you have 2 standard Gaussians in $\mathbb{R}^n$, their inner product is the sum of $n$ i.i.d. variables, with their common distribution fixed (and having finite moments), so you will get convergence to the appropriate Gaussian distribution in line with the central limit theorem, with exponential bounds coming from Hoeffding's inequality, say. Do you need tight bounds or asymptotics is enough?</p> http://mathoverflow.net/questions/9274/combinatorial-distance-euclidean-distance/9276#9276 Answer by Thorny for Combinatorial distance ≡ Euclidean distance Thorny 2009-12-18T15:13:35Z 2009-12-18T15:13:35Z <p>Not even all regular polytopes would have this property: any polytope having property X would have vertex figures with at most two kinds of distances between its vertices, and the 24- and 600-cells have the cube and the icosahedron for a vertex figure. Apart from those two examples, though, all regular polytopes have your property, and at least the regular prism has it as well as a regular pentagonal pyramid. No idea whether there are more examples.</p> http://mathoverflow.net/questions/8417/conditional-expectation-of-convolution-product-equals/8447#8447 Answer by Thorny for Conditional expectation of convolution product equals.. Thorny 2009-12-10T12:30:52Z 2009-12-10T12:30:52Z <p>As long as $\mathcal{G}$ is invariant under whatever operation you use in the convolution ("+", say), $\mathcal{G}$-measurable functions will convolve to $\mathcal G$-measurable functions and the equalities of integrals that define the conditional expectation will be automatic: for any $H \in \mathcal G$ we have $$\int_{\Omega} E(X|\mathcal{G}) * E(Y|\mathcal{G}) (t) \chi_H(t) dP(t) =$$ $$= \int_{\Omega\times\Omega} E(X|\mathcal{G})(x)E(Y|\mathcal{G})(y) \chi_{H}(x+y) dP(x)dP(y) =$$ $$= \int_{\Omega} E(X|\mathcal{G})(x) \int_{\Omega} E(Y|\mathcal{G})(y) \chi_{H}(x+y) dP(y)dP(x) =$$ $$= \int_{\Omega} E(X|\mathcal{G})(x) \int_{\Omega} Y(y) \chi_{H}(x+y) dP(y)dP(x) =$$ $$= \int_{\Omega} Y(y) \int_{\Omega} E(X|\mathcal{G})(x) \chi_{H}(x+y) dP(x)dP(y) =$$ $$= \int_{\Omega} Y(y) \int_{\Omega} X(x) \chi_{H}(x+y) dP(x)dP(y) =$$ $$= \int_{\Omega} X*Y(t) \chi_H(t) dP(t) = \int_{\Omega} E(X*Y|\mathcal{G})(t) \chi_H(t) dP(t)$$ If $\mathcal{G}$ is not invariant under the operation, though, I see no reason for the convolution to be $\mathcal{G}$-measurable. Is an example for that what you're requesting?</p> http://mathoverflow.net/questions/8331/approximately-known-matrix/8335#8335 Answer by Thorny for Approximately known matrix Thorny 2009-12-09T10:04:04Z 2009-12-09T10:04:04Z <p>If an invariant of nonsingular matrices is locally constant (I guess this is what's meant by "can be calculated precisely"), then it can only depend on the connected component of the linear group, which means only the orientation (sign of the determinant) can be calculated. For symmetric matrices, the same argument shows that any calculable quantity is a function of the signature since any matrix can be connected to a standard representatives of one of the signature classes using a continuous version of orthogonalization.</p> http://mathoverflow.net/questions/8202/systems-of-conics/8209#8209 Answer by Thorny for Systems of conics Thorny 2009-12-08T16:49:51Z 2009-12-08T17:01:56Z <p>As long as you can get an elementary proof of the fact that one of the families consists of ellipses with foci $A=(-c,0)$ and $B=(c,0)$ and the other consists of hyperbolas with the same foci, you can say that for any intersection point $P$ the angle between the lines $PA$ and $PB$ is dissected by the tangent to either curve - otherwise moving on the tangent would cause a first-order error in the sum $|PA|+|PB|$ or the difference $|PA|-|PB|$, respectively. Hence the two tangents are just the two angle bisectors of a pair of lines, and are thus orthogonal.</p> http://mathoverflow.net/questions/4939/is-there-a-compact-group-of-countably-infinite-cardinality/8194#8194 Answer by Thorny for Is there a compact group of countably infinite cardinality? Thorny 2009-12-08T15:02:43Z 2009-12-08T15:02:43Z <p>Given a compact Hausdorff space without isolated points, one can easily construct an embedding of the Cantor set into it: take two points, separate them with closure-disjoint open sets, repeat iteratively in each balls' closure. Since we started with a group, it is homogeneous, so either no points are isolated - and hence there is an embedded Cantor set of cardinality $2^\omega$ - or all points are isolated, which implies finiteness due to compactness.</p> http://mathoverflow.net/questions/8160/expressing-field-inclusions-by-polynomial-equalities-on-coefficients/8171#8171 Answer by Thorny for Expressing field inclusions by polynomial equalities on coefficients Thorny 2009-12-08T09:33:59Z 2009-12-08T10:53:24Z <p>If there was a nontrivial polynomial relation between the coefficients, it would be true for a dense subset (<s>reducibility is a nowhere dense condition</s> see comment below) of all polynomials of the form $(x^2+(\alpha +\beta\sqrt{2})x+\gamma+\delta\sqrt{2})(x^2+(\alpha -\beta\sqrt{2})x+\gamma-\delta\sqrt{2})$ with rational $\alpha,\beta,\gamma,\delta$, which would mean the same relation would be true for all real $\alpha,\beta,\gamma,\delta$ as well. But all quartic polynomials are of the form above with real $\alpha,\beta,\gamma,\delta$, so there are no nontrivial relations.</p> http://mathoverflow.net/questions/70127/stable-singularities-of-smooth-map-mathbb-r3-to-mathbb-r4/70224#70224 Comment by Thorny Thorny 2011-07-21T13:29:13Z 2011-07-21T13:29:13Z B. Morin: Formes canoniques des singularit&#233;s d'une application diff&#233;rentiable, Comp. Rend. Acad. Sci. Paris 260 (1965), pp. 5662-5665 should have it http://mathoverflow.net/questions/51008/limit-of-a-sequence-of-polygons/51017#51017 Comment by Thorny Thorny 2011-01-05T14:22:58Z 2011-01-05T14:22:58Z Just a little error: there are no angles in the limit curve. It is composed of self-similar arcs under some affine transformations (with a linear part with matrix entries 1/3, 1/3, 0, 1/3, say), which are not similarities, so no nontrivial angles can be present. http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an/30767#30767 Comment by Thorny Thorny 2010-08-02T07:33:19Z 2010-08-02T07:33:19Z @Casebash: the binary one. http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an/30767#30767 Comment by Thorny Thorny 2010-07-14T07:48:17Z 2010-07-14T07:48:17Z To answer &quot;is it always possible to construct a set of cycle bases with each and every edge shared by at most 2 bases?&quot; in the negative, I construct a graph for which no such cycle base exists. The example I give is the complete graph on 7 vertices. In it, the cycle space (see above) has dimension #edges-#vertices+1=21-7+1=15. No matter how you select 15 nonempty cycles or unions of cycles, those will have at least 45 edges counted with multiplicity. This is more than twice the number of edges in the graph, so by the pigeonhole principle at least one edge will be used 3 times or more. http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an/30767#30767 Comment by Thorny Thorny 2010-07-08T07:21:19Z 2010-07-08T07:21:19Z I answer the question &quot;In a graph, is it always possible to construct a set of cycle bases, with each and every edge Is shared by at most 2 cycle bases?&quot; in the negative, so one counterexample is all it takes. If you wanted to ask a more precise question, then BS's lead is what you should read. As for your other question, please consult <a href="http://en.wikipedia.org/wiki/Cycle_space" rel="nofollow">en.wikipedia.org/wiki/Cycle_space</a> . http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an Comment by Thorny Thorny 2010-07-07T09:46:16Z 2010-07-07T09:46:16Z <a href="http://en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> says: S. Mac Lane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32. http://mathoverflow.net/questions/30759/in-a-graph-is-it-always-possible-to-construct-a-set-of-cycle-bases-with-each-an/30767#30767 Comment by Thorny Thorny 2010-07-07T09:44:00Z 2010-07-07T09:44:00Z I implicitly use that all cycles contain at least 3 edges, and that the dimension of the cycle space is the number of edges exceeding that of a tree with the same vertices. Both facts are straightforward, could you please elaborate on where exactly you have problems? http://mathoverflow.net/questions/28907/covering-a-circle-with-red-and-blue-arcs/28924#28924 Comment by Thorny Thorny 2010-06-21T09:49:22Z 2010-06-21T09:49:22Z Red arcs: 0-0.3 and its shifts by 1/3 and 2/3. Blue arcs: 0.2-0.7 and its shifts by 1/3 and 2/3. Here k=3, but the blue arcs do not have a common point. http://mathoverflow.net/questions/28610/probability-of-a-point-on-a-unit-sphere-lying-within-a-cube Comment by Thorny Thorny 2010-06-18T11:10:39Z 2010-06-18T11:10:39Z What kind of accuracy are you aiming for? Approximating the surface measure of the sphere by a standard Gaussian would give results not worse than deviating ~1/n^{1/2} in d, and would probably be much better than that in most cases. http://mathoverflow.net/questions/22075/connectedness-of-random-distance-graph-on-integers/22117#22117 Comment by Thorny Thorny 2010-04-22T11:17:36Z 2010-04-22T11:17:36Z 1) You are solving the problem of whether there is a path between 1 and N that consists of two monotone subpaths; this is not exactly the same as whether there is a path between 1 and N. 2) If $\sum_{j&lt;n} p(j)$ grows slower than $log(n)$, the steps of $z$ are not integrable. http://mathoverflow.net/questions/21649/how-to-prove-that-w-1ew-1dete/21654#21654 Comment by Thorny Thorny 2010-04-17T10:50:27Z 2010-04-17T10:50:27Z The orientability of a manifold can be tested on loops, and on loops, there are only two kinds of bundles: oriented ones - those are trivial, and non-oriented ones - those are the sum of the $\gamma^1$ and a trivial (one can split trivial subbundles off as long as the rank of the bundle is more than the dimension of the base, which is 1). So the axioms tell us what the pullbacks of $w_1$ to the loops are - 0 if it is an orientation-preserving one, 1 if it is not. http://mathoverflow.net/questions/20848/fractional-fourier-transform Comment by Thorny Thorny 2010-04-09T16:22:25Z 2010-04-09T16:22:25Z <a href="http://en.wikipedia.org/wiki/Fractional_Fourier_transform" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> ? http://mathoverflow.net/questions/20730/about-dense-orbits-on-dynamical-systems/20736#20736 Comment by Thorny Thorny 2010-04-09T07:03:25Z 2010-04-09T07:03:25Z You mean $\alpha$, if I understand you correctly. I am giving you a construction of an $\alpha$ for which the dynamical system exhibits an infinite $A$, so there is no modification. I assume there could be an explicit $\alpha$ given, something along the lines of $\sum 10^{-10^{k^2}}$ - as long as it can be approximated superexponentially, the set $A$ will be infinite for all $\delta&gt;0$. http://mathoverflow.net/questions/20712/do-surjective-degree-zero-maps-exist/20734#20734 Comment by Thorny Thorny 2010-04-08T14:56:28Z 2010-04-08T14:56:28Z Think of $F$ as being embedded into $\mathbb{R}^3$ symmetrically, with a handle in the middle. Mirroring wrt the symmetry plane of this embedding perpendicular to the direction of the handle maps $F$ to a torus minus a disc. Is your map not homotopic to this factor map? http://mathoverflow.net/questions/19398/on-the-convolution-of-generalized-functions Comment by Thorny Thorny 2010-03-26T08:23:42Z 2010-03-26T08:23:42Z Which convergence(s) are you interested in?