Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let BC(2,n) be the stained-glass graph obtained from a 2× n rectangle by the construction described in the paper, and call the bounded regions of this graph cells. Bounded-side conjecture. The cells in BC(2,n) have at most eight sides, and…
Let C and P be graphs, let diam(C) and diam(P) denote their diameters, let r(P) denote the radius of P, and let A_ucg(C,P) be the corresponding appendage number. The uniform central graph appendage conjecture. If diam(C)>1, and diam(P)=4,…
For E_n:y^2=x^3-n^2x, is n a congruent number if and only if L(E_n,1)=0?
Let L be a non-split link, let c(L) denote its crossing number, and let α_3(L) denote its three-page index. Sublinear improvement conjecture. There exists a constant c<3 such that, for every non-split link L, α_3(L)≤ c c(L)+O(1). The…
A triangular hitomezashi pattern is an arrangement of unit-length stitches in the triangular grid such that every lattice point is the endpoint of exactly one east/west stitch, one northeast/southwest stitch, and one northwest/southeast…
Let G be a graph and let e∈ E(G) be an edge. Write G-e for the graph obtained by deleting e, and let Z^+_(1)(G) denote the positive semidefinite 1-leaky forcing number of G. Edge-deletion conjecture. For every graph G and every edge e∈…
How can we start DEI conversations in departments outside the US?
Let G be a graph that is rigid in two-dimensional space. Can we determine in polynomial time the minimum number of edges whose deletion from G results in a graph which is not rigid?
For an n-vertex graph G, let σ(G) be the largest k for which G contains a subdivision of K_k. Is χ(G)≪ n^1/2σ(G)/log n?
- Erdős Problem #724 — Let f(n) be the maximum number of mutually orthogonal Latin squares of order n.
Let f(n) be the maximum number of mutually orthogonal Latin squares of order n. Is it true that f(n) ≫ n^1/2?
Let r be the cardinality of the range of variables, let n× n be the matrix size, and let p_n denote the probability that a matrix of substitutions appears. The preceding bound is p_n≤ fracr^2n-3r^n(n-1)/2. Asymptotic probability…
Given a prime p and a quadratic residue a, can a square root x^2≡ apmod p be found in deterministic polynomial time?
Let P_n be the permutohedron, and let H_0 be its affine hull. For an affine hyperplane H≠ H_0, consider the number of vertices in H∩ P_n. Maximum intersection conjecture. If n is odd, then every hyperplane different from H_0 contains at…
Let F ≠ K_2 be a non-empty graph with vertex set 1,…,m, and let α_1,…,α_m ∈ (0,1) satisfy ∑_i=1^m α_i leqslant 1. Write P(F,α_1,…,α_m) for the property defined by the corresponding average over products of disjoint vertex sets, and let p ∈…
Let k∈N, and let G be a Hamiltonian graph, meaning a graph containing a Hamilton cycle. A 2-factor of G is a spanning 2-regular subgraph, equivalently a union of vertex-disjoint cycles containing every vertex of G.…
Can ω(n), the number of distinct prime factors of n, be computed in deterministic polynomial time?
In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from…
Let G be a graph on n vertices with minimum degree δ. For a graph F, let m(F) denote the maximum number of vertices having the same degree in F. Bounded repeated-degree conjecture. G contains a spanning subgraph H satisfying m(H)≤ n/δ+1+2.…
Let G be an n-vertex graph, let P_n denote the path on n vertices, and let B_p(G) be the random subset of vertices obtained by including each vertex independently with probability p, where 0≤ p≤ 1. Write ZFS(G) for the family of zero…
Given k,m,n with odd n and gcd(km,n)=1, can integers x,y satisfying x^2-ky^2≡ mpmod n be found in deterministic polynomial time?