Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G=(V,E)) be the infinite king grid with vertex set V=Z×Z, in which two vertices are adjacent exactly when their Euclidean distance is at most √2. For a set S⊆ V, define its density by D(S)=limsup_k→∞|S∩ N_G^k[u]|/|N_G^k[u]|, where…
In permutation Wordle, a setter chooses a hidden permutation uniformly from S_n, and a strategy guesses permutations while receiving the positions that are correct. The number of rounds is the number of guesses needed to identify the…
Let G be a connected cubic graph, and let V(G) denote its vertex set. A dominating set is a subset of vertices such that every vertex outside the subset has a neighbor in it. Reed's conjecture. Every connected cubic graph G contains a…
For a positive integer n, let C_n be the cyclic group, let widetilde S_n,j-1 be the set of decorated permutations with the specified excedance statistic, and let widetilde a_n,j(q) be the associated polynomial. Cyclic sieving conjecture.…
Conjecture If F is a finite field with at least 4 elements and A is an invertible n × n matrix with entries in F, then there are column vectors x,y ∈ F^n which have no coordinates equal to zero such that Ax=y.
Consider a matrix where both columns are rows are t-sparse. LLL gives a discrepancy bound of O(√tlog t) here. If we assume the stronger property that every pair of rows intersect in at most one element, can we get a O(√t)?
Let G be a graph of even order, and let k be an integer. A graph is 1-factorable if its edges can be partitioned into 1-factors, equivalently if its chromatic index equals its maximum degree. 1-Factorization Conjecture. If G is k-regular…
Let (Γ,Σ) be a nontrivial graph pair, meaning that Γ and Σ are coprime connected twin-free graphs and exactly one of them is bipartite. Assume that the graphs have no loops and that Σ is bipartite. Wang–Qin–Xia's conjecture. The pair (Γ,Σ)…
Conjecture 4. (Behzad, Chartrand, Wall [2]) The minimum number of vertices in an r-regular digraph G with girth g is r(g − 1) + 1. Behzad, Chartrand and Wall give an example achieving this by placing r(g − 1) + 1 vertices on a circle with…
For a fixed E/F_q, prove that #E(F_q^n)/#E(F_q) is prime for infinitely many n.
A natural question is which results from finite combinatorics have analogues ’definable’ (i.e., Borel, µ-measurable, \tau -Baire measurable) counterparts for Borel graphs. Measurable combinatorics in hyperfinite graphs Matt Bowen (joint…
Let λ∈D_n be a fixed partition, and let ε>0. For a uniformly random rook placement π~Unif(RP(N⊙λ)), write widetildeξ_π(t) for its rescaled profile and m_λ(t) for the limiting mean profile. Uniform convergence conjecture. P…
For the relevant plabic graph G_0 of Gr_{k,n}(C), is the associated Newton--Okounkov body NO_{G_0} unimodularly equivalent to the FFLV polytope FFLV(r\omega_k)?
Let G be a cubic graph. A circuit double cover (CDC) is a set of circuits such that every edge of G is covered by exactly two circuits. A graph is cyclically 5-edge-connected if no edge cut of size less than 5 separates two circuits.…
Let G be a graph, let overline G be its complement, and let ρ ^⊥ denote orthogonal representation dimension. The complementary-dimension bounds conjecture. The two dimensions satisfy ρ ^⊥(G)+ρ ^⊥(overline G)≥ |V(G)|-2 and ρ ^⊥(G)+ρ…
Given two distinct n-leaf networks N_1 and N_2, with V_N the Zariski closure of the model variety of N, determine conditions under which V_{N_1} \cap V_{N_2} is a proper subvariety of both V_{N_1} and V_{N_2}.
Question Is it true that every permutation of positive integers must contain monotone 4-term arithmetic progressions?
Let R(G;k) denote the minimal m such that if the edges of K_m are k-coloured then there is a monochromatic copy of G. Show that lim_k→ ∞fracR(C_2n+1;k)R(K_3;k)=0 for any n≥ 2.
Let R and S be partitions of the same weight, and suppose that the class cal A(R,S) of matrices with row and column sums prescribed by R and S is nonempty. For a matrix A, let ρ_t(A) denote its t-term rank, and write…
For every loopless multigraph G, the list edge-chromatic number equals the edge-chromatic number: ch'(G)=χ'(G). Equivalently, if each edge of G is assigned a list of at least χ'(G) colors, then G has a proper edge coloring choosing for…