Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a finite tree, and let widetildeχ_G^1(q,x) denote the q-chromatic polynomial of G with respect to the all-ones weight vector 1. Leading-coefficient conjecture. The leading coefficient of widetildeχ_G^1(q,x) distinguishes trees.…
Let n,m,k be positive integers such that 1<m<n and k=n-m. Set a=m(n-m+1)/n and suppose that a is not an integer. Let a'=⌈ a⌉, and define U=u_i| i∈[n], V=v_j| j∈[m], E=(u_i,v_(j+α)bmod m)| i∈[n], α∈[a'], j=⌈ im/n⌉. Non-biregular…
Let Γ_n denote the graph considered in the paper, and let an isolated n-PTMC mean an isolated perfect total-multipacking code with parameter n. Existence conjecture. There exists an isolated n-PTMC in Γ_n for every n>2. The supplied…
Can one find a nondeterministic polynomial-time characterization of Seymour graphs?
Let M and N be matroids on the same ground set E. Suppose that E can be covered by k independent sets of M and by ℓ independent sets of N, where 1≤ k≤ℓ. Aharoni–Berger conjecture. Then E can be covered by maxk+1,ℓ common independent sets…
Let A_n-1:=α(n-1;1,2,…,n-1) and let n≥4. Repeated-entry formula conjecture. The identity α(n+1;1,3,4,3,4,5,…,n)=n+4/2A_n-1 should hold. The formula was obtained from computational experiments and is presented as part of a family of…
For the proposed notion of independence of subalgebras B and C contained in an algebra A with state ϕ, defined through an extremal exchangeable state on the infinite free product, is the dependence on the embedding algebra A necessary?
Babai's conjecture: for every nonabelian finite simple group G and every generating set A, the diameter of the Cayley graph Gamma(G,A) satisfies diam(Gamma(G,A)) << (log |G|)^c for an absolute constant c.
Let an athfrakI-contractible graph be a graph reducible to a single vertex by athfrakI-contractible transformations. An expansion is the inverse of a collapse, and a graph is homotopically collapsible when its clique complex can be…
Is it true that if all the hyperedges of a hypergraph H have size at most k for some k∈ N, then H admits a strongly maximal matching?
Let p and q be binary words. They are strongly Wilf-equivalent if B_n,p(k)=B_n,q(k) for all n,k≥ 0, and they are trivially equivalent when they are related by the trivial equivalence defined earlier in the paper. Strong Wilf-equivalence…
Is there a word which is unavoidable over a k letter alphabet, but not a (k-1) letter alphabet, for each integer k > 1? See this.
When does a random graph converge under left-convergence, right-convergence, or the Bollobas--Riordan partition metric; in particular, does G(n,c/n) converge with high probability under each notion?
Open Problem: Find a truly efficient algorithm to decide graph metrizability. Specifics: • All outerplanar graphs are metrizable. • Every 2-connected metrizable graph on 11 or more vertices can be made outerplanar by removing at most one…
What is the maximum number of points in an n × n grid with no three collinear?
For every integer k≥ 2, every graph G with odd girth og(G)≥ 2k+1 and maximum average degree mad(G)<2+1/k admits a (2k+1:k)-coloring; that is, there is an assignment of a k-element subset of 1,…,2k+1 to each vertex of G such that adjacent…
Let G be a 5-connected graph. 5-connected Hippchen conjecture. Every pair of longest paths intersect each other in at least five vertices. The paper proves the analogous statement for 4-connected graphs and proposes this 5-connected…
Let I_n be the number of ones in row m=2^n of the Pascal rhombus, with entries reduced modulo 2. Klostermeyer et al.'s row-count formula conjecture. Then I_n=1/3(2^n+2-(-1)^n). The formula predicts the number of odd entries in power-of-two…
Let G be a connected planar trivalent graph, and let T_G(z) denote its Tait polynomial. Tait polynomial positivity conjecture. If G is bridgeless, then G has a perfect matching M such that ⟨ G:M⟩_2(1)>0. The source explains that this is…
Let G be a nearly bipartite graph, meaning that deleting at most one vertex makes G bipartite. For each integer kgeq 1, let ν_k(G) denote the maximum number of edges in a k-edge-colorable subgraph of G. Lianna's conjecture. For each k≥ 1,…