most recent 30 from http://mathoverflow.net 2013-05-21T20:12:58Z http://mathoverflow.net/feeds/user/24494 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/124194/partitioning-the-vertex-set-of-a-graph-with-a-large-independent-set TOM 2013-03-11T02:27:49Z 2013-03-13T07:29:33Z

<p>Let $G$ be a graph on an even number of vertices, say $2M$. Assume that the largest independent set in $G$ has at most $M$ elements. Is it true that there exists a set of $2m$ vertices (for some $m\leq M$), say $v_1,v_2,\ldots, v_{2m}$, with the following three properties:</p> <p>1) The induced subgraph on $v_1,\ldots,v_{m-1}$ is an independent set;</p> <p>2) The induced subgraph on $v_m,\ldots,v_{2m}$ is a clique;</p> <p>3) Removing these $2m$ vertices from $G$ leaves a graph with no independent set larger than M-m.</p> <p><strong>It turned out that the claim is not true and Colin provided a counterexample - a cycle on five vertices and an isolated vertex.</strong></p> <p><strong>A less precise question</strong>. Under the same condition - a graph $G$ on $2M$ vertices with no independent set larger than $M$ - could we say something about the structure of $G$ like:</p> <p>a) $G$ is has a very particular form (say an independent set on $M-1$ vertices and a clique on $M+1$ vertices);</p> <p>b) Otherwise we can partition the vertex set of into part with even number of vertices (say $2m_i$) so that the induced subgraphs on these sets of vertices have each no independent set larger than $m_i$?</p> <p>Comment: If we could have such a statement, maybe we could say something more about these small graphs? That is, maybe they could have a very simple structure like a cycle on an odd number of vertices and an isolated edge?</p>

http://mathoverflow.net/questions/122868/what-is-the-order-of-the-lower-tail-of-a-chi-squared-distribution TOM 2013-02-25T09:50:47Z 2013-02-25T13:22:46Z

<p>Let X be a random variable with having a chi-squared distribution with n degrees of freedom and let y be some real number at most n. Is it known how P (X &lt; y) behaves at least in some reasonable range of y? For instance, could one determine exactly the order of the latter probability when y=cn (for some $0\lt c \lt 1$) when n becomes large?</p> <p>In the end, I am interested in the upper bound for the latter probability, but I am not sure if the usual Chernoff bound gives the correct magnitude.</p>

http://mathoverflow.net/questions/122056/on-average-length-of-sums-of-unit-vectors-in-rn TOM 2013-02-17T12:29:27Z 2013-02-19T02:04:46Z

<p>Fix a number m and let us take a set, say A, of unit vectors {v_1,...,v_k} in R^n. Assume that k is large, say exponentially large in n (k=e^{cn}). Let X be the euclidean length of a random sum of m vectors in A (all sums are equally likely). </p> <p>It is quite intuitive that the typical length of such sum should be sqrt(m) and it is not that hard to verify it. </p> <p>Question: How does the variance of X behave? More precisely, is it true that VarX=o(sqrt(m)). If so, could one get a better rate? Maybe it is m^1/4?</p> <p>I would be very grateful for any information or link.</p>

http://mathoverflow.net/questions/114886/sufficient-condition-for-exponential-decay-in-chernoff-bound-large-deviations/122140#122140 TOM 2013-02-18T04:59:52Z 2013-02-18T06:01:03Z

<p>Theorem 1.1. in the paper is clearly false - for something like that to be true (two sided bound), usually one requires the variables to be bounded from both sides with probability 1 and then information about the variance gives you more information. Also, it would be enough that the generating function of each X_i is bounded by a generating function of some normal random variable (i.e. all X_i's are sub-Gaussian).</p> <p>Counterexample for Theorem 1.1: Assume n=1 and EX=0 we, by Chebyshev's inequality P(|X|>x) &lt; VarX/x^2 and it is optimal since the symmetric random variable that takes the values {-x,0,x} with P(X=x)=VarX/(2x^2) provides the equality. Theorem 1.1. would imply that VarX/x^2 is bounded above by an exponential function in x for all x, which is not the case. </p> <p>In general it is known that if X_i have only second moments then you will not get a bound of better order than Var(X_1+...+X_n)/x^2 for large x for the probability in question. Please let me know if you want me to expand on this. </p>

http://mathoverflow.net/questions/115477/on-well-separated-point-sets-in-the-plane TOM 2012-12-05T07:44:03Z 2012-12-07T16:39:44Z

<p>Let us say that a finite set $A$ in the plane is $1$-separated if:</p> <p><strong>1)</strong> it has an even number of points;</p> <p><strong>2)</strong> no open ball of diameter $1$ contains more than $|A|/2$ points.</p> <p>For a $1$-separated set $A$ define $G(A)$ to be a graph where two points $x,y$ in $A$ are joined by an edge iff the distance between them is at least $1$.</p> <blockquote> <p><em>Question</em>: can one find a finite set of graphs $G _ 1,\dots,G _ n$ such that any $1$-separated set $A $ can be partitioned into non-empty $1$-separated sets $A _ 1,\dots,A _ k$ such that $G(A _ i)$ is isomorphic to one of the $G _ j$'s?</p> </blockquote> <p><em>Comment</em>: The definition makes sense on the real line (the ball of diameter $1$ is replaced by an interval of length $1$). In that case we can take $n=1$ and $G_1$ to be a graph on two vertices joined by an edge (that is, $G(A)$ contains a matching). </p>

