most recent 30 from http://mathoverflow.net 2013-05-24T12:40:25Z http://mathoverflow.net/feeds/user/8574 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube Lev Reyzin 2011-07-31T16:42:34Z 2011-08-12T20:30:12Z

<p>Is there a known formula for the number of closed walks of length (exactly) $r$ on the $n$-cube? If not, what are the best known upper and lower bounds?</p> <p>[Edit] Note: the walk can repeat vertices.</p>

http://mathoverflow.net/questions/42113/a-small-collection-of-large-subsets-covering-all-small-subsets Lev Reyzin 2010-10-14T05:09:48Z 2010-10-14T05:31:04Z

<p>Let $r,s,n$ be positive integers with $r &lt; s &lt; n$. Let $U = \{1,\ldots,n\}$.</p> <blockquote> <p>Let $S$ contain $s$-element subsets of $U$ (of our choosing). What is that smallest we can make $S$ such that every $r$-element subset of $U$ is a subset of some element in $S$?</p> </blockquote> <p>I'm curious what the best known upper and lower bounds are on the smallest we can make $S$, and I am especially interested in the case where $r &lt;&lt; s &lt;&lt; n$. I am more worried about asymptotic behavior than exact bounds.</p> <p>This can also be viewed as a special case of a set-cover problem that has a lot of symmetry. I'm afraid/hoping there's something simple from graph theory that solves my problem.</p> <p>EDIT: Thanks to @Gerhard, I see this is a well known problem called covering numbers / covering designs.</p>

http://mathoverflow.net/questions/80522/sub-linear-algorithm-for-minimum-spanning-tree-mst-for-a-tree-metric/80566#80566 Lev Reyzin 2012-01-10T14:14:45Z 2012-01-10T14:14:45Z

Sorry, I misread your answer -- I missed that the numbers are weights (I thought they were just labels). The two-level star is needed only in the unweighted case.

http://mathoverflow.net/questions/80522/sub-linear-algorithm-for-minimum-spanning-tree-mst-for-a-tree-metric/80566#80566 Lev Reyzin 2012-01-05T23:02:00Z 2012-01-05T23:02:00Z

@David, I think that's not quite right. If you find the center of the star, you can first make sure it is as star... etc. The easiest way I know of making the $O(n^2)$ lower bound work is using &quot;two-level&quot; stars. See Proposition 7 of this <a href="http://www.cc.gatech.edu/~lreyzin/papers/ReyzinSri07_alt.pdf" rel="nofollow">cc.gatech.edu/~lreyzin/papers/ReyzinSri07_alt.pdf</a>

http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71807#71807 Lev Reyzin 2011-08-02T23:08:45Z 2011-08-02T23:08:45Z

thanks - this is nice.

http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71739#71739 Lev Reyzin 2011-08-02T18:06:37Z 2011-08-02T18:06:37Z

In some sense, I'm more interested in fixed r as n gets large. The summation is certainly quite helpful, but of course if a closed form existed, it would even be nicer :)

http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71739#71739 Lev Reyzin 2011-08-02T17:12:39Z 2011-08-02T17:12:39Z

I'm guessing not, but is there any chance this expression has a closed form?

http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71739#71739 Lev Reyzin 2011-07-31T19:24:46Z 2011-07-31T19:24:46Z

Thanks! that's what I needed.

http://mathoverflow.net/questions/42113/a-small-collection-of-large-subsets-covering-all-small-subsets/42115#42115 Lev Reyzin 2010-10-14T05:40:56Z 2010-10-14T05:40:56Z

Thank you -- this is perfect. It seems Erdos and Spencer give an upper bound of (1+\ln(C(s,r)))C(n,r)/C(s,r), which is perfect for my purposes! If I had enough reputation, I would upvote your answer :