Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Every lower bound on the union-closed constant c_0 since Gilmer (2022) — including (3-√5)/2, Sawin–Yu–Cambie's 0.3823455 and Liu's 0.382709 — is certified by the same single-letter inequality: a memoryless protocol coupling two conditional…
A partition is an (s,t)-core if it is simultaneously an s-core and a t-core, and it is self-conjugate if its Ferrers diagram is invariant under conjugation. For coprime positive integers s and t, consider the finite sets of (s,t)-core…
Let T be a tree, and let its size be its number of edges. The Grundy value of T is the Sprague–Grundy value of the game played on T. Parity conjecture for trees. The Grundy value of a tree is zero if and only if its size is even. For…
A pseudo 2-factor isomorphic graph is a graph admitting a 2-factor such that the parity of the number of cycles is the same for all its 2-factors. A graph is cubic if every vertex has degree 3, and it is essentially 4-edge-connected if it…
Let T be a fixed forest, and let f(T) denote an integer depending on T. A graph has linear rank-width at least f(T) when its linear rank-width is at least that integer. Kanté–Kwon conjecture. For every fixed forest T, there is an integer…
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
Let a transparent rectangle visibility graph (TRVG) be a graph admitting a representation by axis-parallel rectangles in which two vertices are adjacent when their rectangles are visible to one another, and call a graph that has no such…
Does it satisfy Kazhdan’s property (T)? Question ii) Does the Grigorchuk group act metrically properly on a median graph? A construction of Schneeberger shows that a proper action does exist, but this specific action is not metrically…
Conjecture Let G be a graph and let T⊆ V(G) such that for any pair u,v∈ T there are 2k edge-disjoint paths from u to v in G. Then G contains k edge-disjoint trees, each of which contains T.
Let D=(V,A) be an acyclic digraph with designated root-nodes r_1,...,r_k∈ V. Let U_1,...,U_k be convex node sets with r_i∈ U_i. Is it true that there exist independent r_i-arborescences F_i with V(F_i)=U_i if and only if there exist openly…
For a graph G let τ(G) denote the minimal number of vertices that include at least one from each maximal clique of G (sometimes called the clique transversal number). Estimate τ(G). In particular, is it true that if G has n vertices then…
Let G be a graph on n vertices, let i(G) be the size of a smallest maximal independent set, and let τ(G) be the transversal number of the family of maximal independent sets. Define β(G)=τ(G)i(G)/n. Beta conjecture. For all graphs G on n…
Let n=p+q>1 be an integer. Let avdash p and bvdash q be integer partitions, and let d=d_1≥ d_2≥…≥ d_n be their union. Let λ=λ_1≥…≥λ_n-1 be a weakly decreasing sequence of positive real numbers. For partitions and sequences of equal total…
Let a triple (d_1,d_2,d_3) be nearly-Ramsey if, for every ε>0, every two-colouring of the circle contains a monochromatic ε-close copy of the triple. Classification conjecture for nearly-Ramsey triples. The triple (d_1,d_2,d_3) is…
Let G be a connected graph of order n. In the Cat and Mouse localisation game, the cat receives only the information specified by the game rules and seeks to determine a vertex within a prescribed distance of the mouse. The…
Kalai : Suppose H is a linear 3-uniform hypergraph, i.e., a subset of the set of all triples of n points with the property that no two edges intersect in more than one point. Further suppose that H is embedded in R^(3) faithfully, i.e.,…
Let H~ G(n,1/2), where G(n,p) is the binomial random graph on n vertices with edge probability p. An even-non-decomposable graph is a graph with an even number of edges that is not even-decomposable. Versteegen's conjecture. P(H is…
An orientation of a hypergraph is a directed hypergraph obtained by choosing a single head-node in each hyperedge. We call a set of orientations of a hypergraph head-disjoint if none of the hyperedges have the same head-node in two of…
For each n∈-3,3,5,8,12,20, prove that no set of four distinct positive integers has property D(n), meaning that every pairwise product plus n is a square. (The page's original exceptional set also contained -1 and -4, which subsequent…
Let m,n,k be integers, and let ⟨ n #2 ⟩_m denote the (n,k)-th entry of the generalized Pascal triangle of parameter m. For k≥ 0, consider entries satisfying n≥ (m-1)k+1. Pascal recurrence conjecture. For n≥ (m-1)k+1 when k≥ 0, ⟨ n #2 ⟩_m=⟨…