Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
In the circle-packed planar-doubling setting of Section 7, prove that the expected distance of simple random walk from its root at time t is at most t^α for some α<1/2. Is the optimal exponent α=d^-1 when volume grows like r^d?
Can we sample a uniformly random balanced graph partition into two pieces in polynomial time on well-behaved graphs? Specifically, can we do this on grid graphs? Wesley Pegden has an informal argument suggesting that simply running the…
Let g_±1,d(x)=x^d+a_d-1x^d-1+…+a_0 be a monic polynomial of positive degree d, where each a_i is independently +1 or -1 with probability 1/2. Rademacher irreducibility conjecture. The probability that g_±1,d(x) is reducible goes to 0 as d…
Let M_N and M_N' be independent complex Ginibre matrices and set M_N(\theta)=\cos\theta M_N+\sin\theta M_N'. How do the eigenvalues \lambda_i(\theta) vary with \theta?
Conjecture: the diagonal online random Ramsey number satisfies \widetilde r_{\rm rand}(n,n)=2^{(1+o(1))(2/3)n}, and for fixed m\ge3 as n\to\infty, \widetilde r_{\rm rand}(m,n)=n^{(1+o(1))(2/3)m}.
Is the upper bound of Theorem 17 on the concentration of the chro- matic number χpGn,p q of the random graph Gn,p close to best possible or not? Conjecture 16. For all k ě 6, k even, such that the dimension of the solution space of a1 x1 .…
Let R_n be the resistance in the critical resistance model, let p_c=frac12, and let c_eff be the constant in the critical scaling conjecture for log R_n. Derrida's conjecture. The preceding conjecture should hold with c_eff=9ζ(3),…
Suppose we run the up-down walk but restrict to trees that are k-splittable. Is this Markov chain ergodic, and if so, does it mix rapidly?
Is it the case that both properties can be realized simultaneously? Descriptive Combinatorics, LOCAL Algorithms and Random Processes 449
Does Kac's random walk on S^n exhibit cutoff? Does the analogously defined random walk on SO(n) exhibit cutoff?
In one-dimensional long-range percolation with edge probabilities proportional to β|i-j|^-2, study the distance exponent θ(β) defined by typical distances of order n^θ(β). Is θ continuous or monotone in β? Does the model have a nontrivial…
Let X,Y ∈ 0,1 have joint distribution p_X,Y(x,y) = 1/2(1- α) 1/2α 1/2α 1/2(1- α) , then I(X;Y) = 1 - h(α) for 0 ≤ α ≤ 1/2 where h(α) triangleq -α log_2 α - (1 - α) log_2 (1 - α). Note that I(X;Y) triangleq D(p_X,Y || p_X p_Y). The…
In a uniformly random spanning tree of a grid graph with N vertices, we know the probability of having an exactly balanced split edge is at least 1/N^2. Can we improve this to 1/N? Empirically, this seems like the right answer. It would…
This remains open although we suspect that the answer here is negative as well. and xi = 2 for all n < i \leq m. Then S is block-compatible for n. Therefore, the number of sequences that are block-compatible for n is at least n+q−2 1/2 =…
Given a multiplicative linear series V_n ⊂ H⁰(nL), metrics φ and ψ, and a φ_n-orthonormal, ψ_n-orthogonal basis with λ_i = ψ_n(e_i,e_i), let Z_n be uniformly distributed among log(λ_i)/n; does Z_n converge in probability?
Let ω_n be an n-element uniform sorting network. For t∈(0,1), define the scaled configuration by μ_t(ω_n):=frac 1n ∑_i=1^n δ(2i/n-1 , frac 2σ_⌊ tN⌋(i)n-1). For t∈(0,1), define the Archimedes measure by Arch_t(dx× dy):=1/2π√[sin^2(π t)…
Show, perhaps under regularity hypotheses on a SIRSN, that for 2<β<4 the paper's source-destination measure with displacement density |z|^-β induces a locally finite traffic-intensity measure on E(∞,1) and hence on bigcup_rE(∞,r).
(a) What is a good generative model? (b) Perturbed Delaunay triangulations of random point sets seem to work very well. You add edges with preferential attachment then delete edges randomly. Can we formally investigate how/why this works?…
Let X and Y be random variables with distributions P_X and P_Y, and let P_X^n and P_Y^n denote their n-fold product distributions. Let H(X) and H(Y) be their entropies, and let G(P_X,P_Y) denote the maximal guessing coupling value.…
Let M_n^sym be a random symmetric matrix with Bernoulli pm 1 entries. Vu's distinct singular values conjecture. With probability 1-o(1), all the singular values of M_n^sym are distinct. This conjecture is motivated by the study of repeated…