Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
- What is the probability that a random nXn matrix over Z_(p) has zero permanent as n goes to infinity
Tao: What is the probability that a random nXn matrix over Z_(p) has zero permanent as n goes to infinity? (Surely 1/p... as long as p is not 2.)
For m,n∈N, define the q-Fibonomial coefficient by [ ! m+n n !]_F:=frac[F_m+n]^!_q[F_m]^!_q ,[F_n]^!_q, where [F_n]^!_q:=∏_k=1^n[F_k]_q and [n]_q:=1+q+…+q^n-1. Bergeron–Ceballos–Küstner's conjecture. The polynomials [ ! m+n !]_F are…
For every matroid M, its g-polynomial has nonnegative integer coefficients; equivalently, g_M(t)∈Z_≥ 0[t].
Let G=(V,E) and G'=(V,E') be connected graphs with the same vertex set V, where E'=E∪x,y for some x,y∈ V. Write λ_c(G) for the critical infection rate of the contact process on G. Pemantle–Stacey conjecture. The critical rates are equal:…
Let L be a Latin square. A quasi-transversal is a set of entries containing exactly one entry from each row and each column, with exactly one symbol repeated twice and every other symbol occurring once. Quasi-transversal conjecture. Every…
Find orders O whose Picard groups contain Z/ℓ, admit compact element representations, and allow group composition in O(logℓ) operations.
Let G be a cyclically 4-edge-connected graph, meaning that deleting fewer than 4 edges cannot separate G into two components both containing a cycle. Let fn(G) denote its Frank number. Frank number conjecture for cyclically…
Is it true that, for all k eq 1, there are infinitely many n such that 2^n≡ kpmodn?
Let A⊆R be an infinite set. Must there be a set E⊂ R of positive measure which does not contain any set of the shape aA+b for some a,b∈R and a≠ 0?
Determine if the power domination result for 3-regular random graphs can be generalized to d-regular random graphs.
Let S_10 be the number of odd descent-tops, S_12 the number of (odd,odd) pairs, and S_17 the maximal subsequence of the form 1 2… i in a permutation. Let T_1 count occurrences of S_10 but not S_12, let T_2 count occurrences of S_12 but not…
Let G be a graph. A graph is prime if it admits a prime labeling, and odd prime if its vertices can be injectively labeled by 1,3,…,2|V(G)|-1 so that adjacent vertices receive relatively prime labels. Prime graph odd-prime conjecture.…
A finite family H of graphs is heroic if there exists a constant d(H)>0 such that every H-free graph has cochromatic number less than d(H). A family is celebrated if some constant 0<c(H)≤ 1 guarantees that every H-free graph has a clique…
Run BP with a `good' initialization (e.g.\ using a spectral method based on the non-backtracking walk matrix). Show that it achieves the optimal overlap with the truth.
Let G be a connected graph with maximum degree Δ≥ 3. Let C_5^2 be the graph obtained from a 5-cycle by replacing its vertices with independent sets of order 2, and let K_3,3^+ be the graph obtained from K_3,3 by subdividing exactly one…
For a graph G, let D(G) be the multiset of all vertex-deleted induced subgraphs of G. Average-case deck conjecture. There exists an absolute constant c>0 such that, for every graph G, at least frac12|D(G)| members H∈ D(G) satisfy r(H)≥ c·…
Let overrightarrowG be a proper circular arc digraph, meaning a digraph with no induced subdigraph isomorphic to either overrightarrowK_12 or overrightarrowK_21. Let X_overrightarrowG(bf x,t)=∑_j=0^ma_j(bf x)t^j be its chromatic…
Fix an integer d. What is the largest sum-free subset of [N]^d?
A graph is a finite undirected graph, and a minimal separator is a vertex set that minimally separates some pair of vertices. Theta-pyramid-prism-turtle conjecture. There is a polynomial P such that every graph G that contains no theta,…
Let Γ be an n-vertex graph, and let mis(Γ) denote its number of maximal independent sets. Hassler–Treglown conjecture. If Γ contains a perfect matching, then mis(Γ)≤ 2^n/2. The abstract states that this conjecture is resolved by the…