# Kevin P. Costello

 2,862 Reputation 2420 views

## Registered User

 Name Kevin P. Costello Member for 3 years Seen 12 hours ago Website Location Riverside, CA Age 31
Currently an Assistant Professor at UC-Riverside. Interested in Combinatorics, Probability, and especially in their intersection.
 May9 accepted Discrete disjoint covering of integer lattices May8 answered Discrete disjoint covering of integer lattices Apr27 comment Expected edit distanceThe 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). Apr14 accepted Average size of determinants of integer matrices? Apr14 answered Average size of determinants of integer matrices? Apr12 answered Bounding statistical distance by matching moments Mar21 comment Joint (close to uniform) distribution in finite fieldsDo you have any examples in the way of lower bounds? Mar21 comment Joint (close to uniform) distribution in finite fieldsAm I missing something at the end here? It seems like you have $||F||_2^2 \leq \frac{k \epsilon}{k-1}$, not $||F||_2$. Mar15 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}$. Mar9 awarded ● Nice Answer Mar7 revised Invertibility of a certain matrix indexed by the Hamming cubeadded 2 characters in body Mar6 comment Invertibility of a certain matrix indexed by the Hamming cubeIn 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$. Mar6 answered Invertibility of a certain matrix indexed by the Hamming cube Feb27 comment The fraction of the sphere a fixed distance from a subspaceShiri Artstein's "Proportional Concentration Phenomena on the Sphere" (tau.ac.il/~shiri/israelj/ISRAJ.pdf ) might be relevant for the geometric interpretation. Feb10 accepted Concentration bounds for sums of random variables of permutations Jan29 answered Concentration bounds for sums of random variables of permutations Jan27 accepted Completion time of a process on a tree Jan26 comment Need tight lower bound for independence number of order 10 graphIt 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$. Jan25 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 Jan25 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. Jan25 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). Jan24 answered Completion time of a process on a tree Jan16 comment Permanent of a matrix of odd integersPerfect 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. Jan10 comment The probability for a symmetric matrix to be positive definiteOne 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. Jan7 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. Dec11 comment Apparently simple probabilityBy "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 ?$$ Dec6 answered Existence of (Cut-Based) pseudorandom graphs beating the random graph Dec4 accepted The minimum size of Max-Cut for graphs of half density Dec3 revised The minimum size of Max-Cut for graphs of half densityDeleting a load of nonsense. Dec3 answered The minimum size of Max-Cut for graphs of half density Dec3 awarded ● Nice Answer Nov30 comment Additive energy of random setsAn 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. Nov28 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/… ).