Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For graphs H_1 and H_2, let c(H_1,H_2) denote their balanced Ramsey multiplicity constant. Algebraicity conjecture. There do not exist graphs H_1 and H_2 such that c(H_1,H_2) is transcendental. The conjecture asserts that every Ramsey…
Let Γ be a graph with axial function α, let H(Γ,α) be its equivariant cohomology ring, and let S( g^*) be the polynomial ring occurring as the ring of constant maps. For a generic ξ∈ g, let σ_p be the number of ascending edges terminating…
Does there exist a zero-density set A of positive integers and a constant c(A) such that every sufficiently large graph with average degree at least 2c(A) contains a cycle whose length lies in A?
Let k≥0. If every finite induced subgraph H of a graph G has an independent set of size at least (|V(H)|-k)/2, must χ(G)≤k+2?
Reduce the number of guesses required by lattice attacks for factoring with partially known bits.
Consider a set S of great circles on a sphere with no three circles meeting at a point. The arrangement graph of S has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this…
2403.10985 introduced the notion of reversible capacity of a graph and showed that it is at most the Shannon capacity. It is conjectured there that the two values are equal. At the finite-length level, it is known to fail: the maximum…
Let 1<q<1+ε and consider the set of numbers of the shape ∑_i∈ Sq^i (for all finite S), ordered by size as 0=x_1<x_2<…. Is it true that, provided ε>0 is sufficiently small, x_k+1-x_k → 0?
Is complete integer factorization randomized polynomial-time reducible to computation of the squarefree part?
Every 4-connected line graph is Hamiltonian.
Let A ⊂ F_2^n. If V is a subspace, write α(V) for the density of A on V. Is there some V of moderately small codimension on which α is stable?
For a positive integer Δ, let U_Δ be the maximal simply connected open subset of C containing 0 that is zero-free for the independence polynomials of all graphs of maximum degree Δ. Let U_Δ,k be the analogous set for k-uniform hypergraphs,…
Let T be a tree, and let γ_g(T) and γ_g'(T) denote the Dominator-start and Staller-start game domination numbers, respectively. A pair (r,s) is realizable by a tree if there is a tree T with (γ_g(T),γ_g'(T))=(r,s). Tree domination-game…
Let G be obtained from a tree by adding some loops. The quantities ML(G) and ML^*(G) denote the minimum light numbers of the sigma-game and lit-only sigma-game on G, respectively. Tree gap conjecture. ML^*(G)-ML(G)∈ 0,1. This conjecture…
Conjecture Every prism over a 3-connected cubic planar graph can be decomposed into two Hamilton cycles.
Let G be a graph and, for k≥ 2, let f_k(G) be the minimum number of vertices that must be deleted to obtain an induced subgraph with at least k vertices attaining its maximum degree, or with fewer than k vertices. Define…
Let G be a connected bipartite graph. Write γ(G) for its domination number and γ_it(G) for its independent transversal domination number, the minimum cardinality of a dominating set meeting every maximum independent set. Hamid's…
For any (planar) triangle T, is there is a 3-coloring of the (infinite) plane with no monochromatic copy of T? We imagine congruent copies of T moved around the plane via rigid motions, and seek a spot where T is monochromatic. T is…
Let P be an n× n partial Latin square of order n, meaning that each cell contains at most one symbol from [n]=1,…,n and each symbol occurs at most once in every row and column. A completion of P is an n× n Latin square agreeing with P in…
Let G be a graph. A subgraph is called locally irregular if adjacent vertices have distinct degrees, and regular if all its vertices have the same degree. Ahadi et al.'s conjecture. Every graph can be partitioned into three subgraphs, each…