Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let S be an n× n array filled with the symbols 1,…,n, with each symbol occurring exactly n times. A partial transversal is a collection of cells with no two in the same row, column, or symbol. Stein's equi-n-square conjecture. Every such…
Let ℓ(n) be the least positive integer such that ℓ(n)geqslant n and every Latin array of order n with at least ℓ(n) distinct symbols contains a transversal. Akbari–Alipour's unbounded gap conjecture. For every integer c, there exists a…
For a graph G, let ρ(G)=h(G)/|V(G)| be the maximum density among half-dependent sets in G. For the two-dimensional kings graph K^(2)[n], write ρ^(2)(n)=ρ(K^(2)[n]), ρ^(2)=lim_n→∞ρ^(2)(n). Two-dimensional kings graph density conjecture. The…
Let P_n be the path on n vertices, let F be a non-empty linear forest on m vertices, let K_1∨ F denote the join of F with a single vertex, and let o(F) be the number of odd-order components of F. Path–linear-forest quasar Ramsey…
Let G be a graph, let I_G be the family of independent sets of G, and let I_G^(r) be its r-th level. Two subfamilies are cross-intersecting if every member of one intersects every member of the other. Write μ(I_G) for the minimum base…
Let f(n) be the smallest integer such that every simple graph on n vertices with minimum degree at least f(n) contains a cycle of length 4. Is it true that, for all sufficiently large n, f(n)≤ f(n+1)?
A graph G is k-choosable if, for every assignment L of a finite list of exactly k natural-number colours to each vertex, there exists a proper colouring C of G such that C(v)∈ L(v) for every vertex v. Define the list chromatic number…
Conjecture 3. (Seymour) Any simple digraph with no loops or digons has a vertex v whose second neighborhood is at least as big as its first neighborhood, i.e. |N +2 (v)| ≥ | N +(v)|. The following is known for Seymour's second neighborhood…
For a nonamenable group Γ, does the Bernoulli shift 0,1^Γ factor onto 0,1,2^Γ?
Explicitly construct test elements or principal homogeneous spaces having prescribed ramification and a prescribed large prime order ℓ.
A Šoltés graph is a graph G for which deleting any vertex leaves the Wiener index unchanged. Regularity conjecture. If G is a Šoltés graph, then G is regular. This conjecture proposes that every solution to the Šoltés problem has all…
A brick is a 3-connected bicritical graph. A brick G is minimal if G-e is not a brick for every edge e of G. Write V(G) for its vertex set and let |V(G)| denote the number of vertices. Norine–Thomas conjecture. There exists a constant α>0…
Let P be a point configuration on n^2 points, and let f^(n,…,n) denote the number of standard Young tableaux of the square partition (n,…,n), equivalently the number of stable states of the identity configuration. For n∈N, the conjecture…
overlineG is a universal odd distribution with values in groups where multiplication by 2 is invertible.
For the symmetric 2-groups SBM, show that Gibbs sampling achieves ε correlation with the truth, above the KS bound.
Let K_n^d be the full d-dimensional simplicial complex on n vertices, and let Z^d-1 be a non-trivial (d-1)-cycle with coefficients in either F_2 or Q. Let FILL(Z_n^d-1) denote the recursive filling procedure used in the source, and let the…
For fixed k>r and all sufficiently large n, do the divisibility conditions binomk-ir-i|binomn-ir-i for 0≤ i<r guarantee an r-(n,k,1) design? Equivalently, can one choose binom nk/binom kr many k-subsets so that every r-subset lies in…
Let C_n be the cycle on n vertices and let W_m:=C_m* K_1 be the wheel on m+1 vertices. For integers n<m, with n odd and m even, the Ramsey number r(C_n,W_m) is the least integer N such that every red-blue coloring of the edges of K_N…
Let K_1,2,2,2 be the complete multipartite graph with parts of sizes 1,2,2,2. A planar semi-cover G' is the planar graph notion defined in the source, and let H be the subgraph required to satisfy the conditions listed in Lemma .…
For a permutation σ of 1,2,…,n and a permutation β of 1,2,…,k, say that σ contains β as a pattern if there are indices 1≤ i_1<i_2<…<i_k≤ n such that, for all 1≤ a<b≤ k, σ(i_a)<σ(i_b)⇔ β(a)<β(b), and say that σ avoids β otherwise. For n≥ 1…