Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For positive integers z,d with z≤ d, let K_z,d and Box_z,d be as defined in the source. Basis conjecture. If z≤ d, then K_z,d is a basis of kerBox_z,d. This refines the box-kernel conjecture by asserting linear independence as well as…
Let G be a graph, let X be a specified collection of vertices with outside edges, and let s and f be the vertices considered in the bunk bed conjecture. Let G-X denote the subgraph induced by removing the vertices in X. Strong bunk bed…
For any fixed k≥ 3, R(k,n) ≫ fracn^k-1(log n)^c for some constant c=c(k)>0.
Problem Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n × n grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the…
Let π=(d_1≤…≤ d_n) be a graphical degree sequence, and let G be a realization of π. Say that G contains a 2-factor if it has a spanning 2-regular subgraph, and say that G is hamiltonian if it contains a cycle through all its vertices. The…
For θ∈(0,π), define V_θ=re^it ; r>0, |t|>θ. Compute L(V_θ) in terms of θ.
Conjecture 1. For any g \geq 0, we have χw (Sg ) = 4. In [2] it is proved that for any surface X and ǫ > 0, there exists w > 0 such that every G ֒\to X with ew(G) > w satisfies (5) χc (G) \leq χloc (G) + ǫ. In view of (4) this implies that…
Let X be a finite digital image, viewed as a graph, and let a simple m-loop mean a simple loop in X with m vertices. Homotopy triviality conjecture. If X has no simple m-loop for any m≥ 5, then X is homotopy equivalent to a point. This…
Let G be a graph, let χ(G) be its chromatic number, and write G notsucceq K_s,t when G has no K_s,t minor. Woodall's chromatic conjecture. For every s,t ∈ N, if G is a graph with G notsucceq K_s,t, then χ(G) ≤ s+t-1. This conjecture is a…
Let C be a monotone nowhere dense class of graphs. A p-subdivision is obtained by replacing every edge of a graph by a path of length p+1. Structural conjecture for nowhere dense classes. If C does not have bounded expansion, then there…
Roth with constrained differences For which 0∈ D⊆ F_p is it true that any A⊂ F_p^n avoiding x,x+y,x+2y∈ A with y∈ D^n∖0 has size ≤ C^n for some C < p?
Let an embedded shadow have a block-adjacency graph that is a cactus, meaning that any two cyclic blocks share at most one vertex, and suppose that its cyclic blocks are annular in the sense of the source's necklace definition. The…
Is there a graph with ℵ_2 vertices and chromatic number ℵ_2 such that every subgraph on ℵ_1 vertices has chromatic number ≤ℵ_0? Is there a graph with ℵ_ω+1 vertices and chromatic number ℵ_1 such that every subgraph on ℵ_ω vertices has…
Let J_∞(x) be the infinite linear Jaco graph, and let X be a γ-set, that is, a minimum dominating set. The vertex subscripts in the displayed set are 1,2,7,20,54,…. A sequence is p-graphical for a graph family F when it gives the values of…
Let (X_i(t))_t∈[t_i], for i=1,…,k, be the discrete Markov chains considered in the paper, with total lifetime T:=∑_i=1^k t_i. The total lifetime need not be even. Lifespan-parity conjecture. The inequality in the paper's main result holds…
Let G be a graph, and let L=L be a collection of equal-sized lists, each of size k, indexed by the vertices v eq 0 of G. Choose a color from each vertex's list uniformly and independently, and let p(L) be the probability that the resulting…
Let r(C_p,K_r) denote the Ramsey number for a cycle C_p versus a complete graph K_r, where p, r, and k are positive integers. Nikiforov's asymptotic Ramsey conjecture. For every k there exists r_0=r_0(k) such that, whenever r>r_0 and…
Let A⊂ N be an infinite set for which there exists some ε>0 such that in any subset of A of size n there is a subset of size at least ε n which contains no three-term arithmetic progression. Is it true that A is the union of a finite…
For every simple connected graph G on n vertices, let F(G) denote the number of spanning forests of G and let T(G) denote the number of spanning trees of G. Then F(G)/T(G)≥ F(K_n)/T(K_n), with equality if and only if G≅ K_n.
Let S_n be the permutation group and fix k∈N. Then, #σ∈ S_n: ∃ i, 1≤ i≤ n, σ(i)-i=k=#σ∈ S_n: ∃ i, 1≤ ilneq n, σ(i+1)-σ(i)=k.