Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Conjecture Every simple graph on five or more vertices is switching-reconstructible.
There exists a constant C>0 such that, for every integer n≥ 1 and every simple planar graph G with |V(G)|=n, its scramble number satisfies sn(G)≤ C√n; equivalently, every simple planar graph has scramble number O(√n).
For every pair of distinct elements x_i,x_j of an n-element set, choose p(x_i,x_j) different from both. Call a subset independent if it never contains x_i,x_j, and p(x_i,x_j) together. If g(n) is the minimum, over all such functions p, of…
Let a USCS graph be a graph whose edges all lie on directed cycles. Suppose that the graph supports a given set of rates for asymptotic non-linear index coding, and let e be an edge lying on a single directed cycle, meaning that it…
Let G be a graph. Write underlinef(G) for the minimum fort size of G, let MObs(G;i) denote the marginal observance at step i, and let γ_P(G) denote the power domination number. For a positive integer k, write [k]=1,…,k. Minimum-fort-size…
Euclidean Ramsey sets Ron Graham Let X be a finite set in E^n (n-dimensional Euclidean space). We say that X is Ramsey if for all positive integers r there exists N = N(X,r) such that if one colors the points of E^N with r colors, then…
Let r_n be the Rueppel sequence. Let H_n be the Hankel transform of the sequence 1-r_n, and let h_n be the Hankel transform of the first-difference sequence r_n+1-r_n. Rueppel complement-difference conjecture. Then |h_n|=√|H_n+1|-|H_n|.…
Fix n≥1, k≥0, and r≥1. Let (a,w,S)∈LD(n)^• k, let m be a diagonal multiset of size n, and let Ξ be a scaffold recording the diagonals, labels, and decoration indicators of rows with labels outside r,r+1. Define…
Let n be a positive integer, and let a parking preference be represented by its associated lattice-path diagram, with corners defined as turns of the path. Suppose that there is only one corner above the line y=n-x. One-corner conjecture.…
What is the maximum chromatic number of biplanar graphs?
Let k be a positive integer and let [... ELLIPSIZATION...]rnameCirc[(ℓ^2-1)k,1,ℓ])=2ℓ. ] and field independent minimum rank with universally optimal matrix A(G).
For a heat-conduction network whose pinning potential V is much stronger than its interacting potential U, can one prove that there is sufficient energy transmission along the network?
Let G be a planar graph of order n, and let ψ_3(G) denote its 3-path vertex cover number. Planar 3-path vertex cover conjecture. ψ_3(G) ≤ 2/3n. This conjecture was first mentioned by Brešar et al. in 2011. Equality is attained by, for…
For every maximum degree bound \Delta, does there exist n_0 such that for all n\geq n_0, whenever n-vertex graphs F_1,\ldots,F_t are r_i-regular with r_i\leq\Delta and \sum_{i=1}^t r_i=n-1, the complete graph K_n decomposes into…
Let P_n be the path on n vertices, and let P_nsquare P_n be the Cartesian product of two such paths. Write ρ(G) for the expected percentage of vertices saved when a fire starts at a uniformly random vertex of the finite graph G. The…
Let T(n,k) denote the set of strings of length n over the alphabet of symbols used in the paper. Let γ∈T(m,k) be a string containing a symbol a≤ k-2, and let S⊆T(n,k), for some n≥ m, be the set of strings not containing γ as a cyclic…
Determine whether natural de Rham cup-product pairings can be used to improve zeta-function computations.
Let r,d∈Z_≥ 0, and let G be a connected graph. Write R for the polynomial ring associated with G, J(G) for its cover ideal, reg(R/J(G)) for the Castelnuovo–Mumford regularity, and h_R/J(G)(t) for the numerator of the Hilbert series of…
Let k>3 be an integer, and let g_2k,3(h) denote the minimum number of tiles in a crystallized 2k,3-polyform with h holes. Asymptotic growth conjecture. lim_h→ ∞ fracg_2k,3(h)h = k-1+ √(k-1)^2-2k-2/k-2. This conjecture is motivated by the…
Let P be a poset, let ω∈Rev(P), and let Comp(P,ω) denote the associated companion whose character is χ_Comp(P,ω). Nonvanishing conjecture. If P is a poset and ω∈Rev(P), then χ_Comp(P, ω)≠ 0. The conjecture asks whether every companion…