Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let A⊆R be an infinite set. Must there be a set E⊂ R of positive measure which does not contain any set of the shape aA+b for some a,b∈R and a eq 0?
Let H_m,m be the finite truncated square tiling graph with m≥ 1, let γ_t,r(H_m,m) denote its (t,r) broadcast domination number, and let m and r be positive integers. Single-vertex broadcast conjecture. If m≥ 1 and r≥ 1, then γ_t,r(H_m,m)=1…
Let T_n denote the Takeuchi numbers, let W be the Lambert W-function, and set w=W(n). Let C_T be a positive real constant. Asymptotic expansion conjecture. As n tends to infinity, one has log T_n=e^w(w^2-w+1)+1/2w^2-1/2log(1+w)+log…
In additive combinatorics, the Erdős sumset conjecture is a conjecture which states that if a subset A of the natural numbers N has a positive upper density then there are two infinite subsets B and C of N such that A contains the sumset…
What is the chromatic number of the plane? That is, what is the smallest number of colours required to colour R^2 such that no two points of the same colour are distance 1 apart?
Let d_ℓ(m) be the coefficient of x^ℓ in the Boros-Moll polynomial P_m(x). For fixed m, consider the ratio sequence d_ℓ(m)/d_ℓ-1(m). Ratio-shape conjecture. For m≥ 3, the sequence d_ℓ(m)/d_ℓ-1(m)_1≤ℓ≤⌊ m/2⌋+1 is log-convex, and the sequence…
Let G be a cubic graph with a perfect matching mathcal M such that G / mathcal M is 4-connected. A cycle dominates mathcal M if it contains at least one endpoint of every edge of mathcal M. Dominating-cycle conjecture. The graph G contains…
What is the minimum number of collinear triples in a subset S of the n\times n\times n integer grid when |S|=n^{3-s}? Find a rigid bipartite unit-distance graph.
Conjecture. In particular this machinery was key in their proof of the best current bound for the general version of the problem. Typically a graph will have many Mozhan partitions, and the method involves a scheme called a move sequence…
Let K_6 be the complete graph on six vertices, and let M^3(K_6) denote its third Mycielskian. Write α^∘(G) for the circular altitude of a graph G and χ_c(G) for its circular chromatic number. The preceding bounds give 8leqslant α^∘(…
Let (p_k(x))_k≥ -1 be the sequence of polynomials defined by p_-1(x)=0 and, together with q_-1(x)=1, by p_k+1(x)=2(kx+1)p_k(x)+2x(1-x)p'_k(x)+q_k(x). For n≥ 0, let B_m^(-k) denote the poly-Bernoulli number of index -k. Stephan's…
Let P=(P_i,j)_i,j≥ 0 be the Pascal infinite array, where P_i,j=binomi+ji. For k≥ 1, let P^(k)_i,j denote the determinant of the k× k sub-array of P beginning at position (i,j): P^(k)_i,j=det(P_i+r,j+s)_0≤ r,s<k. Rahimpour's determinantal…
Let g and d be positive integers. A graph is d-regular if every vertex has degree d, its girth is the length of its shortest cycle, and its order is its number of vertices. Folklore conjecture. For every positive integers g and d, there…
Let h(N) be the smallest k such that 1,…,N can be coloured with k colours so that every four-term arithmetic progression must contain at least three distinct colours. Estimate h(N).
Determine, up to isomorphism, all finite simple triangle-free intrinsically knotted graphs G satisfying |E(G)|=22.
Let G be a distance-hereditary graph. A big-μ cograph without universal vertices is a cograph of the form G=(K_1∪ K_t)+H without universal vertices, as described in the preceding characterization. Mutual-visibility conjecture. If G is a…
Let G be a finite simple graph, and for each edge uv∈ E(G) define its imbalance by imb_G(uv)=|d_G(u)-d_G(v)|. Suppose that imb_G(uv)>0 for every uv∈ E(G). Then the multiset M_G= imb_G(e):e∈ E(G) is graphic; that is, there exists a finite…
For the random graph process, determine what happens when the number r of edge-disjoint Hamilton cycles is allowed to grow with n; in particular, determine the threshold for finding r such cycles in terms of the minimum degree and edge…
What is the perfect value of komi (compensation points) in Go?
Let F be a class of graphs, and let ≡_F denote the relation on graphs defined by equality of homomorphism counts from every graph in F. A graph class is minor closed if it contains every minor of each of its graphs, and it is closed under…