Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a partial cube, and for each isometric cycle of G consider its gated hull. A gated hull is a disk or a full subdivision according to the corresponding classes of cell complexes described in the paper. Gated-hull characterization…
Let G be a finite connected graph with n=|V(G)| and n≥ 2, equipped with its graph metric. For distinct vertices u,v, let the line L_G(u,v) be the metric line determined by u and v, and call a line universal if it contains every vertex of…
Must every permutation of N contain a monotone 4-term arithmetic progression? In other words, given a permutation x of N must there be indices with either i<j<k<l or i>j>k>l such that x_i,x_j,x_k,x_l are an arithmetic progression?
Let m(d,k) denote the maximum possible number of modes of a mixture of k Gaussian distributions in dimension d. Sturmfels's conjecture. For all integers d,k≥ 1, the maximum number of modes is m(d,k)=binomd+k-1d. This conjecture was…
Let [n]=1,2,…,n, and let binom[n]k denote the family of all k-subsets of [n]. A family F⊆binom[n]k is intersecting if F∩ F'≠∅ for all F,F'∈F. Define Δ(F)=max_x∈[n]|F∈F:x∈ F|, varrho(F)=fracΔ(F)|F|. Frankl–Wang's 3/7 conjecture. If…
A strong USP is a collection of strings with the strong uniquely solvable puzzle property, and the strong USP capacity is the largest constant C such that there exist strong USPs of size (C-o(1))^k and width k for infinitely many values of…
Given a crossing supermodular function p:2^V→ Z satisfying p(∅)=p(V)=0, what is the minimum number of edges of an undirected graph G covering p (that is, with the property that d_G(X)≥ p(X) holds for every X⊆ V)?
Let G be a k-edge-connected graph, where k≥ 2, and let H⊂ G be a minimum-edge spanning k-edge-connected subgraph, meaning a spanning k-edge-connected subgraph with minimum e(H). Li–Li edge-connection conjecture.…
Is the exponent e_q(E) of E(F_q) typically close to q?
Let α(n;k_1,…,k_n) denote the generalized monotone-triangle enumeration, and let n≥1. An alternating-sign matrix (ASM) is a square matrix with entries in -1,0,1 whose row and column sums are 1, with nonzero entries alternating in every row…
Let θ be real algebraic number of degree at least 3. Then inequality (2.11) has infinitely many solutions in integers p and q with q>0 if and only if the integral ∫_1^∞ ψ(x) dx diverges.
Let G be a graph, let χ_f(G) denote its fractional chromatic number, and let ρ(G) denote its Hall ratio, the maximum of v(H)/α(H) over all non-null subgraphs H⊆ G. Harris's Hall-ratio conjecture. There exists a constant C such that χ_f(G)≤…
Let G=(V,E) be a simple connected graph with n=|V| vertices and m=|E| edges. Its first and second Zagreb indices are M_1=∑_i∈ Vd_i^2, M_2=∑_(i,j)∈ Ed_i d_j, where d_i is the degree of vertex i. Zagreb index inequality conjecture. For all…
Consider the labeled chip-firing process on a complete binary tree with 2^n-1 nodes, using the labels 1,2,…,2^n-1, and let a terminal configuration be a configuration obtained when no further firing moves are possible. A binary search tree…
Let T(h) denote a complete binary tree with height h, and let PC(T(h)) denote its paired coalition number. Complete binary tree conjecture. PC(T(h))= 5 if h=2, 3 if h is odd, 0 otherwise. This conjecture gives the proposed paired coalition…
Let D_n be the set of link patterns of size n, and let c_απ be the coefficients introduced in the paper. Write link patterns as binary words, with 1_i=(01)^i and 0_ℓ+1=0^ℓ+11^ℓ+1. Suppose π=(01)^i0^ℓ+11^ℓ+1(01)^j=1_i0_ℓ+11_j.…
Fix k and consider k-outerplanar graphs, with the subclass of 3-connected k-outerplanar graphs. A graph property is recognizable if it is recognized by a finite-state tree automaton; it is MSOL-definable or CMSOL-definable if it can be…
Fix n≥1, a diagonal multiset m realizable by an area word of size n, k≥0, r≥1, a scaffold Ξ, and a matrix g=(g_t,δ) recording per-gap, per-diagonal numbers of undecorated active rows. Let Φ^(r)_m,k,Ξ,g(u,v;q) be the corresponding refined…
No. The following assertion is false: every simple graph G whose chromatic cardinal is ℵ_1 contains a subgraph H whose chromatic cardinal is ℵ_1 and which is infinitely connected. Equivalently, for every type of vertices V and every simple…
Let G be an undirected graph, and let H_n^normalfont Cube(G) denote its n-th cubical homology group. Suppose that G contains no 3-cycles and no 4-cycles. Cubical vanishing conjecture. Then H_n^normalfont Cube(G) ≅ (0) for n≥ 2. The…