Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For every integer n≥ 3 and every set of n distinct lines in the real projective plane RP^2 that are not all concurrent, there exist at least three points of RP^2 incident with exactly two of the lines.
Let G be a finite group with |G|≥ 4, and let Γ(G) be its generating graph: the vertices are the non-identity elements, and x and y are adjacent exactly when G=⟨ x,y⟩. Breuer–Guralnick–Kantor's Hamiltonicity conjecture. Γ(G) contains a…
Let P_m be a path graph with m vertices, and let G=compl_n(P_m) be the n-vertex complement of P_m. Let Θ_G denote the associated dynamical system, and call the cycles of this system orbits. Orbit-size conjecture for complements of odd…
For odd N=2n+1, consider the cyclic spin-chain Hamiltonian with parameters λ,ζ and its three translation-invariant zero-energy singlets Ψ_N^a, indexed by a=0,±, with components ψ_μ^a in spin configurations μ. Let ν_1(μ) be the number of…
Let A⊂1,2,…,n have cardinality n-2, with exactly two missing elements a_i,a_j∈1,2,…,n. The two-missing-elements perfect Skolem set conjecture. The set A is a perfect Skolem set if and only if: (1) if n≡0 or 1 modulo n, then a_i≡ a_j modulo…
Let H be a graph. A set of vertices A is complete to a disjoint set B if every vertex of A is adjacent to every vertex of B, and anti-complete if no such edges exist. Strong pivot-minor Erdős–Hajnal conjecture. For every graph H, there…
Let Gha be a vertex transitive graph with a partite presentation P such that Gha=PCay(P), and let Gpa≤Aut_c-loc(Gha) be a transitive group. A cover is a graph map η:Gha→sC_P' compatible with the stated presentation structure. Equivariant…
Conjecture Is it possible to color edges of the complete graph K_n using O(n) colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors? Equivalently: is the star chromatic index of K_n linear in n?
Given an undirected graph G=(V,E), find a maximum cardinality 2-matching containing no cycles of length 4 in polynomial time.
Is there a graph G with vertex set ω_2^2 and chromatic number ℵ_2 such that every subgraph whose vertices have a lesser type has chromatic number ≤ ℵ_0? What if instead we ask for G to have chromatic number ℵ_1?
Brouwer : Is it true that the sum of the k largest Laplacian eigenvalues of a graph with m edges is at most k(k+1)/2+m?
Let F(m) be the frequency sequence and let B_k=2^k,…,2^k+1-1. Dyadic frequency law. The frequencies F(m) satisfy #m∈ B_k:F(m)=r=2^k-r+2 (3≤ r≤ k+1), together with #m∈ B_k:F(m)=k+2=1, #m∈ B_k:F(m)=k+3=1. The law is suggested by numerical…
Let G be a graph, and let Tχ_G^o(q) denote its total oriented chromatic quasisymmetric function. Say that cycles of G are edge-disjoint when no two cycles share an edge. Symmetry conjecture for edge-disjoint cycles. If no two cycles of G…
Let the Thom generating function be Tp_k(z_1,…,z_k)=frac∏_m<l(z_m-z_l) Q_k(z_1… z_k)∏_m+r≤ l≤ k(z_m+z_r-z_l). For coefficient multi-indices i_1,…,i_k, consider neighbouring coefficients obtained by increasing i_l by one and decreasing i_m…
Is there a scale at which the structure of a (real) network “looks like” a manifold? (e.g., Krioukov's result)
Problem Is it true for all n ≥ 0, that every sufficiently large n-connected graph without a K_n minor has a set of n-5 vertices whose deletion results in a planar graph?
Let T(n,k) be defined by the shifted GKP recurrence T(n,k)=[widetildeα(n-1)+widetildeβk+widetildeγ]T(n-1,k)+[widetildeα'(n-1)+widetildeβ'(k-1)+widetildeγ']T(n-1,k-1), and let P_n(x;widetildeμ) be its row-generating polynomials, where…
Let [n]=1,2,…,n denote the vertices of a circulant instance, and let edge length i refer to the corresponding circulant edge-length class, for i=1,…,d. Let t_1,t_2,…,t_d be nonnegative integers, where t_i counts the edges of length i.…
Conjecture Let G be a cubic graph with no bridge. Then there is a coloring of the edges of G using the edges of the Petersen graph so that any three mutually adjacent edges of G map to three mutually adjancent edges in the Petersen graph.
Is it true that if the hypergraph H has no isolated vertices and all of its hyperedges are finite, then H admits a strongly minimal edge cover?