Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let vecG be a minimal simply three edge connected, totally cyclic directed graph, and let G be its underlying graph. A twisted graph has the form T=(vecG,G,<,A), where < is a total order on the edges and A is the associated set of…
We assume all matroids are finite. A matroid is modular if every pair of its flats is modular, and hypermodular if every pair of its maximal proper flats is modular. A matroid is a restriction of another matroid when it is obtained by…
Let W(ℓ r,ℓ(1-r)) denote the set of binary words with the indicated numbers of the two letters. Fix r∈(0,1) and n≥ 2, and let i(n,ℓ,r) be the fraction of UT_n(T) isoterms in W(ℓ r,ℓ(1-r)). Isoterm-fraction conjecture. The function i(n,ℓ,r)…
Does every planar graph G satisfy χ_L(G)≤5, and is the bound best possible?
Let Δ_k(n) be the number of the k-diamond broken partition of n, and let D denote the difference operator with respect to n. Finite-difference sign conjecture. For any k≥ 1 and r≥ 1, there exists a positive integer n_k(r) such that, for n≥…
Question Is M_c(G) always rational?
Let H be a finite edge-weighted graph, possibly with loops, whose adjacency matrix A_H is entrywise nonnegative and has at most one positive eigenvalue, counted with multiplicity. Then, for every finite graph G, with d_v=deg_G(v) for each…
Let G be a planar graph, and let its local track-number be the minimum number of tracks in an injective track cover such that every vertex belongs to at most that many tracks. Local track-number conjecture. The local track-number of G is…
Can ω(n), the number of distinct prime factors of n, be computed in deterministic polynomial time?
There are many long-standing open questions about Artin groups. Let Γ be a finite simplicial graph with edges labeled by integers greater than or equal to 2. The Artin group AΓ is the group with presentation hs1 , . . . , sn | si sj si . .…
Does every Eulerian digraph of average degree d have a directed path of length Ω(d)?
Let K_s(n) be the complete s-partite graph with each part of size n. For an ordering of the edges, let ms denote matching sequencibility, and let cms denote cyclic matching sequencibility. Matching sequencibility conjecture. For any…
Conjecture 6. Every connected vertex-transitive graph contains a Hamilton path, and, except for five known examples, a Hamilton cycle. As Cayley graphs are vertex-transitive and none of the five known exceptions in Conjecture 6 are Cayley…
For any t∈ (0,1) let t=∑_k=1^∞ ε_k(t)2^-k (where ε_k(t)∈ 0,1). What is the correct order of magnitude (for almost all t∈(0,1)) for M_n(t)=max_x∈ [-1,1]lvert ∑_k≤ n(-1)^ε_k(t)x^krvert?
How many intersections among an arrangement of pseudosegments in the plane must be added as vertices to allow the pseudosegment arrangment to be extended to a pseudoline arrangement? An arrangement of pseudosegments in the plane is a…
Let G be a graph of order n, and let EP(G)=(p_ij) be its edge-path matrix, where p_ij is the maximum number of pairwise edge-disjoint paths between distinct vertices v_i and v_j, and p_ii=0. Conjecture 1. For every positive integer q, if…
Let G be a graph, let S⊆ V(G), and let k,ℓ be positive integers. An S-cycle is a cycle containing a vertex of S. Long S-cycle Erdős–Pósa conjecture. For every graph G, every subset of vertices S, and every pair of positive integers k,ℓ,…
For a finite set X⊆N and a coloring f:N×N→-1,1, define its imbalance on X by |∑_x<y∈ Xf(x,y)|. Let H(n) be the minimum, over all such colorings of pairs from 1,…,n, of the maximum imbalance over all subsets X⊆1,…,n. Determine the…
Graham: For every non-equilateral triangle T, show that it is possible to color the plane with three colors so that there is no monochromatic (congruent) copy of T.
Problem Consider the set of all topologically inequivalent polyhedra with k edges. Define a form parameter for a polyhedron as β:= v/(k+2) where v is the number of vertices. What is the distribution of β for k → ∞?