Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Is R(4,k)≥ frack^3(log k)^O(1) as k→∞?
Let P_n be the path graph on n vertices, let f_n(λ)=∑_k=0^⌊ n/2⌋(-1)^n+kbinomn-kkλ^n-2k be its characteristic polynomial, and let F_0=0, F_1=1, with F_n denoting the Fibonacci numbers. For each n, let R_n be the set of roots of…
Let G be an outerplane graph. For each connected component G_i of G, let B_i,1,…,B_i,b_i be its blocks; let F(B_i,j) denote the bounded faces of B_i,j, let ewdB_i,j denote its extended weak dual, and let v_F be the vertex of this dual…
Let P_n be the path with n vertices, let C(P_n) be the set of endomorphism-induced partitions of V(P_n), and let l_k(n) be defined by l_k(n)=|ρ∈C(P_n):|ρ|=n-k+1|. Michels–Knauer's conjecture. There exists a polynomial f_k∈Q[x] with…
Is complete integer factorization randomized polynomial-time reducible to deciding quadratic residuosity modulo a composite?
For what ε is it true that Pr(e ∈ F and f ∈ F) ≤ (1+ε)Pr(e ∈ F)Pr(f ∈ F) for F a uniformly random spanning forest?
Conjecture Let M,M' be abelian groups and let B ⊆ M and B' ⊆ M' satisfy B=-B and B' = -B'. If there is a homomorphism from Cayley(M,B) to Cayley(M',B'), then every graph with a B-flow has a B'-flow.
Let s(H) denote the minimum degree among all Ramsey H-minimal graphs. Let H be a connected graph on n vertices, and let δ be its minimum degree. Linear upper-bound conjecture. s(H)≤ δ(n-1). The conjecture gives an upper bound for s(H) in…
The supplied source identifies this as a conjecture about finite graphs, with the relevant configuration involving a connected graph G of radius 3 having exactly one diametrical pair, i.e. |u,v⊆ V(G):d_G(u,v)=diam(G)|=1. The conjecture’s…
Let G be a decorated unicyclic graph with cycle length parameter g, let R_G be its curvature operator, and let w^* denote the Perron metric. Write λ_∞:=lim_g→∞λ_max(R_G), and let φ be the golden ratio, so that φ^2=φ+1. Universal…
Let C be a neural code, let Δ(C) be its simplicial complex, and let W=(σ_1,σ_2,σ_3,τ) be a wheel of C. A face of Δ(C) is a max-intersection face if it is the intersection of two or more facets of Δ(C). Bubble-up and missing-rim conjecture.…
Let M=(S,r) be a loopless matroid of rank k whose ground set can be partitioned into k bases. Is it true that no matter how we partition S into sets of size k, the partition will have k-1 disjoint transversals that are bases?
Does Z_q equal M_q for caterpillar graphs?
Let G=(V,E) be a graph with |V(G)|=n. The parameters γ_gr^Z,k(G) and F_k(G) denote the k-Grundy Z-domination number and the k-forcing number, respectively. Equality conjecture. γ_gr^Z,k(G)=n-F_k(G). This conjecture would show that the…
Every graph on n vertices is conjectured to decompose into O(n) cycles and edges; the random-graph and linear-minimum-degree cases are established special cases.
Let Γ be a finitely presented group, and let F be a connected, locally finite Cayley graph of Γ. A graph is r-locally F if every radius-r ball in it is isomorphic to a radius-r ball in F. Benjamini–Georgakopoulos conjecture. There exists…
Let G) be a 2-connected graph on n vertices, and let c(G) denote the length of a longest cycle in G. Woodall's conjecture. If there are at least n/2+k vertices of degree at least k, then c(G)≥ 2k. This conjecture is proved in the paper as…
Determine the largest t=t(k) such that K_k is 2-equivalent to K_k+K_{1,t}, and the largest t=t(k) for which some tree T on t vertices satisfies K_k\sim_2 K_k+T; moreover, for each q\ge2, do there exist two non-isomorphic connected…
Fix a rooted radius-r ball B(o,r) that occurs as every radius-r ball of some finite graph. What is the minimum diameter of a finite graph all of whose radius-r balls are isomorphic to B(o,r)? Bound this diameter in terms of r and the root…
Let G be a twin-free graph of order n without isolated vertices. A locating-dominating set is a dominating set D such that every two distinct vertices outside D have distinct neighborhoods in D; let gamma_L(G) denote the minimum…