Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph, with order n(G) and clique number ω(G). Assume n(G)≥ ω(G)+1≥ 4. Ghalavand's conjecture. The local metric dimension of G satisfies dim_l(G)≤ (ω(G)-2/ω(G)-1)n(G). This conjecture relates the local metric dimension to the…
What is the correspondence between the classical Kenyon--Okounkov theory and Lorentz-minimal surfaces, and how does local graph structure lead to conjectural Lorentz-minimality of scaling-limit surfaces?
Let G be a connected graph on n vertices, and let p(G) denote the minimum number of paths in a path decomposition of G. Gallai's conjecture. p(G)≤ n+1/2. This conjecture is a central problem on path decompositions; the paper notes that it…
Let n=2m+1, and let widetildeΔ^n denote the stable configurations reachable from Δ^n by chip-firing. In the odd case, these configurations may be identified with permutations, and an inversion is a pair of entries in the permutation that…
Let an unweighted instance of \texttt{Tron} on a tree be an instance in which all vertex weights equal 1/n, where n is the number of vertices. The unweighted-tree value conjecture. Any unweighted instance of \texttt{Tron} on a tree has…
Let δ>0. If n is sufficiently large and G is a graph on n vertices with no K_5 and at least δ n^2 edges then G contains a set of ≫_δ n vertices containing no triangle.
Let f(n,3,k) be the minimum number of hyperplanes, counted with multiplicity, needed to cover every point of the three-dimensional triangular grid T_3(n) at least k times. The notation O_k(1) denotes a quantity bounded independently of n…
For J⊆[n], let I_n be the relevant coinvariant ideal, let f_J be the associated polynomial, and consider the finite-dimensional graded quotient A_J= C[bf x_n]/(I_n:f_J). A graded algebra has the Hard Lefschetz property if it satisfies…
Does every higher-rank semisimple real lattice have rank gradient zero?
Develop an efficient quantum algorithm for the Smallest Conjugate problem.
Given a set system where the elements are the vertices of the hypercube 0,1^n. Corresponding to each vertex v, there is a set S_v which is generated by picking a random subset of the neighbours of v in the hypercube. What is the…
Let k,n∈ N, let σ∈ Perm(k+1), and let π∈ P_k(n). Write T_σ: R^k+1→ R^k+1 for the linear map whose matrix in the standard basis is (e_σ(1),…,e_σ(k+1)), and let sym_σ(π) be the partition obtained by applying T_σ to the Young tableau of π. A…
Let M be a matroid on ground set S, and suppose that S can be partitioned into k bases. Is it true that there is a cyclic ordering of the elements of S such that any |S|/k consecutive elements in this ordering form a basis?
Conjecture 6. 2 (Hamidoune, 1981) Let D be a digraph with δ+ D ≥ r, δ− D ≥ r, and r ≥ 1.Then there is an edge (x, y ) such that κ(y, x ) ≥ r. Note that a counterexample to the above conjecture for all r ≥ 3 is given by Thomassen in Theorem…
Conjecture: for every n and e, an extremal n-vertex graph with at least e edges maximizing the number of non-triangular edges can be chosen as G(a,b,c), where A is a clique of size a, B and C are independent sets of sizes b and c, B is…
Let G_n be the action graph associated with S(0,n), and let K_ℓ,v,n be the number of paths of length ℓ in G_n that start at a vertex labeled v and end at a vertex labeled n. Super Catalan computation conjecture. The subsequent super…
(9) Lionel Levine: "Is there an efficient way to compute the rank (in the sense of Baker and Norine [7]) of a divisor?" PROBLEMS FROM THE AIM CHIP-FIRING WORKSHOP 5
Let G be a non-bipartite diameter-2-critical graph of order n, and let H_5 be the exceptional graph and C_5^+ the family of expanded 5-cycles described in the source. Strengthened conjecture. If G is not H_5, then G has at most…
Let A(n,k) denote the Eulerian numbers, and let (x_k)_k≥ 0 be a sequence for which log-convexity is defined. Define its Eulerian transformation by z_n=∑_k=0^nA(n,k)x_k. Eulerian transformation conjecture. The Eulerian transformation…
Let n denote the width parameter and let M_blocks be the Markov-chain sampler on building block sequences described in the paper. Cubic mixing-time conjecture. The sampler M_blocks mixes in time O(n^3). The experimental results suggest…