Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph, let c(G) be its cyclomatic number, let L_1(G) be its number of leaves, and let mdim(G) be its mixed metric dimension. A cactus graph is a graph in which all cycles are pairwise edge disjoint; a balanced Theta graph is the…
Let β_1,…,β_n be p-adic algebraic numbers in the domain of convergence of the p-adic exponential function exp_p. Then the n numbers exp_pβ_1,…, exp_pβ_n are algebraically independent over Q.
Let K_n be a complete graph with an even number of vertices, and let the action be the sum of the edge curvatures. A perfect-matching minimum-action conjecture states that the minimum action for K_n is achieved by the perfect-matching…
Let G be a connected directed graph. An antimagic labeling is an edge labeling in which each label is a distinct element of 1,2,…,|E| and the oriented sums at the vertices are pairwise distinct, where an oriented sum is the sum of labels…
For every finite connected graph G=(V,E) with Gnot≅ K_2, there exists a bijection f:E→1,2,…,|E| such that the vertex-sums s_f(v)=∑_e∈ E: v∈ ef(e) are pairwise distinct; that is, s_f(u)≠ s_f(v) for all distinct vertices u,v∈ V.
Can one retain the optimal fragment I\Sigma_{n-2} while making the number of colors constant in the proof-theoretic finite Ramsey theorem construction?
Let (G,σ) be a signed connected simple subcubic graph, where v(G) denotes the number of vertices of G, F(G,σ) denotes its frustration index, and the girth is the length of its shortest cycle. Girth-five frustration index conjecture. If…
For a family of generalized Petersen graphs G(nk,k), let Q_c(k) be the real crossing value and let μ_k+1,ℓ,(ℓ),⋆ denote the indicated dominant eigenvalues. Dominant-eigenvalue pattern conjecture. For k≥4, the dominant eigenvalue on regions…
Let A be a class of graphs that is bridge-addable, meaning that adding an edge between vertices in distinct components preserves membership, and decomposable, meaning that a graph belongs to A if and only if each of its components does.…
An odd hole is an induced cycle of odd length at least five. The odd-hole detection conjecture. It is NP-complete to determine whether a graph contains an odd hole. This conjecture concerns the complexity of odd-hole detection. The source…
Let EP be an edge-to-edge plane graph. A pair of vertices of degree 5 is called adjacent when the two vertices are joined by an edge. Nonadjacency conjecture. Are there any two degree-5 vertices adjacent in EP? No way! Equivalently, no two…
Let f(m,s) be the largest possible size of the smallest assigned muffin piece, where m is the number of muffins and s the number of students. One-third lower-bound conjecture. For all m>s≥ 2, f(m,s)≥ 1/3. The conjecture is solved: the…
Let P be a primitive necklace, let P^* be its dual necklace, and let c_P and c_P^* denote the integers whose existence is asserted by the orbit-size growth conjecture when they exist. Pham's duality conjecture. For any primitive necklace P…
In the SBM and related models, are there regimes in which maximum-likelihood reconstruction does not achieve the optimal threshold?
Let d be a positive integer and let G=(V,E) be a graph on at least d+2 vertices that is minimally globally rigid in R^d. The extremal sparsity conjecture. |E|≤ (d+1)|V|-binomd+22 and the minimum degree of G is at most 2d+1. This conjecture…
Let G be a class of connected graphs closed under contracting edges and subdividing edges. For graphs G and H, an (L,C)-quasi-isometry has multiplicative distortion L and additive distortion C. Edge-contraction and subdivision conjecture.…
Conjecture 1. To prove Theorem 2, we then use a combination of the semi-random method and the absorption method. We use an implementation of the semi-random method in this setting from work of the author with Pokrovskiy and Sudakov [9],…
Let G be a graph on n vertices. A twin-free graph is one with no two distinct vertices having the same open neighborhood, and LD(G) denotes its location-domination number. Location-domination conjecture. If G is a twin-free graph on n…
A triangulated disc is a plane graph whose bounded faces are triangles, and a graph is k-outerplanar if it has a planar embedding whose vertices become empty after repeatedly removing the vertices on the outer face k times. A completely…
Given a graph G, determine if there exists a clique cover whose minimum rank matrices admit a minimum rank matrix of G.