Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is complete integer factorization randomized polynomial-time reducible to computation of the squarefree part?
Let underlineθ=(θ_1,…,θ_m) be a m-tuple of complex numbers. Define t=trdeg Q(underlineθ) and assume t≥ 1. There exist positive constants c_1 and c_2 with the following property. Let (D_ν)_ν≥ 0 and (μ_ν)_ν≥ 0 be sequences of real numbers…
What is the maximum pathwidth of an n-vertex cubic graph?
Every finite simple connected graph G with |V(G)|=2d+1, diam(G)=d≥ 3 satisfies W(G)≤ W(C_2d+1) =frac(2d+1)d(d+1)2. The claimed equality cases are exactly C_2d+1 for every d≥3, the double star D_2,3 when d=3, and the nine-vertex tree…
Can constant-degree sum-of-squares refute k-colorability for random graphs of average degree less than k^2 (i.e.\ below the Kesten-Stigum bound)?
Griggs, Lu: ("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_(2) as a subposet? (What is the maximum number of subsets of [n] so that there are no A, B, C, D with A <…
Problem Which Steiner triple systems are universal?
An upho poset is a poset whose every principal filter is order-isomorphic to the whole poset; it is finitary when its intervals are finite. A coloring assigns labels to the covering edges of an upho poset in a way compatible with the…
Assume that K=Q and that V(Q) is Zariski dense; is Z a union of connected components of V(R)?
A finite set A⊆1,…,N is sum-distinct if all subset sums ∑_a∈ S a, S⊆ A, are distinct. Erdős asked whether there is an absolute constant C>0 such that every sum-distinct set A⊆1,…,N satisfies N>C 2^|A|. The conjecture is false: for every…
Let x be an irrational number and let G_x be its associated Haros graph with degree distribution P(k,x). Call the properties in the preceding conjecture the combination of a periodic pattern of zeros in P(k,x) and an exponential tail.…
Consider higher Pascal's triangles and the Catalan-number construction by algebraic complexes. Categorification conjecture for higher Pascal triangles. There exist constructions of algebraic complexes whose dimensions match the entries in…
overlineG is a universal odd distribution with values in groups where multiplication by 2 is invertible.
Conjecture 6.4. Any simple digraph with no loops or digons has a vertex v such that |N +2 (v)| + |N+(v)| ≥ 2|N −(v)|.Notes: Recall, for comparison, SSN can be written as |N +2 (v)| + |N +(v)| ≥ 2|N +(v)|. To see how
Make the proposed realization of existing finite-field discrete-logarithm systems inside class groups explicit for practical systems.
Let G be a graph on at most ℵ_1 vertices which contains no K_4 and no K_ℵ_0,ℵ_0 (the complete bipartite graph with ℵ_0 vertices in each class). Is it true that ω_1^2 → (ω_1ω, G)^2? What about finite G?
Let u_r(n) be the sequence associated with A_r, and let mo(r) denote the minimum order of a linear recurrence with constant coefficients satisfied by u_r(n) for all sufficiently large n. Exact recurrence-order conjecture. The values are…
Let n be the order of a minimal-ABC tree, and let big vertices denote the vertices distinguished as big in the paper's branch decomposition. The branches other than those incident with the big vertices are classified as B_i-branches.…
Let G be a group that acts transitively on a set X. A subset T⊂ G is X-uniform if, for every x,y∈ X, 1/|T||g∈ T:g(x)=y|=1/|X|. Polynomial-size uniform subset conjecture. There exists an X-uniform subset T⊂ G such that |T|≤ |X|^c for some…
Every bridgeless graph has a cycle double cover: a collection of cycles that covers each edge exactly twice.