Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Problem Do 4-colorings of Z_p, for p a large prime, always contain a rainbow AP(4) if each of the color classes is of size of either ⌊ p/4⌋ or ⌈ p/4⌉?
Does there exist a graph where the dominating number equals the eternal dominating number and both are less than the clique covering number?
Conjecture Let G be a 2-connected cubic graph and let S be a 2-regular subgraph such that G-E(S) is connected. Then G has a cycle double cover which contains S (i.e all cycles of S ).
Problem 2.9 (T. Gowers). Suppose A ⊆ Z, |A| = n. Let S = {x + a + b + c: x, x + a, x + b, x + c, x + a + b, x + b + c, x + a + c ∈ A}. If |S| < cn, then can one deduce anything about the structure of A?B. Green comments: The answer to this…
Let a(n) denote the nth term of OEIS A091468. The conjecture is that, for every n≥ 0, a(n)=3 A003239(n)-2.
Let p_α(n) be the continuous extension of the k-colored partition function, with α∈R_≥ 2. Under the assumptions n,ℓ∈N, n>ℓ, and (α,n,ℓ)≠(2,6,4), Heim–Neuhauser conjecture. The Chern–Fu–Tang inequality remains valid after replacing k by α:…
Let G_1 and G_2 be graphs, and for a prime power q=p^s let c_2^(q)(G) denote their c_2 invariants. Schnetz's prime reduction conjecture. If c_2^(p)(G_1)≡ c_2^(p)(G_2)pmod p for every prime p, then c_2^(q)(G_1)≡ c_2^(q)(G_2)pmod q for every…
Let Φ be an irreducible classical root system of rank at least 2, and let Γ_s(Φ) be its small Weyl graph. The diameter of a graph is the maximum distance between two of its vertices. Diameter-three conjecture. The diameter of Γ_s(Φ) is at…
A signed graph (G,Σ) consists of a graph G and a set Σ⊆ E(G) of negative edges. A signed circuit is either a balanced circuit, containing an even number of edges of Σ, or a barbell, consisting of two unbalanced circuits sharing exactly one…
Conjecture Every simple eulerian graph on n vertices can be decomposed into at most 1/2(n-1) cycles.
Let k be an integer with k≥ 4, and let G be a graph. Here P_n denotes the path on n vertices, P_2∪ kP_1 is the disjoint union of a two-vertex path and k isolated vertices, a graph is 1-tough when its toughness is at least 1, and…
Can finite-state deterministic graphical games of perfect information, given explicitly as graphs, be solved in linear time by a comparison-based algorithm?
Let G_n be the partition graph on the partitions associated with the parameter n, and consider its simplicial thick zones, including the tetrahedral and higher-order regions. The front extremes and antennas refer to the frontal extremal…
Is the exponent of matrix multiplication 2? In other words, can two n b n matrices be multiplied in O(n^(2+)^(ľ)) steps? See this.
Let G be a graph, and say that G excludes a graph as an asymptotic minor if there is an integer k such that the graph is not an asymptotic minor of G. Georgakopoulos–Papasoglu's conjecture. If there is an integer k such that a graph G…
Problem 1. Let G be a finite almost quasisimple group, g \in G r Z(G). (A) Find an explicit, and as small as possible, 0 < \gamma = \gamma(g) < 1, such that |χ(g)| \leq \gamma, \forall χ \in Irr(G) with χ(1) > 1. χ(1) (B) Find an explicit,…
Let p(2,n) denote the number of solutions of the multiple permutation problem with parameter m=2 and size n. Asymptotic conjecture. p(2,n)~ n!/2^n. The paper presents this as an additional challenge concerning the asymptotic behavior of…
Define f(N) be the minimal k such that the following holds: if G is an abelian group of size N and A⊆ G is a random set of size k then, with probability ≥ 1/2, all elements of G can be written as ∑_x∈ Sx for some S⊆ A. Is f(N) ≤ log_2…
Schoenberg proved that for every c∈ [0,1] the density of n∈ N : φ(n)<cn exists. Let this density be denoted by f(c). Is it true that there are no x such that f'(x) exists and is positive?
Let S be the abelian loop of odd numbers used in the paper, with binary operation •. Consider quartets (a,b,c,d) of distinct numbers in S satisfying a • b=b • c=c • d=d • a. Four-cycle conjecture. There are infinitely many such quartets.…