Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Does every two-colouring of the edges of K_n contain at least (1+o(1))n^2/12 pairwise edge-disjoint monochromatic triangles?
A matroid Chow ring is the Chow ring associated with a matroid. These rings form a conjectural class of quadratic algebras arising in the same general setting as the cohomology rings of wonderful models. Matroid Chow-ring conjecture. The…
For n,m∈ N, let ExistsEventuallySurjective(n,m) mean that there exists a function f: P(Fin(n))→ Fin(n) which satisfies, for every subset Y⊆Fin(n) with |Y|≥ m, f(A):A⊆ Y=Fin(n). Define H(0)=0, and for n>0 let H(n) be the infimum in N of the…
A frequency square of type (n;λ) is an n× n array in which each symbol occurs exactly λ times in every row and every column. Two frequency squares are orthogonal if each ordered pair of symbols occurs equally often in corresponding cells.…
For which restricted classes of digraphs can the fixed-k edge-disjoint paths problem be solved in polynomial time? Here the input is a digraph G and k terminal pairs, and the task is to decide whether mutually edge-disjoint directed paths…
Let G be a finite undirected simple graph. A k-page book embedding of G consists of a linear order preceq of V(G) and a (non-proper) k-colouring of E(G) such that edges with the same colour do not cross with respect to preceq. That is, if…
Given coprime a,n∈N, can a prime p≡ apmod n be found in deterministic polynomial time?
Let q_1,…,q_n be nonzero algebraic numbers in the unit open disc such that the 3n numbers J(q_i), DJ(q_i), D^2J(q_i) (i=1,…,n) are algebraically dependent over Q. Then there exist two indices inot = j \ (1≤ i≤ n, 1≤ j≤ n) such that q_i and…
For every finite matroid M of rank r, let Δ(M) be its independence complex and let h(M)=(h_0,…,h_r) be defined by ∑_i=0^rf_i-1(Δ(M))(t-1)^r-i=∑_i=0^rh_i t^r-i, where f_-1(Δ(M))=1. Then h(M) is a pure O-sequence: there exists a finite pure…
Let G be a graph, let Δ(G) denote its maximum degree, and let X,Y⊆ V(G). A set of vertices separates X and Y if it intersects every X-Y-path; paths are pairwise at distance at least d when their graph distance in G is at least d. The…
Given an elliptic curve E:y^2=x^3+Ax+B over Q, determine whether E has infinitely many rational points.
Fix a rooted radius-r ball B(o,r) that occurs as every radius-r ball of some finite graph. What is the minimum diameter of a finite graph all of whose radius-r balls are isomorphic to B(o,r)? Bound this diameter in terms of r and the root…
Let G=(V,E) be a graph with at least 4 vertices. A graph is (3,6)-tight when |E|=3|V|-6 and every vertex subset U with at least two vertices spans at most 3|U|-6 edges. For an edge e, write (V,S)/e for the graph obtained by contracting e.…
Conjecture For every graph G without a bridge, there is a flow φ: E(G) → S^2 = x ∈ R^3: |x| = 1 . Conjecture There exists a map q:S^2 → -4,-3,-2,-1,1,2,3,4 so that antipodal points of S^2 receive opposite values, and so that any three…
Let G be a graph, let α(G) be its independence number, let v be the number of vertices of G, and let Δ be its maximum degree. AGX's order-to-degree conjecture. α(G)geqv-1/Δ The source attributes this bound to AGX conjecture-making software…
Consider a length-regular drawing of the d-dimensional hypercube, with edge lengths ℓ_1≤ ℓ_2≤…. Length-profile conjectures. The following assertions are proposed: (1) for every i, ℓ_i≤ 2^d-1-2^d-(i+1); (2) there must exist edges of even…
Additionally the authors of [7] observed that the number of vertices of the graphs Gℓ from Theorem 3 is exponential in their treewidth, while for walls and their line graphs, the number of vertices is polynomial in the treewidth. This…
Conjecture Let G be a simple graph with n vertices and list chromatic number χ_ℓ(G). Suppose that 0≤ t≤ χ_ℓ and each vertex of G is assigned a list of t colors. Then at least tn/χ_ℓ(G) vertices of G can be colored from these lists.
Let LB_κ(θ) and LB'_κ(θ) be the stated inner-minimization problems, with variables r, s, r_1, r_6, s, t, s_1,2, and parameter κ. Triangle-free extremizer conjecture. For all initialization angles θ, the optimal values in these minimization…
Let S be a section, let f be a state, and let (x_0,y_0,t_0) be a point in overset∘Y∩L in the future of S. Assume that the cone C meets S in at least one point, and let W be the closure of the prescribed intersection of S with the interior…