Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a minimal k-1,2-factor-critical planar graph, and let t be one of the two values k or k+1. Completeness conjecture. If G is a minimal t-1,2-factor-critical graph, then G is a complete graph. The conjecture is motivated by examples…
Let G be a connected loopless multigraph, let Γ(G) be the corresponding metric graph with unit edge lengths, and let r ≥ 1. For each integer k ≥ 1, let σ_k(G) denote the multigraph obtained by subdividing every edge of G into k parts.…
Construct pairing-friendly hyperelliptic curves suitable for cryptography.
Conjecture If G = (V,E) is a graph, p: E → Z is admissable, and p(e) is even for every e ∈ E(G), then (G,p) has a faithful cover.
Let d be sufficiently large, let G be a connected graph with n vertices and minimum degree at least d, and let T be a uniformly random spanning tree of G. Lee's conjecture. For every tree T, P(T ≅ T) ≤ n^-Ω(1). This conjecture seeks a…
Is it true that such point configurations are never geproci? Subvarieties in Projective Spaces and Their Projections 3107 The reciprocal plane. Another construction from a hyperplane arrangement that gives rise to some interesting…
Let c,k be integers with c≥ 2 and k≥ 1. For an integer r≥ 0, an r-chorded cycle is a cycle with r chords. Gould, Horn and Magnant's conjecture. Every graph G of order at least (c+1)k with minimum degree δ(G)≥ ck contains k vertex-disjoint…
Can Daniel Burgarth's ideas relating the zero forcing number and controllability be extended to PSD matrices?
Let T(n,m) be the sequence studied in the paper, and write its nth row generating function as T(n,x)=∑_m≥ 0T(n,m)x^m=fracH_n(x)(1-x)^n+1. Let M_i,j denote the array specified in the source. Numerator-degree conjecture. For n≥ 2, H_n(x) has…
Is every connected graph on n vertices the union of at most ⌊(n+1)/2⌋ pairwise edge-disjoint paths?
Let T be a tree of order n. The competition-independence number I_s(T), namely the length of the competition-independence game when Sweller moves first and both players play optimally, satisfies I_s(T) ≥ 3/7n. Henning's conjecture. For…
Let K_v be the complete graph on v vertices, where v=2n+1 is odd, and define edge-length by ℓ(x,y)=min(|x-y|,v-|x-y|). A near 1-factor F is a spanning subgraph of K_v with one isolated vertex and a matching on the remaining vertices. Let L…
For integers n>k≥ 1, let KG(n,k) be the graph whose vertices are the k-subsets of [n], with two vertices adjacent exactly when the corresponding sets are disjoint. Two copies are packed into a graph when their edge sets are placed on the…
Open problem: Signings in the subtour polytope Michel Goemans Consider the subtour polytope P of the TSP on G = (V, E) (where we have dropped the degree constraints, without loss of generality, for the question below): P = {x \in RE :…
Why measure it? (What are the real-world applications?)
Witsenhausen’s problem [6] asks for the largest measurable set on a unit sphere such that no two points in the set are orthogonal. More precisely, let S n−1 = {x \in Rn : kxk = 1} be the n-dimensional unit sphere, \omega be the standard…
Call a graph an (ℵ_0,ℵ_1)-graph if it has a bipartition (A,B) so that every vertex in A has degree ℵ_0 and every vertex in B has degree ℵ_1. Problem Characterize the (ℵ_0,ℵ_1)-graphs.
Let G(n,l) be a bipartite circulant graph of the form considered in the paper, and let the generic completion rank be the rank attained by a generic matrix completion. The dimension-count prediction is n- ⌊√n^2-nl⌋. Bipartite circulant…
Let d≥ 6. A bipartite (d,3,-4)-graph is a bipartite graph of degree d, diameter 3, and defect 4. Non-existence conjecture. There is no bipartite (d,3,-4)-graph with d≥ 6. The conjecture extends the paper's proved non-existence result for…
Determine an asymptotic formula for ex(n,C_4), the largest number of edges in an n-vertex graph containing no four-cycle.