Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let B_m^(2) denote the book graph consisting of m triangles sharing a common edge, and let r(B_cn^(2),B_n^(2)) be the smallest integer N such that every red-blue coloring of the edges of the complete graph K_N contains a red copy of…
For a finite undirected graph G, let B be the graphical pointed building set of G, and let Bicl(B) denote the subposet of biclosed ornamentations in O(B). Graphical biclosed ornamentation lattice conjecture. The poset Bicl(B) is a lattice.…
Zarankiewicz’s problem is one of the long-standing open problems in Extremal Graph Theory asking to find the maximum number of edges in a bipartite graph G with parts of size m and n, which does not contain a complete bipartite graph with…
A 1–3 tree is a tree in which every vertex has degree either 1 or 3. For a tree, a leaf-to-leaf path is a path whose endpoints are leaves. Narins–Pokrovskiy–Szabó conjecture. There exist a constant α>0 and a function N=N(n) with N(n)→∞ as…
Let L_2 denote the asymptotic binary subword-entropy constant, and let log_2 be the logarithm to base 2. Strict lower-bound conjecture. L_2 > log_2(3/2). This conjecture is supported by exhaustive computations suggesting that the universal…
Let G be a graph. Its Euclidean dimension, denoted dim(G), is the minimum dimension of a Euclidean space in which G can be represented with adjacent vertices at unit distance. Let χ(G) be the chromatic number of G, the minimum number of…
Hypergraph triangles versus cliques Jacque Verstraete Known: (Kim, Ajtai--Koml'os--Szemer'edi) r(3,t) = Θ(t^2/log t). Let triangle denote the 3-uniform hypergraph with vertex set [6] and edges 123,345,561. Known: Ω(fract^3/2(log t)^3/4) =…
The conjecture asserts that for every matchable nanotube N, its resonance graph R_6(N) is disconnected. Here R_6(N) is the graph whose vertices are the perfect matchings of N, with two perfect matchings M and M' adjacent when there is a…
Let G=(V,E) be a graph and let S be a set of terminal pairs with |S|=2. The multicut dominant textscMultC(G,S) is the dominant associated with multicut incidence vectors. Two-pair description conjecture. It is completely described by x_e≥…
Let G_m,n denote the m-by-n grid graph, and let γ_2(G_m,n) be its integer 2-domination number. The three-row grid conjecture. For every positive integer n, γ_2(G_3,n)=⌊3n/2⌋+1. The conjecture asserts that the upper bound proved in the…
Let a stable configuration be a chip distribution on an undirected binary tree, and say that it satisfies the ballot property if, for each i∈N, the ith smallest chip in the subtree rooted at the left child of a subtree's root has a smaller…
For every graph G with minimum degree cdelta(G)≥ 4, there exists an edge-colouring c:E(G)→1,2,3 such that, for every edge e∈ E(G) and every colour α∈1,2,3, |f∈ E(G):f is adjacent to e and c(f)=α|≤ 1/2|f∈ E(G):f is adjacent to e|.
Let (A_i) be a family of sets with lvert A_irvert=ℵ_0 for all i, such that for any i eq j we have lvert A_i∩ A_jrvert finite and eq 1. Is there a 2-colouring of ∪ A_i such that no A_i is monochromatic?
Call an infinite connected graph G of uniformly bounded degree an infinite expander if there is a constant c>0 such that, for every vertex set S and every finite-radius ball B(r) satisfying |S∩ B(r)|<|B(r)|/2, one has |∂ S∩ B(r)|>c|S∩…
Let G_m,n=P_mBox P_n be the Cartesian product of paths on m,n≥ 2 vertices. Let D_m,n be the orientation of G_m,n with all P_m-layers oriented up except the last P_m-layer, which is oriented down, and all P_n-layers oriented to the left…
Let A be a d-dimensional (0,1)-matrix of order n. For each i, let r_i be the number of ones in the ith hyperplane of A. Multidimensional permanent upper-bound conjecture. The permanent of A satisfies per A ≤ n!^d-2 ∏_i=1^n ⌈…
Let M be a matroid on ground set V, let H=(V,E) be a hypergraph with maximum degree Δ, let c(v) be the cost of node v, and let l(e) ≤ u(e) (e ∈ E) be lower and upper bounds on the hyperedges. Let OPT denote the minimum cost of a basis B of…
Let G be a graph, and let E(G) denote its edge set. A 3-flow on G is a flow whose values lie in a group of order three, and its support is the set of edges on which the flow is nonzero. Large-support 3-flow conjecture. Every…
Let f be a transitive permutation in the symmetric group S_n. For each i=1,…,n-1, set A_i=i,i+1 and define its characteristic number by m_i=minm| (convf)^m(A_i)⊇ A_i, where, for finite A⊆N, convf(A) is the convex hull of f(A). Let m_1'≤…≤…
Let L_1(n) denote the set of vertices of local simplex dimension 1 in the partition graph on partitions of n. The two antenna vertices are the partitions (n) and (1^n). Antenna-vertex conjecture. For every n≥ 4, the only vertices of local…