most recent 30 from http://mathoverflow.net 2013-05-26T01:47:18Z http://mathoverflow.net/feeds/user/22236 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104704/azumas-inequality-when-the-conditions-hold-with-high-probability Patt Geffrey 2012-08-14T16:18:39Z 2012-08-14T23:02:51Z

<p>In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| &lt; c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the above inequality (for each $k$) holds with high probability?</p>

http://mathoverflow.net/questions/102920/number-of-trees-with-the-same-matching-number Patt Geffrey 2012-07-23T12:08:52Z 2012-07-23T14:34:49Z

<p>Let $\sigma(n,m)$ be the number of trees with $n$ vertices ${ v_1, \dots, v_n }$ such that the matching number (the size of a maximum matching) is $m$.</p> <p>I have been trying to compute the value of $\sigma(n,m)$ but I have been unsuccessful. It looks hard. Is it known? Any idea or suggestion about how can $\sigma$ be computed? Or any good bounds? </p>

http://mathoverflow.net/questions/102479/matchings-in-hypergraphs Patt Geffrey 2012-07-17T19:36:23Z 2012-07-18T06:09:34Z

<p>I have been reading Pippenger and Spencer's paper "Asymptotic behavior of the chromatic index for hypergraphs" and they comment that their result is applicable to the family of random k-uniform hypergraphs $G_k(n,p)$ whenever $p(n) = o(1)$ and $\frac{\log n}{n^{k-1}} = o(p(n))$.</p> <p>I'm looking for a proof of this. </p> <p>Let $d(G)$ and $D(G)$ denote the minimum and maximum degree of $G$ respectively. Let $C(G)$ denote the maximum co-degree in $G$: given $x,y \in V$, then $cod(x,y) = | { e \in E : x,y \in e } |$. Basically, their theorem says that if</p> <p>$d(G) \sim D(G)$ and $C(G) = o(D(G))$</p> <p>then $\chi^{\prime}(G) \sim D(G)$ and $\phi(G) \sim D(G)$, where $\chi^{\prime}$ stands for the chromatic index and $\phi$ denote the largest number of coverings into which the edges of $G$ can be partitioned. In particular, this implies that asymptotically a.s. there is a perfect matching. Note that taking $k=2$ we get that we need $p(n) \gg \log n/n$, which is a well-known result by Erdos and Renyi. </p> <p>Let $H = G_k(n,p)$ and let $p = p(n)$ be such that $p(n) = o(1)$ and $\frac{\log n}{n^{k-1}} = o(p(n))$. I would appreciate if someone could tell me where can I find a proof of $D(H) \sim d(H)$ and $C(H) = o(D(H))$ or give me some explanations. How do we study the behavior of the co-degree?</p> <p>Thanks a lot</p>

http://mathoverflow.net/questions/99465/counting-trees-with-two-kind-of-vertices-and-fixed-number-of-edges-beetween-one-k Patt Geffrey 2012-06-13T15:50:15Z 2012-06-14T05:53:55Z

<p>I'm interested in the following problem: given vertices $v_1, \dots, v_j$ and $w_{j+1}, \dots, w_n$ I want to count the number of trees with these $n$ vertices such that the number of edges between the $v_i$ vertices is exactly $t$, for fixed $t$. Clearly, we should only consider $t \in {0, 1, \dots, n-j-1}$.</p> <p>The way in which I tried to solve it seems to be unsuccessful and probably not the best approach. The $t$ edges between the $j$ vertices $v_i$ will form a forest with $j-t$ components. We can do this in $\binom{j-1}{j-t-1} j^t$ ways, I think. If we consider any such tree $T$ and if we remove the vertices $v_i$, then we get a forest with the $w_i$ vertices. The number of components in this forest could go from 1 to $n-j$. Hence, we can compute the sum over all the possible number of components $c$ and repeat the above computation for the number of forest with $n-j$ vertices and $c$ components. Finally, fixed a forest with the $v_i$ vertices ($j-t$ components) and one with the $w_k$ vertices ($c$ components), we need to count the number of spanning trees in $K_{j-t, c}$. A complete bipartite graph $K_{m,n}$ has $m^{n−1} n^{m−1}$ spanning trees. However, each edge - say, from component $A$ to component $B$ - corresponds to $|A| |B|$ possible edges, as each component can have several vertices: but we don't have that information! If we fix an spanning tree $T$, then the number of corresponding trees for answering the original question associated to $T$ is equal to the product of the size of each component $C_i$ to the power of $deg_T(C_i)$. Is there any "expectation" approach that could work?</p> <p>I would appreciate any idea, suggestion or help! Thanks.</p>

http://mathoverflow.net/questions/91577/rank-of-isogenous-elliptic-curves Patt Geffrey 2012-03-18T23:31:49Z 2012-03-19T05:11:28Z

<p>I think that k-isogenous elliptic curves have the same rank as I think rank is an isogeny invariant. However, I am not sure. Does anyone know where could I find a proof? Thanks!</p>

http://mathoverflow.net/questions/104704/azumas-inequality-when-the-conditions-hold-with-high-probability Patt Geffrey 2012-08-14T17:41:38Z 2012-08-14T17:41:38Z

The sequence is not necessarily non-increasing as for two distinct values of $N$ and fixed $k$, $P(|X_k - X_{k-1}|)$ is not necessarily equal.

http://mathoverflow.net/questions/104704/azumas-inequality-when-the-conditions-hold-with-high-probability Patt Geffrey 2012-08-14T16:54:12Z 2012-08-14T16:54:12Z

If the martingales considered is $(X_k)_{k=1}^{N}$, what I mean is that $\mathbb{P}(\forall k, |X_k - X_{k-1}| &lt; c_k) \to 1$ as $N$ goes to $\infty$.

http://mathoverflow.net/questions/104704/azumas-inequality-when-the-conditions-hold-with-high-probability Patt Geffrey 2012-08-14T16:31:32Z 2012-08-14T16:31:32Z

Yes, I mean almost surely instead of surely.

http://mathoverflow.net/questions/102920/number-of-trees-with-the-same-matching-number/102929#102929 Patt Geffrey 2012-07-23T18:35:34Z 2012-07-23T18:35:34Z

Thanks David, consider the probability space where all the labelled trees with n vertices are equally likely. Would it be a harder question: what's the expected matching number of a random tree? Is there any paper solving that?

http://mathoverflow.net/questions/102479/matchings-in-hypergraphs/102513#102513 Patt Geffrey 2012-07-18T10:50:27Z 2012-07-18T10:50:27Z

Thanks Brendan!

http://mathoverflow.net/questions/91577/rank-of-isogenous-elliptic-curves/91579#91579 Patt Geffrey 2012-03-18T23:48:21Z 2012-03-18T23:48:21Z

Thank you Will!