Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let D be a binary Δ-matroid. A handle slide is the operation that replaces D by D_ab for distinct elements a,b of its ground set, as defined by the feasible-set transformation in the source. Let D_i,j,k,l be the direct sum of D_i,j,k with…
Let d ≥ 1 and let P ⊂ R^d be a convex polytope of dimension d that is centrally symmetric, i.e. P = -P after a suitable translation. For 0 ≤ i ≤ d let f_i(P) denote the number of i-dimensional faces of P, so that f_0(P) is the number of…
Let G be a simple graph of maximum degree Δ on n vertices. An edge Roman dominating function is a function fcolon E(G)→0,1,2 such that every edge assigned 0 is adjacent to an edge assigned 2, and the edge Roman domination number γ'_R(G) is…
Let X be a graph on n vertices with Seidel adjacency matrix S. For 1≤ m≤ n, let D_m be the set of diagonal matrices having exactly m diagonal entries equal to one and the remaining entries equal to zero, set c=1/n-1, and define…
Let G be a simple graph, let v∈ V(G), and let G-v denote the graph obtained by deleting v. Twin-pair conjecture. If γ_ P(G-v)=γ_ P(G) for all v∈ V(G), then G has at least one pair of twin vertices. This is proposed as a stronger variant of…
Let G be a simple graph, let n_G be its number of vertices, and let S^V(G,β) denote its walk entropy at temperature β≥0. The graph G is walk-regular when every vertex is contained in the same number of closed walks of every length. Benzi's…
Let n∈N with n≥ 3, and let G=G_i:i∈[n] be a family of n-vertex graphs with the same vertex set; the graphs in the family may be identical. For a graph G, let σ(G) denote the minimum, over all nonadjacent vertex pairs u,v, of d_G(u)+d_G(v).…
Are there complete stable minimal hypersurfaces in asymptotically flat manifolds, and are affine functions the only entire minimal graphs over \mathbb{R}^{n-1} in \mathbb{R}^n?
Let G be a graph. In the impartial graph game Snort, let t(G) denote the temperature of the position on G, let deg(G) be the maximum degree of G, and let deg_2(G) be the maximum number of vertices at distance 2 from any vertex of G. The…
Let A267013(d) denote the number of non-primonumerophobic digit patterns of length d, and let A164864(d) denote the total number of available digit patterns of length d. Asymptotic ratio conjecture. As d→fty, the ratio of these sequences…
Let C_n( T_2k+1,B_2k+1 _kgeqslant 1) be the set of connected chord diagrams of size n avoiding all odd top and bottom cycles. The cubic-map enumeration conjecture. The cardinality of this set equals the cardinality of the set of all…
Local trees of triangles Vojt\v{e}ch R"odl A tree of triangles is any graph built recursively by starting with a triangle, and then adding two edges at a time that forms a single new triangle with an existing edge. Known: Given any tree T…
Let G be a graph and let u_k(G) denote the maximum number of edges in a k-matching of G, that is, a set of edges in which every vertex is incident with at most k edges. A graph is nearly bipartite if it contains a vertex w such that G-w is…
Conjecture The union of a 1-degenerate graph (a forest) and a 2-degenerate graph is 5-colourable.
Let FCG_n,c denote the fair cake-cutting graph with parameters n and c. A graph is uniformly most reliable for fixed order n and size m if its reliability polynomial is at least that of every competing graph for every edge-operational…
Let P_m,n be the graph consisting of a path with m vertices on one side of a doubled edge and n vertices on the other. A smooth arithmetical structure on P_m,n is an arithmetical structure whose vertex labels satisfy a_1>a_2>…>a_m and…
Let G be a graph, and let A_d(G) denote its d-dimensional generic affine edge measurement matroid. Uniform affine measurement matroid conjecture. If G has at least binomd+12 edges, then A_d(G) is the uniform matroid of rank binomd+12. The…
Conjecture 6. 3 4. (Thomass´ e) Every digraph D has a path of length δ+ D (g − 1), where g is the girth of D.Note: This is open for g = 3, and implies Caccetta-H¨ aggkvist.
Let (c_1,…,c_l) be a sequence of cluster sizes of a bounded confidence (BC) process. A subsequence is connected when its corresponding clusters are connected in the final configuration. Forbidden-subsequence conjecture. There cannot be a…
Let T_1 and T_2 be trees on n and m vertices, respectively, and fix i∈ V(T_1) and j∈ V(T_2). For a positive integer l, define G_1 as the tree on n+m+l vertices with edge set E(T_1)sqcup E(T_2)sqcup i,m+n+1 , m+n+1,m+n+2 ,…, m+n+l,j , and…