Kevin P. Costello
|
Registered User
|
Currently an Assistant Professor at UC-Riverside. Interested in Combinatorics, Probability, and especially in their intersection.
|
|
May 9 |
accepted | Discrete disjoint covering of integer lattices |
|
May 8 |
answered | Discrete disjoint covering of integer lattices |
|
Apr 27 |
comment |
Expected edit distance The limit must exist because the expected edit distance is subadditive (we can always edit a string of length $m+n$ by editing each part separately). |
|
Apr 14 |
accepted | Average size of determinants of integer matrices? |
|
Apr 14 |
answered | Average size of determinants of integer matrices? |
|
Apr 12 |
answered | Bounding statistical distance by matching moments |
|
Mar 21 |
comment |
Joint (close to uniform) distribution in finite fields Do you have any examples in the way of lower bounds? |
|
Mar 21 |
comment |
Joint (close to uniform) distribution in finite fields Am I missing something at the end here? It seems like you have $||F||_2^2 \leq \frac{k \epsilon}{k-1}$, not $||F||_2$. |
|
Mar 15 |
comment |
Mean minimum distance for N random points on a unit square (plane) If all you care about is showing that the expected distance is less than $1$ for $N=2$, I believe you can dodge most of the computation using by using Jensen's inequality to bound $[E(d)]^2≤E(d^2)=2E((x_1−x_2)^2)=\frac{1}{3}$. |
|
Mar 9 |
awarded | ● Nice Answer |
|
Mar 7 |
revised |
Invertibility of a certain matrix indexed by the Hamming cube added 2 characters in body |
|
Mar 6 |
comment |
Invertibility of a certain matrix indexed by the Hamming cube In terms of the name, an "intersection graph" is a more general term for a graph formed on a collection of subsets by connecting two subsets if they have non-empty intersection. I'm not sure if there's a special name for the graph in the case where $S$ is all the non-empty subsets of $F$. |
|
Mar 6 |
answered | Invertibility of a certain matrix indexed by the Hamming cube |
|
Feb 27 |
comment |
The fraction of the sphere a fixed distance from a subspace Shiri Artstein's "Proportional Concentration Phenomena on the Sphere" (tau.ac.il/~shiri/israelj/ISRAJ.pdf ) might be relevant for the geometric interpretation. |
|
Feb 10 |
accepted | Concentration bounds for sums of random variables of permutations |
|
Jan 29 |
answered | Concentration bounds for sums of random variables of permutations |
|
Jan 27 |
accepted | Completion time of a process on a tree |
|
Jan 26 |
comment |
Need tight lower bound for independence number of order 10 graph It only works here if you happen to pick the right vertex of lowest degree to start with -- if you start by picking $5$, you'll only end up with a set of size $3$. |
|
Jan 25 |
comment |
How random are random spanning trees? The second half of my comment was only referring to the case $n=4$. In that case conditioned on the graph having $5$ (or $6$) edges, there's only one possible graph up to isomorphism. That graph either has exactly half the spanning trees of each type (for $5$ edges), or all of them (for $6$ edges), so the spanning trees appear in the right proportions (one way of thinking about this -- for any $k$ each tree appears in the same number of $k$ edge graphs. If each $k$ edge graph has the same number of spanning trees, that means each tree appears with the same probability given there's $k$ edges |
|
Jan 25 |
comment |
How random are random spanning trees? Then there's a $1/5$ chance that $G$ is a $4-$cycle (in which case all four spanning trees are paths), and a $4/5$ chance that $G$ is a triangle with one edge added (in which case there are only three spanning trees, one star and two paths). Combining, each of the $12$ paths has a $11/180$ chance of being chosen, while each of the $4$ stars has a $1/15=12/180$ chance. |
|
Jan 25 |
comment |
How random are random spanning trees? I don't see why each labelled tree is equally likely. Although each tree is a spanning tree for an equal number of graphs, trees which tend to be spanning trees for graphs with fewer spanning trees in total will be more likely to be chosen. Consider for example the case where $n=4$. If we condition on the graph having $3$ edges, all trees are equally likely. The same holds true if we condition on $G$ having $5$ or $6$ edges. But suppose we condition on $G$ having $4$ edges (continued in next comment). |
|
Jan 24 |
answered | Completion time of a process on a tree |
|
Jan 16 |
comment |
Permanent of a matrix of odd integers Perfect proved a similar result for $\pm 1$ matrices in his "Positive Diagonals of $\pm 1$ Matrices" (he mentions the connection to the permanent in the concluding remarks to his paper). I don't know if his proof carries over or not, but it may be worth looking at. |
|
Jan 10 |
comment |
The probability for a symmetric matrix to be positive definite One strange corollary of this: Imagine exposing your matrix minor by minor (so that after step $k$ the $k \times k$ upper left submatrix is exposed). By Sylvester's criterion, $M$ is positive definite iff the determinants of each exposed submatrix are positive. So what this is saying is that the probability the $n^{th}$ determinant is positive, conditioned on the previous determinants being positive, decays exponentially in $n$. I find this counterintuitive, especially given that individual entries have symmetric distribution. |
|
Jan 7 |
comment |
Minimal period of arithmetic progressions occurring in sets of positive density. A version of this question is also discussed at mathoverflow.net/questions/87923/… (the Thue-Morse sequence mentioned in the original question there corresponds to Stefan's answer). Raff and Zeilberger's "Finite Analogs of Szemeredi's Theorem" (math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/… ) might also be of interest. |
|
Dec 11 |
comment |
Apparently simple probability By "this inequality is independent of the other events $B_i$", do you mean that for any disjoint $S$ and $T$ and any $i \notin S \cup T$ that $$P(B_i \vert B_j \textrm { holds for all } j \in S \textrm{ but does not hold for any } j \in T) \leq x ?$$ |
|
Dec 6 |
answered | Existence of (Cut-Based) pseudorandom graphs beating the random graph |
|
Dec 4 |
accepted | The minimum size of Max-Cut for graphs of half density |
|
Dec 3 |
revised |
The minimum size of Max-Cut for graphs of half density Deleting a load of nonsense. |
|
Dec 3 |
answered | The minimum size of Max-Cut for graphs of half density |
|
Dec 3 |
awarded | ● Nice Answer |
|
Nov 30 |
comment |
Additive energy of random sets An alternative viewpoint as to why the bound here is essentially tight: A random set $A$ will have size at least $(\frac{1}{2}+t)N$ with probability at least $\exp(-c_0 t^2 N)$ for some $c_0$. Whenever this happens, the energy is likely to increase by a constant factor as well. |
|
Nov 28 |
comment |
Monic polynomial with integer coefficients with roots on unit circle, not roots root of unity? Just as a note: The result that if all roots are on the unit circle then they must be roots of unity goes back to Kronecker (for references and a couple of quick proofs, see mathoverflow.net/questions/10911/… ). |
