Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let H be any graph. For a positive integer k, say that H is k-Turán-good if the relevant Turán graph T_k-1(n) is extremal for copies of H in every sufficiently large graph subject to the corresponding k-chromatic forbidden-subgraph…
Let C_n be the cycle graph on n vertices, and let ext_D(C_n) denote the minimum number of blanks such that every coloring of the remaining vertices extends to a distinguishing coloring of C_n. Cycle extension conjecture. ext_D(C_n)= 4 if…
Let C_k and P_k denote the graph families of k-th powers of cycles and paths, respectively, and let their B-Z constants be defined. B-Z constant equality conjecture. The B-Z constants of C_k and P_k are equal for all k≥ 1. This conjecture…
Problem 1.13 (R. Graham). Obtain "reasonable" bounds for the Hales-Jewett theo-rem and for the density version of it.
Let G be a doubled 3-regular graph. Perform the YY-Δ transformation on all wyes in all possible ways to obtain a graph G' of smallest size. A chain of 3-cycles is a chain of one or more 3-cycles, each connected by a vertex that is also…
Let m≥ n. A ν-chain is a sequence of integers arising from the successive sizes of a monotone chain of order ideals in the m× n grid, where ν is the associated size-growth function; the antidiagonal chain is the chain obtained by adding…
A graph G is said to be a Seymour graph if for any edge set F that satisfies |C∩ F|≤ |C∖ F| for every circuit C of G, there exist |F| pairwise disjoint cuts each containing exactly one element of F. Can we decide in polynomial time whether…
Let A be an axial algebra of Monster-type with generating axes X, and let Δ(X) be the graph whose vertices are the axes in X, with distinct vertices a,b adjacent exactly when ab≠ 0. A sum decomposition is a decomposition A=∑_i∈ IA_i into…
Let A⊆ 1,… N be a set such that there exists at most one n with more than one solution to n=a+b (with a≤ b∈ A). Estimate the maximal possible size of lvert Arvert - in particular, is it true that lvert Arvert ≤ (1+o(1))frac2√3N^1/2?
Prove that there are sufficiently many prime-order elliptic curves over every finite field F_q.
Let f(n,k) be minimal such that there is a graph with n vertices and f(n,k) edges where every set of k+2 vertices induces a subgraph with maximum degree at least k. Determine f(n,k).
Does there exist a function f:\mathbb{N}\to\mathbb{N} such that, for every finite simple graph G, f(\operatorname{mlt}(G)) is an upper bound for the generic completion rank of G?
For graphs H,H', if they are 2-equivalent must they be 3-equivalent, or can a pair be 100-equivalent but not 101-equivalent; and is it merely coincidental that known pairs which are 3-equivalent but not 2-equivalent include a disconnected…
Let C_4=C_kcolon k≥ 4, and let ι(G,C_4) denote the maximum number of vertex-disjoint members of C_4 in a graph G. Problem 3 asks for the smallest real number c, if it exists, such that there is a finite set E of graphs satisfying ι(G,C_4)≤…
Let G be a snark, and let ω(G) denote its oddness. Snark order-to-oddness ratio conjecture. The order of G satisfies |V(G)|≥ (7+1/2)ω(G). This is a proposed universal lower bound on the order of a snark in terms of its oddness. The source…
For a constant c, the 4-colour Rado number R(c) is the least N such that every colouring of 1,…,N in four colours contains a monochromatic solution to x + y + c = z. Myers (Rutgers thesis, 2015, Conjecture 4.9) and Ahmed, Boza,…
Find, for all large n, a non-trivial pairwise balanced block design A_1,…,A_m⊆ 1,…,n such that, for all t, there are O(n^1/2) many i such that lvert A_irvert=t.
For all integers k≥ ℓ≥ 1, every connected claw-free (k+ℓ+1)-regular graph G of order n satisfies γ_P,k(G)≤ n/k+ℓ+2, where γ_P,k(G) denotes the generalized k-power domination number of G. The bound is sharp.
/Ellis/Kahng: An asymmetric packing code of radius R is a set of binary n-words so that no binary n-word can be reached from more than one of the codewords by changing at most R zeroes to ones. How big is the largest asymmetric covering…
A graph G is toroidal if it can be embedded on the torus, and its basis number bn(G) is the smallest integer k for which G has a cycle-space basis in which every edge belongs to at most k basis elements. Schmeichel's conjecture. Every…