Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is the chip-firing halting problem in P for Eulerian digraphs with multiple edges?
Does every complete graph on an even number of vertices admit a perfect 1-factorization?
Let O denote the graph with vertex set consisting of all lines through the origin in R^3 and two vertices adjacent in O if they are perpendicular. Problem Is χ_c( O) = 4?
For a graph G, let ν(G) denote its matching number and ν_ur(G) its uniquely restricted matching number. For every positive real number ε and every positive integer Δ, consider graphs of maximum degree at most Δ and girth at least g.…
Let C be a class of graphs. A graph is of bounded shrub-depth if its shrub-depth is bounded by some fixed integer. Shrub-depth characterization conjecture. The class C is of bounded shrub-depth if, and only if, there exists an integer t…
Let ind(k,ℓ) denote the limiting maximum proportion of k-vertex subsets inducing exactly ℓ edges. Quadratic edge-statistics conjecture. For all pairs (k,ℓ) satisfying min ℓ, binomk2 - ℓ = Ω(k^2), we have ind(k,ℓ) = O(k^-1/2). The…
For each positive integer d, let C_d be the set of content arrays α∈sf Cont_1^d,1^d for which the diagonal entry sf RSK_1^d,1^d(α,α) is zero. Asymptotic zero-diagonal conjecture. lim_d→∞|C_d|/d!=1. The initial computed values of |C_d|…
Let J_n(x) be a finite linear Jaco graph of order n≥3, and let X be its Δ-set, equivalently its Jaconian set, consisting of vertices attaining the maximum degree. A sequence is p-graphical for a graph family F when it gives the values of a…
For sequences of finite weighted networks with an SIS stationary infected count, does a separation between sublinear and linear infection at two virulence thresholds imply analogous phase-transition behavior in general networks?
Let G range over graphs. For each K∈N, let α_K denote the smallest K-asymptotic robustness ratio over all graphs, and let α^*(G) denote the randomized robustness ratio of G. Asymptotic robustness limit conjecture. lim_K → ∞ α_K = inf_G…
Let P) and Q be two colored paths on m vertices with concentration matrices K_P and K_Q satisfying det(K_P)=det(K_Q). A reflection of a colored path is the path obtained by reversing its vertex order. Colored-path determinant conjecture.…
Let i(P) denote the number of independent sets of a connected planar graph P. Planar Linek's Problem. Every positive integer is equal to i(P) for some connected planar graph P. The conjecture strengthens the proved result that almost every…
Let Q_n denote the set of Stirling permutations of order n, and let flat_3(Q_n) be the set of those with exactly three runs. Three-run enumeration conjecture. The number of Stirling permutations of order n with exactly three runs is…
Let T(n,k) satisfy the two-dimensional recurrence T(n,k)T(n-k,k)=T(n-i,k+2)T(n-k+i,k-2)+T(n-j,k+1)+T(n-k+j,k-1), with initial terms T(i,j)=x_i,j for all i<0. Consider the recurrence families conjectured to produce integer sequences in…
Let Q=(u,u-r) with r≥3, and let P_k,1 denote the entries in the first column of the table T(Q). Recall that for partitions P=(p_1≥ p_2≥…) and P'=(p'_1≥ p'_2≥…) of the same integer, P≥ P' in the Bruhat order when ∑_i=1^m p_i≥∑_i=1^m p'_i…
Let G be a bounded-degree expander, or strongly ergodic, graphing that can be properly colored by C colors with arbitrarily small error. Can it be properly C-colored?
Seymour/Szekeres: The "cycle double cover conjecture" states that every bridgeless graph contains a set of cycles which cover each edge of the graph exactly twice. See this and this.
A d-dimensional polystochastic matrix of order n is a nonnegative d-dimensional array whose entries on every line sum to 1. Its permanent is the sum of the products selected by diagonals. Taranenko's conjecture. The permanent of every…
Let G be a graph of order n in which every vertex is redundant and no vertex is surrounded. Its diameter is the graph distance between vertices at maximum distance. Maximum-diameter conjecture. The maximum diameter of such a graph is ⌊…
Fix r∈(0,1) and consider words in W(ℓ r,ℓ(1-r)). Choose w uniformly from this set, choose u uniformly from the ~_2-class of w, and choose v uniformly from the immediate neighbours of w in that class. Random-equivalence conjecture. The…