Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
The strong grid is the graph obtained from the square grid by joining vertices that are at king-move distance one, so each vertex is adjacent also to its diagonal neighbours. In the Pyro game, firefighters protect vertices while the fire…
Let t be an integer satisfying t≡ 0,1,2pmod6, and let r be an integer with r>⌊ t/6⌋. The extended cube graphs are denoted by ECG(t,6r-t-4). Extended-cube conjecture. These graphs have field-independent minimum rank, and their adjacency…
Pach, Tóth: Define the "crossing number" of a graph to be the minimum number of (topological) crossings of edges in any straight-line embedding in the plane. Define the "pairwaise crossing number" of a graph the be the minimum number of…
Is there such a bound depending polynomially on the degree and height of P?
If a polarized projective manifold (M,L) is K-stable relative to a maximal algebraic torus T in Aut(M), does the polarization class c_1(L) contain an extremal Kahler metric?
A superpermutation on n symbols is a string containing every permutation of the n symbols as a contiguous substring. Determine the minimum possible length of a superpermutation for every n>5.
For an n-Venn diagram, consider the graph whose vertices are the crossings of the curves and whose edges are the curve segments between consecutive crossings; this graph may have multiple edges. Pruesse and Ruskey's conjecture. For n≥ 2,…
Let A_n:=α(n;1,2,…,n), and let n≥2 and i=1,…,n-1. One-descent conjecture. The identity A_n=α(n+2;1,2,…,i+1,i,i+1,…,n) should hold. This is a computational conjecture related to a broader reverse-duplication identity developed later in the…
A covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one of the codewords by changing at most R bits. How big is the smallest covering code of radius R with n bits? It is known to be a…
For a PDE-inspired graph functional f and its continuum counterpart F, determine graph analogues of F's properties, whether the graph functionals converge to F, how their minimization algorithms can be used for data analysis and image…
Which hard graph problems can be efficiently solved by translating graphs to their word representations?
Let S be a family of finite graphs such that for every n there is some G_n∈ S such that if the edges of G_n are coloured with n colours then there is a monochromatic triangle. Is it true that for every infinite cardinal ℵ there is a graph…
For every connected graph G with maximum degree Δ(G)≤ 3, the domination number satisfies γ(G)≤ 2ρ(G)+1, where ρ(G) is the maximum cardinality of a set of vertices whose pairwise distances are at least 3.
Let G be a graph of even order. A spanning balanced bipartite subgraph B is a spanning bipartite subgraph whose two vertex classes have equal size. Bollobás–Scott's conjecture. G contains a spanning balanced bipartite subgraph B such that,…
Let G=(V,E) be a non-acyclic graph, with a fixed-point-free involution μ:V→ V and, for every vertex v, a bijection σ_v:δ(v)→δ(μ(v)). Assume that λ(v,μ(v))=deg(v) and σ_μ(v)=σ_v^-1. Tiling conjecture. There exists a nonempty list of cycles…
Let (α,β,γ) be the type of an Ulrich partition. Nonexistence conjecture. There are no Ulrich partitions of type (α,β,γ) if β≥3 and γ≥3. The paper states that its partial classification implies this is equivalent to the complete-list…
Let G be a graph and let an end of G be an equivalence class of rays, where two rays are equivalent if there are infinitely many vertex-disjoint paths between them. The degree of an end is the maximum cardinality of a collection of…
Let A be a finite simplicial hyperplane arrangement of rank r, and let W(A) be its poset of regions with the standard region order. Is dim W(A)=r for every such arrangement?
We are given a hypergraph G_0=(V,E_0) of rank at most k (where k is fixed, not part of the input) and a symmetric function r:V× V→ Z_+. Can we find in polynomial time a graph G=(V,E) with a minimum number of edges such that λ_G_0+G(x,y)≥…
Let G satisfy the paper's general-graph regularity assumption, and let V_n _n ≥ 1 satisfy the candidate-set assumption. For each initial source v, write P_v for probability under source v, let v^* be the true source, let widehatv_B(t) be…