Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a graph. It is claw-free if it has no induced subgraph isomorphic to a claw, and G is 4-connected if deleting fewer than four vertices does not disconnect it. Matthews–Sumner conjecture. Every 4-connected, claw-free graph has a…
Question: What is the minimum number of colors needed above?
Which two-dimensional Artin groups of hyperbolic type are virtually Helly; which Artin groups act properly on CAT(0) cube complexes; are parabolic subgroups stable under intersection; is the complex of proper parabolic two-dimensional…
Let k be the uniformity parameter in the graph proposition referred to in the source. Small-k graph conjecture. The statement of that proposition holds whenever k≥4. The source says that the proposition was proved only for sufficiently…
Let k≥ 2 be a positive integer, let n be sufficiently large, and let G be an n-vertex graph. Write f(G) for the maximum number of distinct degrees in an induced subgraph of G, and let hom(G) denote the maximum size of a homogeneous set in…
Let A be an arrangement consisting of n pseudolines, and let t^A_2 denote its number of double points. Its characteristic polynomial χ(A,t) need not split over R. Simpliciality conjecture. If t^A_2<n/2, then A is simplicial. The conjecture…
Let G be a connected r-regular graph with r>0. Let α(G) denote the independence number of G, and let μ(G) denote its matching number. TxGraffiti's independence–matching conjecture. Then α(G)≤μ(G), and this bound is sharp. This is a…
Let G be a graph, and let I_n(G) denote its complex of independent sets of size at most n. For a simplicial complex X, let C(X) denote its collapsibility number. Let Δ be a nonnegative integer and let n be a positive integer.…
Fix k and let λ∈Par(k). A Dyck partition is a partition equipped with the Dyck-partition structure used in the paper; dp_k(dyck(λ)) is the Dyck partition associated with λ. For a Dyck partition γ, R(γ)=ν^m(γ):0≤ m≤ρ(γ) is its associated…
Let A⊆ N be such that A+A has positive density. Can one always decompose A=A_1sqcup A_2 such that A_1+A_1 and A_2+A_2 both have positive density? Is there a basis A of order 2 such that if A=A_1sqcup A_2 then A_1+A_1 and A_2+A_2 cannot…
For finite graphs H_1 and H_2, let D(H_1,H_2) be the set of graphs that are Ramsey-minimal for one of H_1,H_2 but do not arrow the other. The graphs H_1 and H_2 are Ramsey close if D(H_1,H_2) is finite, and they are Ramsey equivalent if…
Let w' be a word of length k≥ 2 whose letters are all distinct, and let f(w',n,2) denote the maximum number of copies of w' appearing in an n× n grid. Distinct-letter word conjecture. f(w',n,2)~ 3/k-1n^2. The paper notes that the known…
Is there a polynomial time algorithm that is able to find the largest clique of G (with high probability) for ω ≪ √n ? For example, for ω ≈ frac√nlog n ? Is there a polynomial time algorithm that is able to distinguish, with high…
Let k be a positive integer. The equation x^p-y^q=k, where the unknowns x, y, p and q take integer values, all ≥ 2, has only finitely many solutions (x,y,p,q).
Let s(d) denote the function measuring the extremal quantity studied in the paper, where d is the relevant dimension parameter. Asymptotic constant conjecture. The limit lim_d→ ∞s(d)/d=ln 2/1-ln 2. The conjecture asserts that the lower…
Let G and H be graphs on the same vertex set V. For a weight function w:V→N, let (α_∩^w)^*(G,H)=max∑_v∈ Vx(v)w(v)mathrel|vecx∈ IP(G)∩ IP(H) and let γ_∪^w(G,H) denote the weighted collective domination number for the system (G,H). Weighted…
Let G be a minimally rigid graph. Unique NAC-colouring conjecture. We have NAC_#(G)=1 if and only if either G∈G_sc and it has exactly one 3-prism subgraph, or G is a 0-extension graph with exactly one open step. The conjecture has been…
Let a graph be 6-chordal if every cycle of length at least six has a chord, and let graph hyperbolicity be measured in the usual graph metric. Let G_1,G_2,G_3,C_4,C_6,H_i for i=1,…,5 be the ten special graphs depicted or defined in the…
Let G be a graph with minimum degree Greekmath 010E and connectivity Greekmath 0114 , where 1≤Greekmath 0114 ≤Greekmath 010E . Let C be a longest cycle in G, and let overlinep be the order of a longest path in G-C. Jung's reverse…
For 1≤ z≤ d, let M_z,d be the recursively defined set of plain basis vectors, and define B_z,d:=u_n_1… u_n_sboxast u_ℓ_1… u_ℓ_d: lu_ℓ_1… u_ℓ_d∈M_z,d, n_j∈Z_>0, n_1+…+n_s+ℓ_1+…+ℓ_d=z+d, ℓ_1>z-d+δ_n_1=s=1 . Basis conjecture. For 1≤ z≤ d,…