Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A triangulation is a plane graph in which every face, including the outer face, is bounded by a triangle. The degree of a vertex is its number of incident edges. The bounded-exception domination conjecture. For every constant t, there…
Let d be an integer, let m be given, and let n>m with n=m+k. A regular solution to the (n,d)-queens problem is a solution containing a subset of size k^d with p queens. The (m,d)-board is the board of side length m in dimension d.…
For every ε>0, there exists a finite simple graph G on n vertices such that δ(G)≥ (3/4-ε)n and G is not globally synchronizing for the Kuramoto model; equivalently, the Kuramoto energy on G has a local minimum other than a fully…
Given a graph G=(V,E), and weight and capacity functions w,u: E → R_+ defined on the edge set, is there a combinatorial, strongly polynomial algorithm to find a vector x maximizing wx subject to the constraints x ∈ P(G) and x ≤ u, where…
Let χ_lat(R^n) denote the minimum number of colors in a lattice coloring of R^n such that no two points of the same color are at Euclidean distance 1. The conjecture asserts that χ_lat(R^4)=49 and χ_lat(R^5)=140; equivalently, there are…
Let v_1,…,v_n be positive integers, and let ML(v_1,…,v_n)=max_t∈Rmin_1≤ i≤ nlVert tv_irVert, where lVert xrVert denotes the absolute distance from x to the nearest integer. The Loneliness Spectrum Conjecture. One has either ∃ s∈N,…
Can the sequence of metric balls in an infinite Cayley graph form a family of expanders?
If a_0,a_1,a_2,… is a sequence of integers and a_0 = 1 ≤ a_1 ≤ a_2 ≤ … can we find a caterpillar graph C such that Z_0(C) = a_0, Z_1(C) = a_1,...?
Let an S-polygon be a polygonal configuration equipped with a contour, and let the orbit of a contour be the set of contours reachable from it by solitaire moves, with diameter measured in the solitaire-move graph. Contour orbit diameter…
For every positive integer d and finite graph G, K_{d+2} is a minor of G if and only if gamma(G)\geq d, where gamma(G) is the largest integer q for which some connected family of induced subgraphs of G has nerve with nonzero H_q.
Construct a malleable RSA generator producing publicly related moduli n,n' such that factoring n' makes n easy to factor.
Is the no-complex-multiplication condition in the stated lower bound for Heegner points necessary?
Let n denote the size of the one-dimensional game board, and let the robber have arbitrary speed. The game is played with cops attempting to catch the robber. Sublinear cop conjecture. In the one-dimensional game of Rugby, for all speeds…
Let T be an irreducible hypertree, and identify it with its graph G, whose edges are the pairs occurring in the triples of T. Irreducible hypertree copiousness conjecture. Every irreducible hypertree is copious. The paper proves this for…
Let C_2k+1 denote the family consisting of the cycle C_2k+1, and let sat_g(C_2k+1;n) be the corresponding saturation-game value on n vertices. Consecutive odd-cycle saturation-game monotonicity conjecture. For all k≥ 2, sat_g(C_2k-1;n)≤…
Let G be the star graph on n vertices, and let S_λ be the Specht module indexed by a partition λ. Write λ_2 for the second part of λ, and let H_i,0(G) denote the degree-zero chromatic symmetric homology component in homological degree i.…
What is the saturation number sat(n,C_k), the minimum number of edges in a C_k-free graph on n vertices such that adding any missing edge creates a copy of C_k?
Let G be a loopless graph with maxmaxflow Λ, and let P_G(q) be its chromatic polynomial. Maxmaxflow chromatic positivity conjecture. For every real q>Λ, P_G(q)>0. In particular, P_G(q) has no roots in (Λ,∞). The source presents this as a…
Let G be a bipartite cubic planar graph, meaning that G is bipartite, planar, and every vertex has degree three. A graph is dispersable if it has a proper Δ(G)-edge-colouring and a Δ(G)-page book embedding in which all edges of one colour…
Let G=(S,T;E) be a bipartite graph. An S-link is a path of length 2 whose two endpoints lie in S, and a family of S-links is node-disjoint if no two links share a node. A matching is a set of pairwise nonincident edges. Liang's conjecture.…