Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For the class of countable vertex-finite graphs, we conjecture that (0) 000 = h(O), (I-), (R+), (S), (C+), (P+), (K+)i (1) 001 = h(O), (I-), (R+), (S)i (2) 010 = h(O), (I-), (K+)i (3) 011 = h(O), (I-)i (4) 100 = h(O), (I+), (R+), (C+),…
Conjecture Every planar graph on n verices has an induced forest with at least n/2 vertices.
: What is the list-chromatic number of Sudoku? That is, suppose one places k symbols (aka colors) in each cell of a Sudoku board -- not necessarily all the same lists of symbols. What is the least k so that it is always possible to choose…
Let G be an N-regular graph on n vertices. A Hamiltonian cycle is a cycle that meets every vertex, and a perfect matching is a matching covering every vertex. The Hamiltonian decomposition conjecture. If N≥ lfloorn/2⌋, then G has a…
Let G be a graph. The broadcast domination number γ_b(G) is the minimum cost of a dominating broadcast on G, and mp(G) is the maximum size of a multipacking in G. A multipacking is a subset of vertices such that every ball of radius r…
Let E_n be defined by ∑_n≥ 0E_nz^n/n!=sec z+tan z. For q≥ 1, define the minimal eventual period and preperiod by d(q)=mind≥ 1:∃ s≥ 0 ∀ n≥ s, E_n+d≡ E_npmod q and s(q)=mins≥ 0:∃ d≥ 1 ∀ n≥ s, E_n+d≡ E_npmod q. Ramassamy's conjecture asserts…
Let σ be a weakly consecutive sequence, and let m<k/2. Boundary-location conjecture. Each m appears among either the first m or the last m terms of the sequence; equivalently, its position satisfies σ^-1(m)∈[1,m]∪[k-m+1,k]. The paper…
For a compact convex domain Ω, the values of F_Ω at the vertices of its corner locus C_Ω give complete coordinates. How are these coordinates for Ω related to those for the dual domain Ω^*?
Several open problems that I am intrigued by are summarized below: • An ambitious open problem is showing the implication of training losses for shallow neural networks. The report passage is retained verbatim as the relevant context for…
Let K[a_i,b_i] denote the complete b_i-partite graph with a_i vertices in each part, and let G be its direct product G= ∏_i=1^t K[a_i,b_i]. Assume 2≤ b_1≤ b_2≤…≤ b_t. The upper domination conjecture. Γ(G)=1/b_1∏_i=1^t a_i b_i. Here Γ(G) is…
Let k≥ 2 be an integer and α_1,…,α_n be non-zero elements in a field K of zero characteristic, such that no quotient α_i/α_j with jnot=i is a root of unity. Consider the function F(X_1,…,X_k)= detpmatrix α_1^X_1 … α_k^X_1cr ⋮ ddots ⋮cr…
Straus: Is every polygonal room in the plane illuminable from some point? See this.
For a graph G on n vertices, let f_k(G) be the minimum number of vertices whose deletion leaves an induced subgraph in which the maximum degree is attained by at least k vertices, and let f_k(n)=max_|V(G)|=n f_k(G). Caro–Yuster conjecture.…
For any r≥ 3 and s≥ 4 we have f^r(n,s(r-2)+3,s)=o(n^2).
Let D=(V,A) be a digraph whose underlying graph is k-partition-connected, and let r_0 ∈ V be a node of in-degree 0. Suppose that the in-degree of every other node is at least k. Is it true that D can be decomposed into k weakly connected…
For d-polytopes with n facets, is the maximum graph diameter bounded by a polynomial in n (equivalently, for polytopes with 2d facets); can a family have diameter growing superlinearly in its number of facets; and does every d-polytope…
Every 4-connected planar locally finite graph has a Hamilton circle, i.e. a circle in its topological compactification containing every vertex.
Easier arithmetic Kakeya Let S⊂Z^n be such that for all (d_1,…,d_r)∈ ([N]^n)^r, S contains the GAP (for some translate a_0) a_0+i_1d_1+… +i_rd_r : i_1,…,i_r∈ 0,1,…,k-1. Then |S|≥ N^c_kn+o_k→∞(1).
Is complete integer factorization C_5 in deterministic polynomial time P?
Chung/Diaconis/Graham: For each k and every sufficiently large n with k dividing ((n-1) choose (k-1)), there is a universal cycle for the k-subsets of an n set.