Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let λ be the partition of n whose diagram is the union of m rectangles described above. Let μvdash k and fix a permutation w_μ∈ S_k of cycle type μ. Let S_k^(m) be the set of permutations in S_k whose cycles are colored by [m]=1,…,m. For…
Let G be a graph, let Δ be its maximum degree, and let HG(G) denote its hat-guessing number. Maximum-degree hat-guessing conjecture. HG(G)≤ Δ+1. This conjecture tightens the folklore upper bound eΔ obtained from the Lovász Local Lemma and…
Let T be a tree on n vertices, let M be its order-k Steiner distance hypermatrix, and write sgn(x) for 1 if x>0, -1 if x<0, and 0 if x=0. Sign conjecture. For any tree on n vertices, sgn(det(M))=(-1)^n-1 when this quantity is nonzero. The…
Let M be a matrix with non-negative real entries, let t be an odd positive integer, and let (x_1,y_1),…,(x_t,y_t) be distinct entries of M satisfying M_x_i y_i=0 for every i=1,…,t. Matrix inequality conjecture. Then ∑_i=1^t∑_j=1^tM_x_i…
Let (G,<) be a preference system with ties where in every odd cycle there is a node that prefers its clockwise neighbour to its other neighbour, and there is another node that prefers its anti-clockwise neighbour to its other neighbour.…
Let Σ be a surface with Euler characteristic χ, let ω be the largest integer such that K_ω embeds in Σ, and let G be a graph embeddable in Σ. Write |V(G)| for the number of vertices of G. General exact upper-bound conjecture. Every graph G…
Let A be the adjacency matrix of a graph Γ on n vertices with vertex set V. Let C be the binary linear code generated by [I_n|A], and let d(C) denote its minimum distance. For a nonempty subset S of V, let von(S) denote its von Neumann…
Let lcsn denote the size of the largest critical set in any Latin square of order n. Largest-critical-set bound conjecture. lcsn ≤ n^2-n^3/2. This bound is motivated by the proof of the paper's Theorem 3.1 and is described as analogous to…
Let G be a connected graph and let e be a non-edge of G. Write the nonnegative real roots of the Laplacian matching polynomial 4LM_G(x)4 in non-increasing order as λ_1(G)≥…≥λ_n(G). Two-place LMRIV conjecture. When e is added to G,…
Let T be a triangulation of the partition simplex Δ^n-1, and let L:Vert(T)→ 2^[n] be a consistent labeling of T. A triangulation is friendly when it has the ownership structure required for the labeling L in the paper, and a labeling is…
Given a base graph G with property P, determine if there exists a permutation assignment to the edge of the base graph such that the lift of the graph inherits property P.
Let G be a graph with treewidth k and maximum degree Delta(G). The treewidth–maximum degree conjecture asserts that if Δ(G)≥ k+√k, then χ'(G)=Δ(G). The conjecture would improve the known sufficient bound Delta(G)≥ 2k-1 for graphs of…
We say that a,b∈ N are an amicable pair if σ(a)=σ(b)=a+b. Are there infinitely many amicable pairs? If A(x) counts the number of amicable 1≤ a≤ b≤ x then is it true that A(x)>x^1-o(1)?
There exists an absolute constant C>0 such that, for every integer t≥ 1, every graph G with no K_t minor satisfies χ(G)≤ Ct.
A snark is a bridgeless cubic graph that is not 3-edge-colourable, and a graph is cyclically 4-edge-connected if no edge cut of size less than 4 separates two components each containing a circuit. A dominating circuit in a graph G is a…
Let n and c be odd integers satisfying n=2c+1. Consider the even and odd hit-huggers beginning with 1 in S_n. A hit-hugger is a permutation subject to the hit-hugging relation considered in the paper, and the even or odd designation refers…
Let cal K be a simplicial complex of type 3,4, meaning that every (d-2)-face is contained in 3 or 4 faces of dimension d-1. Let (P_1,…,P_t) be the corresponding partition of 1,…,d, and let l_i denote zigzag lengths. Type-3,4 zigzag…
Let d_n^k denote the entries of Euler's difference table, with 0≤ k≤ n. For a sequence a_k_k≥ 0, define La_k=a_k^2-a_k-1a_k+1. A sequence is infinitely log-concave when L^la_k is positive for every l≥ 1. Infinite log-concavity conjecture.…
Let F(m) be the frequency sequence and let B_k=2^k,…,2^k+1-1. For each block, let m_k be an index at which F(m) attains its maximum. Peak location law. The peak locations satisfy m_k=4/32^k+O(1). Numerical experiments suggest this…
Let M and M' be sixth-root-of-unity matrices representing the same matroid M. The lattices ker_C(M)∩ E^E and ker_C(M')∩ E^E are isometric if there is a bijection between them preserving their inner products. Isometry conjecture. If M and…