Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For nearby moduli n_i=n_1+d_i and maps f_i(r)=r^e_ibmod n_i, prove the conjecture that with sufficiently many components at least one f_i is not polynomial-time invertible, thereby validating the proposed trapdoor-free RSA-like…
Construct efficient pseudorandom generators from ideal-lattice problems.
Does every non-totally-ordered finite poset have two elements with probability between 1/3 and 2/3 in random linear extensions?
For a graph G, let X_G,k be the number of edges induced by a uniformly random k-vertex subset, and define I(n,k,ℓ):=maxP[X_G,k=ℓ]:v(G)=n, with ind(k,ℓ):=lim_n→∞I(n,k,ℓ). Quadratic-range edge-statistics conjecture. For all k,ℓ∈N with…
Let μ denote the minimum overlap constant in the Erdős minimum overlap problem. Conjectured interval for μ. The constant μ lies in the interval [0.3803,0.3809]. This numerical conjecture is motivated by the output of a modified convex…
Is it true that there are only finitely many pairs of intervals I_1,I_2 such that ∑_n_1∈ I_11/n_1+∑_n_2∈ I_21/n_2∈ N?
Does SVP reduce to CVP while remaining inside the class of cyclic or ideal lattices?
Consider a generalized spoke and star graph with ℓ levels. Level one consists of one node, the hub; level two consists of n_1 spokes connected to the hub; and each node at level k has n_k nodes connected to it at level k+1.…
Consider the family of finite configurations whose current binary word is 1(01)^k, with period function P(k) assigning to the configuration indexed by k its period. Even-index period formula conjecture. The period function satisfies…
Let p(k) be the limit as n → ∞ of the probability that a random permutation on [n] preserves some set of size k. Is p(k) a decreasing function of k? Is p(k) = (C + o(1))k^-α(log k)^-3/2 for some absolute constant C?
Let r obreak∈Z, and let hat S_n,k(-1,2;r)=2^k k! S_n,k(-1,2;r) denote the rescaled generalized Stirling number. Heuristic formula. The identity hat S_n,k(-1,2;r)=∑_j=⌊(2-r)/2⌋^⌊(n+2-r)/2⌋binomn-jn-k n!binomn+12j+r-1 should hold for all…
Let K ⊂ S^3 be an alternating knot. Its Alexander polynomial is Δ_K(t)=∑ a_i t^i. Here a polynomial is log-concave when its coefficient sequence satisfies a_i-1a_i+1≤ a_i^2 for every relevant index. Strong Fox conjecture. The Alexander…
For t≥3, let f(t) be the least integer such that every red-blue colouring of the edges of every sufficiently large K_n contains at least ⌊n/t⌋-f(t) vertex-disjoint monochromatic copies of K_t, not necessarily all of the same colour.…
Does there exist ε>0 and d₀ such that every graph G with minimum degree δ(G)≥d₀ satisfies χ′_g(G)≥(1+ε)δ(G), where χ′_g(G) is the game chromatic index?
Let G be a graph on n vertices, and let reg_even(G) denote the largest degree of an even-regular spanning subgraph of G. The regular-subgraph conjecture. If δ(G)≥ n/2, then G contains at least fracreg_even(G)2 edge-disjoint Hamilton…
If a and b are two positive integers with a<b and R(a)=R(b) then there is a prime p with a< p< b.
For all finite graphs G and H, the quantum chromatic number of their categorical product satisfies χ_q(G× H)=minχ_q(G),χ_q(H), where G× H has vertex set V(G)× V(H) and (g,h) is adjacent to (g',h') exactly when g is adjacent to g' in G and…
Let GP(n,k) be the generalized Petersen graph, let d denote graph distance, and let D be its diameter. For an integer k≥ 2, define n_k= 11, k=2, (k+1)^2, k odd, k(k+2), k≥4 even. The eventual non-ℓ-distance-balance conjecture. For any…
Let P_m and P_n be paths on m and n vertices, respectively, and let pr(G) denote the minimum coprime number of a graph G. Asplund–Fox's path-join conjecture. For any positive integer N, there exists a positive integer M such that for all…
4-color Ramsey number of triangles Fan Chung Problem: Find r(3,3,3,3). Is it 51? Known: 51 ≤ r(3,3,3,3) ≤ 62. Lower bound due to (Chung 1973), and upper bound due to (Fettes--Kramer--Radziszowski 2004).