Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let f be a Boolean graph property on the n choose 2 possible edges. A min-term graph property is a graph property of the type defined in Chakraborty's work, and f is non-trivial when it is not constant. Min-term sensitivity conjecture. The…
For the vertex-capturing game VC(n) on the complete graph K_n, let s_VC(n) denote the optimal score difference between the two players. Bensmail–Mc Inerney's conjecture. s_VC(n)= 2 if n=2 1 if n≡ 3 pmod 4 0 otherwise. The source attributes…
Let an n-dimensional poset poly-antimatroid be an n-dimensional poly-antimatroid that is closed under intersection, and let its convex dimension be the minimum number of chains whose unions describe the poly-antimatroid. Convex-dimension…
Let r(x)=√1+x/1-x and define R_n(x)=∑_k=0^2n-1R(n,k)x^k by (xD_x)^n(r(x))=fracR_n(x)(1-x)^n(1+x)^n-1√1-x^2. The recurrence is R_n+1(x)=(2nx+1)xR_n(x)+x(1-x^2)D_xR_n(x), with R_0(x)=1 and R_1(x)=x. Hurwitz stability conjecture. The…
A planar graph is a graph admitting a planar embedding. For a graph G, let c(G) denote its cop number and let cc(G) denote its attacking cop number. Planar attacking cop number conjecture. For every planar graph G, cc(G) ≤ c(G)+1. The…
Let G be a vertex-regular planar graph, and suppose that all but two faces of G have the same degree. Nearly platonic graph conjecture. The remaining two faces must have the same degree as each other. The conjecture arises from the…
Let B=b_1,b_2,… ,b_k⊂0,1,… ,n-1, and let B_i=b_1+i, b_2+i,…, b_k+i where addition is modulo n. That is, B=B_1,B_2,… B_N is the collection of cyclic translates of B. Prove that there exists a binary matroid M such that every B_i is a basis…
For a permutation π∈ S_n, let d_T(π,ι) be the minimum number of transpositions whose product sends π to the identity permutation ι. Define the transposition diameter by TD(n)=max_π∈ S_nd_T(π,ι). Determine the exact value of TD(16). The…
Let G be a graph, let A_k(G) denote its kth discrete homotopy group, and let hc_k(G) denote its kth discrete singular cubical homology group. Suppose n≥ 2 and A_k(G) is trivial for every k<n. Discrete Hurewicz conjecture. Then A_n(G)≅…
Let G be a possibly infinite graph and let rgeqslant 3 be an integer. A graph is r-locally series-parallel when each of its r/2-balls is series-parallel, and an r-local subdivision of a wheel or of K_4 is a subdivision H of a wheel or K_4…
Let G be a 2-connected cubic graph embedded in the torus. Grünbaum's conjecture. If G is not 3-edge-colorable, then G contains two edges on the same face of the embedding whose removal gives a planar graph in which the four endpoints of…
A real matrix is normal if it commutes with its adjoint; for real matrices this means MM^T=M^TM. Let a sign matrix be a matrix whose entries belong to ±1. Since every real symmetric sign matrix is normal, there are at least 2^binomn+12 n×…
Conjecture Every surreal number has a unique sign expansion, i.e. function f: o→ -, +, where o is some ordinal. This o is the length of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this…
Let H_n and I_n be respectively the n-th order Hilbert and identity matrices. Let det(H_n) be the determinant of H_n, and let APD_n-1(H_n) and APD_n-1(I_n) denote their first appearance values. Harmonic APD relation. For n ≥ 1,…
Let r≥ 2 and G be a r-uniform hypergraph with chromatic number 3 (that is, there is a 3-colouring of the vertices of G such that no edge is monochromatic). Suppose any two edges of G have a non-empty intersection. Must G contain O(r^2)…
Let (n,r,b) be integers with 0<r≤ n and 1≤ b≤binomnr. A linear (n,r,b)-matroid is a matroid with n elements, rank r, and exactly b bases that is represented by a matrix over a field. Linear matroid existence conjecture. A linear…
Is it true that the chip-firing halting problem for simple digraphs is NP-complete?
Let n be a positive integer, let there be n value measures on a cake, and let t be an entitlement vector. A t-proportional allocation assigns each agent a piece whose value according to that agent's measure is at least their entitlement.…
Let T be an n-vertex tree, and let sigma(T) and sigma_t(T) denote its Albertson irregularity and sigma_t-irregularity, respectively. Let P_n be the path on n vertices. Tree irregularity inequality conjecture. σ_t(T)≤ (n-2)σ(T). Equality…
Let G be a simple bipartite planar graph. Write |G|=|V(G)|, and let a(G) denote the maximum number of vertices in an induced forest of G. Akiyama–Watanabe conjecture. a(G) ≥ 5|G|/8. The conjecture was proposed in 1987. The paper proves the…