Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For G less than or equal to Sym(Omega), determine the smallest vertex- and edge-coloured graph Gamma representing G, where size is measured by |V|+|E|.
Let G be a graph of order n≥ 6k+9 with minimum degree δ≥ 2, and suppose that G contains no induced cycles of lengths in 5,8,…,3k+2. The differential of a set D⊆ V(G) is ∂(D)=|B(D)|-|D|, where B(D) is the set of vertices outside D having a…
Problem 1.10 (R. Graham). Let A ⊆ Z × Z satisfy ∑ (x,y )∈A 1 x2 + y2 = ∞. Conjecture ($1000): A contains the four vertices of a square, i.e. four points of the form (x, y ), (x + a, y ), (x, y + a), and ( x + a, y + a). (More generally, it…
Let G_n and H_n be the numbers of odd and even entries, respectively, among the first n rows of the Pascal rhombus. Klostermeyer et al.'s odd-entry density conjecture. Then lim_n→∞G_n/H_n=0. Thus odd entries become negligible relative to…
For a graph G, let rm iso(G,k) be the maximum number of pairwise disjoint k-clique isolating sets in a partition of V(G), and let rm iso_c(G) be the analogous number for cycle isolating sets. The isolation-number lower-bound conjectures.…
Let λ be a Young diagram. For each box Box∈Z^2_≥ 0, let p_λ,Box=∏_Box'∈ H_λ(Box)q_Box', where H_λ(Box) is the hook at Box with respect to λ. Let Z^spp_λ(q) denote the refined local Donaldson–Thomas partition function associated with λ. The…
A B_3-space is a space Σ equipped with the structures used in the paper, and imm(Σ) and ω(Σ) denote its immunity and associated bound. The cycles of Σ are simply intersecting when they satisfy the paper's simply-intersection condition. The…
Let G be a graph, and let BB(G) be its bunkbed graph with two layers, whose corresponding vertices are denoted x^- and x^+ for x obreak in obreak V(G). Let μ colon E(BB(G)) → [0,1] be a symmetric weight on BB(G), and write P_BB(G),μ(u~ v)…
Let S(m,k) denote the MV assignment with m blocks, each of size k, and let c(S(m,k)) be its number of foldings. Equal-block asymptotic conjecture. For any fixed m and sufficiently large k, c(S(m,k))~ frace^m√2π m k^m. The conjecture gives…
Conjecture 6. 2 8. (Devos) For any digraph G with no directed cycles of length at most three, there is a probability distribution p on V (G) such that at every vertex v, p(N +(v)) ≥ p(N −(v)) and p(N − 2 (v)) ≥ p(N −(v)), where p(S):= ∑…
The projective-plane Hanani--Tutte statement says that every drawing of a graph not embeddable in the projective plane contains two non-adjacent edges crossing an odd number of times. Does the analogous statement hold for drawings on any…
Let C be a set, let a be a transitive n× n matrix with entries in C, and let r=r^(c)_c∈ C⊂ g⊗g be a solution of the transitive classical Yang–Baxter equation. Write r^(a) for the corresponding element constructed from a and r.…
Let T⊂X^D_K be a subset, and let O⊂T be an D-dimensional orthotope with 2^D elements. Write S(O) for the sum of the elements of O, and let Ψ be the constant associated with the ambient set. Orthotope sum conjecture. For every orthotope…
Let q range over prime powers, and let an irregular orthomorphism be an orthomorphism whose translate T_g[θ](x)=θ(x+g)-θ(g) is non-cyclotomic for every g∈F_q. Irregularity conjecture. Asymptotically almost all orthomorphisms are irregular.…
Let T be a tree, let P_2 and P_3 denote the paths on two and three vertices, and say that T has adjacency perfect state transfer if its adjacency-matrix continuous-time quantum walk transfers a state between two vertices with fidelity…
Conjecture Let F be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists x such that x is an element of at least half the members of F.
Let Γ be a connected t-valenced graph, meaning that it has t distinct valencies, with two main and two plain eigenvalues. Valency conjecture. There exists a positive integer C such that if t≥ C, then Γ is a strong graph. This conjecture is…
Conjecture Any oriented graph has a vertex whose outdegree is at most its second outdegree.
Let G be a bridgeless graph, and let Φ^∞_2(G) denote its two-dimensional flow number for the Chebyshev norm. Two-dimensional Chebyshev flow-number conjecture. For every bridgeless graph G, Φ^∞_2(G)≤frac52. The conjecture is presented as…
Seymour: "Seymour's Second Neighborhood Conjecture" Any oriented graph has a vertex whose outdegree is at most its second outdegree (vertices at directed distance 2). See this.