http://mathoverflow.net/questions/115479/linear-independence-of-finite-binary-sequences TOM 2012-12-05T08:14:17Z 2012-12-05T13:44:36Z

<p>Let V_n={-1,1}^n be the hypercube and let $C_n$ be a collection {x_1,...,x_n} of n distinct elements of V_n. </p> <p>Question: what is the smallest number N(n) of non-zero vectors with integer coefficients are needed to check that C_n is linearly independent over the integers? That is, what is the smallest set of such vectors <code>$\{v_1,...v_{N(n)}\}$</code> that if $C_n$ is linearly dependent over the integers then there exists some element v_{i} with coordinates $(k_1,...,k_n)$ such that $k_1x_1+...+k_nx_n$ is non-zero.</p>

http://mathoverflow.net/questions/99767/on-distances-between-points-on-the-plane TOM 2012-06-16T02:19:09Z 2012-06-16T04:30:24Z

<p>Take a set of 2n points on the plane and assume that no open set of diameter 1 contains more than n of these points. Question: con we pair up the points so that the distance between the points in a pair is at least 1? </p>

http://mathoverflow.net/questions/124194/partitioning-the-vertex-set-of-a-graph-with-a-large-independent-set TOM 2013-03-13T07:16:34Z 2013-03-13T07:16:34Z

Dear all, Colin's counterexample indeed works! I will try to formulate the &quot;right&quot; question. Thank you all for the help!

http://mathoverflow.net/questions/124194/partitioning-the-vertex-set-of-a-graph-with-a-large-independent-set TOM 2013-03-13T04:50:44Z 2013-03-13T04:50:44Z

Dear Tony, I have found I counterexample for that formulation and changed the formulation into a weaker statement.

http://mathoverflow.net/questions/124194/partitioning-the-vertex-set-of-a-graph-with-a-large-independent-set TOM 2013-03-13T00:25:08Z 2013-03-13T00:25:08Z

No, I meant exactly what I said - m-1 vertices forming an independent set, and m+1 vertices forming a clique. I just wanted to add one more assumption - assume that the initial graph immediately has an independent set of size exactly M. Otherwise the 3-partite Turan graph gives a counterexample for the claim I want.

http://mathoverflow.net/questions/122868/what-is-the-order-of-the-lower-tail-of-a-chi-squared-distribution/122880#122880 TOM 2013-02-25T18:34:30Z 2013-02-25T18:34:30Z

Thank you! This was most helpful!

http://mathoverflow.net/questions/122056/on-average-length-of-sums-of-unit-vectors-in-rn/122251#122251 TOM 2013-02-19T05:24:13Z 2013-02-19T05:24:13Z

Thank you, that is most useful and interesting! But still, the initial set is arbitrary - not random - I want to have a given large set of unit vectors (much larger than all other parameters) and then I want to take a random m-tuple of vectors from that set. Let us for simplicity agree that the sum of all vectors in A is 0, so that the mean of the random sample is 0. Then second moment of the length of a random m-tuple is at most m (straightforward calculation) and so the mean is at most sqrt(m) (by Cauchy-Schwarz). Thus we know that most of the sums lie within a ball of radius const*sqrt(m).

http://mathoverflow.net/questions/114886/sufficient-condition-for-exponential-decay-in-chernoff-bound-large-deviations/122140#122140 TOM 2013-02-19T03:40:04Z 2013-02-19T03:40:04Z

I did - the correction is already made: <a href="http://www.cs.utah.edu/~jeffp/teaching/cs5955/L3-Chern-Hoeff.pdf" rel="nofollow">cs.utah.edu/~jeffp/teaching/cs5955/&hellip;</a>

http://mathoverflow.net/questions/122056/on-average-length-of-sums-of-unit-vectors-in-rn TOM 2013-02-18T03:06:17Z 2013-02-18T03:06:17Z

Per Alexandersson: there are n vectors with 1 as a coordinate and we have exponentially many, so I clearly mean any vector of legth 1. Joseph O'Rourke: it is - it is the about the average length of a random sum x_1+...+x_m, that is, it's euclidean length. Douglas Zare: I think I have really meant what I have written. Anyhow, how should I use the CLT in this case? I really need just a bound on the variance of the length of such a sum, nothing more.

http://mathoverflow.net/questions/115479/linear-independence-of-finite-binary-sequences TOM 2013-02-17T12:43:23Z 2013-02-17T12:43:23Z

Yes, I did mean &quot;zero&quot; at the end.

http://mathoverflow.net/questions/99767/on-distances-between-points-on-the-plane/99771#99771 TOM 2012-06-16T10:35:36Z 2012-06-16T10:35:36Z

Thank you very much, it was most helpful!