Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let A⊂ N be an additive basis of order 2. Must there exist B=b_1<b_2<…⊆ A which is also a basis such that lim_k→ ∞b_k/k^2 does not exist?
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 A be the n-th order row-shifted second-power lattice with entries A[i,j]=(j+(i-1)d)^2, where d is a positive integer, and define T_n-1=n(n-1)/2. Let f(σ)=∑_i=1^n A[i,σ(i)]. Row-shifted second-power lattice value conjecture. For n ≥ 2,…
Let d≥ 1, let K be an arbitrary field, and let G be a graph on vertex set [n]. Primality and complete-intersection conjecture. If G is (n-d)-connected, then L_G is prime and a complete intersection. For d=2, the corresponding result is…
Let G=(V,E) be a finite connected graph. For each independent edge set S of G, let ω_G(S) be the product of the sizes of the connected components of (V,S), and let ω_G vanish outside the independent sets. Graph component-weight Rayleigh…
A brace is a bipartite matching covered graph with no nontrivial barrier. A 3-line is an edge whose two endpoints have degree 3. Let G be a minimal brace with at least 6 vertices. 3-line conjecture. G has a 3-line. This conjecture extends…
Let G=(V,E) be a simple graph, where V is its vertex set. A graph is critically s-chromatic if it has chromatic number s and deleting any vertex lowers its chromatic number. For a subset W⊆ V, let G[W] denote the graph obtained by…
Let G be a finite graph and let t∈N. A minor of G is a graph obtainable from G by a sequence of vertex deletions, edge deletions, and edge contractions; write χ(G) for the chromatic number and K_t for the complete graph on t vertices.…
Let E_d(m,n) be the count and let p_d(m,n) be the closed-form polynomial. When s=min(m,n)<d-1, write the correction in the larger variable as B_d^(s)(n):=E_d(s,n)-p_d(s,n). Boundary-correction structure conjecture. For every d≥4 and every…
Let G=(V,E) be a connected graph, and let Rel(G;q) denote its all-terminal reliability polynomial in the edge-failure probability q. A complex number z is an all-terminal reliability root if Rel(G;z)=0. Brown–Colbourn conjecture. If z is a…
For each n≥ 2, let G_n be the set of Gilbreath sequences of length n, let K_S denote the valid-extension set associated with S, and let U_n be the doubling sequence. Maximum-width conjecture. max_S∈G_n|K_S|=2^n-1+1, and the maximum is…
For the k-point semidefinite-programming bounds \Delta_k(G_{n,a})^* for the equiangular-line graph, explain their stabilization at (1/a^2-2)(1/a^2-1)/2, determine whether \Delta_k(G_{n,a})^*=\Theta(n^2) for fixed k and a, and compare the…
Let G be a graph with the maximum possible number of edges among graphs that do not contain k cycles of consecutive even lengths. A block is a maximal connected subgraph with no cut vertex. Sudakov–Verstraëte's conjecture. Every block of G…
Let Λ_n be the n-dimensional lattice graph, and let P_k denote the path on k vertices. For a finite graph H, a t-PDDS[H] in Λ_n is a perfect distance-dominating set whose components are all isomorphic to H. The Cartesian product of graphs…
Conjecture Every tournament D on an even number of vertices can be decomposed into ∑_v∈ Vmax0,d^+(v)-d^-(v) directed paths.
Let M be an ω-categorical structure with growth rate f_M(n), and for k∈N let the generalized Fibonacci numbers be defined by F_n,k=∑_i=1^kF_n-i,k, with F_n,k=0 for n<0 and F_0,k=1. Generalized Fibonacci growth conjecture. If…
For every connected graph G on n vertices, let λ_1,…,λ_n be the eigenvalues of its adjacency matrix, and define s^+(G)=∑_λ_i>0λ_i^2 and s^-(G)=∑_λ_i<0λ_i^2. Then mins^+(G),s^-(G)≥ n-1.
Are there entire transcendental functions f(z) such that if x is a Liouville number then so is f(x)?
Note that i(P;1;n) = i(P;n). It is known that i(P;ω;n) is a polynomial with leading coefficient given by ∫_P ω. Investigate ω-Ehrhart function for well-known classes of polytopes.
Let D=2^i| i∈Z_≥ 0, and let Δ(D,k) denote the diffsequence parameter studied in the paper for the set D and positive integer k. Diffsequence growth conjecture. When D=2^i| i∈Z_≥ 0, Δ(D,k)=2^Θ(√k). The paper establishes a lower bound with…