Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let Σ be a two-letter alphabet, let w,v∈Σ^+ with w≠ v, and let n≥ 2. Write w↔ v when w and v differ by one adjacent swap, and let ~_n denote equivalence in UT_n(T). Adjacent-swap connectivity conjecture. w~_n v if and only if there exists…
Let r(G) denote the two-color Ramsey number of a graph G. Let G be a graph, and let H be obtained from G by deleting a single vertex. Conlon–Fox–Sudakov conjecture. There exists a universal constant C>0 such that r(G)≤ C· r(H). The paper…
Let n=p^2+p+1 for a prime power p. If a pairwise balanced design on n points has t>n blocks, must t≥ n+p?
For even n, determine if the disjoint union C_n dot∪ C_n is edge-magic total. For m ≥ n, determine if the disjoint union C_m dot∪ C_n is edge-magic total.
Let G be a bridgeless cubic graph, let a∈ E(G), and let i∈0,1,2. For a list of perfect matchings, define ν_G[a:M_1,M_2,M_3] to be the number of those matchings containing a. Frequency formulation of the Fan–Raspaud conjecture. There exist…
Let X be a digital image, meaning a finite graph-like digital topological space, and let C_n denote the cycle of n points. Call X non-rigid if it admits a continuous self-map homotopic to the identity that is not the identity, and…
Let G be a graph on n-1 vertices, and let k→ l be an edge in G. Construct a graph G' on n vertices by subdividing the edge k→ l: add vertex n and replace the edge k→ l by the two edges k→ n and n→ l. Edge-subdivision conjecture. If G has…
Let s_q(K_t) denote the minimum degree parameter for q-color Ramsey problems with clique target K_t. Fox–Grinshpun–Liebenau–Person–Szabó conjecture. For all qgeqslant 3 and tgeqslant 3, we have s_q(K_t) geqslant s_q(K_t-1). This conjecture…
Is it true that for every n≥ 1 there is a k such that n(n+1)…(n+k-1)| (n+k)… (n+2k-1)?
Let K_1,n be the star graph with n leaves. Suppose that n divides binomn+12. A combined voltage assignment (α,ω) on a base graph X with values in the group Z_n defines a covering graph X^(α,ω). Covering conjecture for 2-token star graphs.…
Let k be a positive integer and set n=(k-1)^3. Write obreakSav_n(12… k) for the set of permutations of length n whose square strongly avoids the increasing pattern 12… k. Sharpness conjecture. Sav_n(12… k)≠∅. The conjecture asserts that…
Let [n]^3 be the n× n× n cube, and let s_3(n) denote the minimum possible area covered by the three orthogonal projections onto the faces of a solution to the faces of [n]^3. Projection-area conjecture. s_3(n)≥ n^2+6n-4 for all n. The…
Does |w| greater than 7/3 tau(w) minus 4 imply tau(w)=pi(w); what is the infimum d for which a counterexample has |w| at least 7/3 tau(w) minus d; must such extremal words be Assous-Pouzet words; and for fixed delta how can all words with…
Let A⊂ R^2 be a set of size n and let d_1,…,d_k be the set of distinct distances determined by A. Let f(d) be the number of times the distance d is determined, and suppose the d_i are ordered such that f(d_1)≥ f(d_2)≥ … ≥ f(d_k). Estimate…
If H is anti-ferromagnetic, meaning all eigenvalues of its edge-weight matrix except the top one are nonpositive, is the triangle-free hypothesis on G removable from the homomorphism inequality for d-regular graphs?
Vector Balancing Let X,Y be norms on R^d. Given vectors v_1,...,v_n∈ R^d satisfying ||v_i||_X≤ 1 for all i. We want to find signs ε_i ∈ -1,1 to minimize || ∑_i=1^nε_iv_i ||_Y. Call this the discrepancy of the vectors. Define α_n(X,Y,d) as…
A cyclic (n_3) configuration is a configuration whose Levi graph is a cyclic Haar graph; write H(n,S) for the Haar graph associated with the integer n and connection set S. The configuration is unsplittable when it is neither…
Let N_*(d,t) be the minimal number of elements in a t-design in the d-point simplex, and let binomab denote a binomial coefficient. Simplex-design lower-bound conjecture. The minimal number of elements satisfies N_*(d,t) ≥ binomd+t/2-1t/2.…
Let G be a graph, let J_G be its binomial edge ideal, and let c(G) be the number of maximal cliques of G. Seyed Fakhari–Kiani's conjecture. reg(J_G)≤ c(G)+1. This conjecture is proposed as an upper bound for the regularity of binomial edge…
Let G be an n-vertex graph, and let δ(G) denote its minimum degree. A graph is distance preserving if it has an isometric subgraph of every order from 1 to n. Minimum-degree conjecture. If δ(G)>n/2, then G is distance preserving. Nussbaum…