Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let p_1 and p_2 be integer skew-supermodular set functions on ground set S such that maxp_1(X),p_2(X)≤ min|X|,k for every X ⊆ S, and let m_1,m_2,n_1,n_2 be positive integers such that m_1 n_1+m_2 n_2=|S|. Can we decide in polynomial time…
For the stated generalized cluster algebra of type C_n with its generalized exchange polynomials, does every cluster variable correspond to a connected subgraph of the associated generalized snake graph, with analogous descriptions for the…
Conjecture If G is a simple triangle-free graph, then there is a set of at most n^2/25 edges whose deletion destroys every odd cycle.
Let a,b,ℓ,r be positive integers with a≤ b and r/r-1(1-a-1/aℓ)≥ 1. Let K_a,b^ℓ denote the graph considered in the paper. Generalized niceness conjecture. Under these conditions, K_a,b^ℓ is r-nice. The conjecture proposes a further…
Let L_1,R_1,L_2,R_2 be vertex sets of sizes n_1,k_1,n_2,k_2, respectively, satisfying n_1k_2=n_2k_1. Let (L_1,R_1,E_1,u_1,v_1) and (L_2,R_2,E_2,u_2,v_2) be biregular bipartite labeled multigraphs with |E_1|=|E_2|=n_1k_2. For functions with…
Conjecture Define a 2 × n array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where…
Let C_n,m be the class of connected simple graphs on n vertices and m edges, and define its corank by c=m-n+1. A uniformly most reliable graph (UMRG) is a graph in this class whose reliability is at least that of every other member for…
Let C_k denote the kth Catalan number, let Nar_k(t) denote the Narayana polynomial, and define overlineNar_k^(j)(t)=∑_i=0^k-jj+1/k+1binomk+1ibinomk+1i+j+1t^i. Let W_n,k^+(t) and W_n,k^-(t) be the symmetric-decomposition polynomials.…
Let d≥ 0. A subpolytope of a polytope is the convex hull of a subset of its vertices, and a stacked polytope is a polytope obtained by starting with a simplex and successively stacking simplices onto facets. Shephard–Kalai conjecture.…
Let T be a tree, and let MH_k,ℓ(T), EMH_k,ℓ(T), and DMH_k,ℓ(T) denote its magnitude, Eulerian magnitude, and discriminant magnitude homology groups, respectively. Tree discriminant magnitude homology conjecture. For k=3,4,…
No. The following assertion is false: for every real number ε>0 and every real number C, for all sufficiently large natural numbers n, every simple graph G on n vertices such that each degree occurs at most twice and the number of distinct…
Begin with the generating function for unrestricted partitions: (1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)... Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the…
Let P be the set of partitions of a ground set S. We allow two operations on P: (1) splitting a class into two arbitrary classes and (2) joining two classes into one. For two partitions X and Y, let us define the distance d(X,Y) as the…
Let G be a graph, and let its chromatic symmetric homology be the bigraded homology theory associated with G. Consider its component in bidegree (1,0). Chromatic symmetric homology planarity conjecture. The graph G is non-planar if and…
Let p be a prime satisfying 3nmid p-1, let L(p) be the piecewise function defined by L(p)= (p-1)/4 if p≡1pmod 8, (p+1)/4 if p≡3pmod 8, (p+3)/4 if p≡5pmod 8, (p-3)/4 if p≡7pmod 8, and let U_3(p) denote the number of unconnected graphs…
Let G be a connected graph with matching number u(G) and saturation number μ(G) satisfying μ(G)/ν(G)<1. Let M,H,H' satisfy the conditions that M is a maximum matching and that are specified in the source. Leaf-end conjecture. If G is…
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges such that in any 2-colouring of the edges of H there is a monochromatic copy of G. Determine hatR(K_n,n), where K_n,n is the…
Given a graph G with random vertex label, determine the probability that G is radio labeled.
(18) Caroline Klivans: "How can we extend to higher dimensions Merino's result [25] that the generating function of the critical configurations (by degrees) is equal to an evaluation of the Tutte polynomial of G (in particular, is equal to…
Let (G,c) be a colored graph, let T_c,j(G) denote the family of transversal edge sets associated with color j, and let H be a minimally rigid graph. Transversal characterization conjecture. The graph (G,c) is minimally angle-rigid if and…