Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be an infinite Cayley graph of a group that is not virtually cyclic. Prove that there exists p<1 for which Bernoulli p-edge percolation on G has an infinite cluster.
Is computation of a curve's zeta function polynomial simultaneously in the genus g and in log q?
Suppose X, Y are finitely-supported independent random variables taking integer values such that X + Y is uniformly distributed on its range. Are X and Y themselves uniformly distributed on their ranges?
Given n points in R^2, no five of which are on a line, the number of lines containing four points is o(n^2).
Let G be a simple graph. Two k-edge-colourings are Kempe-equivalent if one can be reached from the other through a series of Kempe changes using colours from 1,…,k. Mohar's conjecture. All (Δ(G)+2)-edge-colourings of G are…
Given a symmetric crossing supermodular function p:2^V→ R and positive integers n_1,n_2,…,n_k, does there exist a hypergraph H=(V,E) covering p and having exactly k hyperedges of sizes n_1,n_2,…,n_k?
For every finite multigraph G of maximum degree at most Δ, and every pair of vertices x,y with graph distance d_G(x,y)=t, the number n_G(x,y) of shortest x–y paths satisfies n_G(x,y)≤ Δ(⌊Δ/2⌋⌈Δ/2⌉)^(t-1)/2.
Let p be a prime, let L(p) be defined by L(p)= (p-1)/4 if p≡1pmod 8, (p+1)/4 if p≡3pmod 8, (p+3)/4 if p≡5pmod 8, (p-3)/4 if p≡7pmod 8, and let U_1(p) denote the number of unconnected graphs in the linear family. Exact-count conjecture. For…
Let g≥ 1. Brill–Noether non-existence conjecture for real divisors. There exists a family of undirected, connected multigraphs, one for each genus, such that for every pair of real numbers r≥ 0 and 0≤ d≤ 2g-2, if ρ(g,r,d)=g-(r+1)(g-d+r)<0,…
Open Problem: Iterative rounding for feedback vertex set Samuel Fiorini The (undirected) feedback vertex set problem is to find, given a vertex-weighted graph (G, c) a minimum cost set X such that G − X is a forest. Is it true that for…
Let G be a connected, quasi-transitive, locally finite graph. An end of G is thick if it contains infinitely many pairwise disjoint rays, and an ultra-fat model of the half-grid is a model of the half-grid in G satisfying the ultra-fatness…
Conjecture Every planar graph of girth ≥ 4k has a homomorphism to C_2k+1.
Let M≥ 2. An equiangular tight frame (ETF) in C^M with N vectors is denoted by ETF(M,N); the maximal possible number of vectors in the complex case is N=M^2. Zauner's conjecture. There exists an equiangular tight frame ETF(M,M^2) for every…
Is there a constant c > 0 such that f(n) ≥ Ω(n^c)?
Let G be a finite simple graph. Say that G is 5-connected if |V(G)| ≥ 6 and, for every set S ⊆ V(G) with |S| ≤ 4, the graph G - S is connected. Say that G contains a subdivision of K_5 if there exist five distinct vertices v_1, …, v_5 ∈…
Let T be a tree, let p be its number of internal vertices, and let ρ^±_ℓ(T) denote its signed list-ranking number. Signed tree list-ranking conjecture. For every positive integer p, there is a positive integer q_p such that, for every tree…
For n≥3, let K_3,n=overlineK_3∨overlineK_n and K_1,1,1,n≅ K_3∨overlineK_n. Complete multipartite formula conjecture. Their Speyer polynomials are g_K_3,n(t)=t(nt^2+nt+t+2)(2+t)^n-1-3t(1+t)^n+1 and g_K_1,1,1,n(t)=t(nt^2+nt+t+2)(2+t)^n-1.…
Prove unconditional lower bounds such as n^{\Omega(k)} for resolution or another restricted proof class certifying that an n-vertex graph has no k-clique.
For a partition λ, let K_λ be the matrix whose rows are indexed by horizontal tableaux of shape λ and whose columns are indexed by vertical tableaux, with entries K_λ^μ,ν= 1 if μ⊥ν; 0 otherwise. Here μ⊥ν means that every row of the…
Let G be a graph with a standard edge, meaning an edge that is neither a loop nor an isthmus, and let ψ be a strongly Tutte-descriptive activity. A spanning tree T has an edge active when that edge belongs to ψ(T). Inactivity conjecture.…