Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Graham: A set of points S is Euclidean Ramsey if, for every k, there exists an N so that every k-coloring of Euclidean N-space contains a monochromatic copy of S. Show that, if S can be embedded in some d-dimensional sphere, then it is…
If A and B are countably infinite groups, does A× B have fixed price 1?
Let D=DASEP(n,p,q) be parameterized by t and u as described above. For a partition λ with S_n(λ)⊆ D, let S_n(λ) denote the set of permutations associated with λ, and let μ,ν∈ S_n(λ) be arbitrary permutations. Write Pr and Pd for the…
Let g(n) be the maximum, over graphs on n vertices, of the number of distinct clique sizes occurring in the graph. Is g(n)=n-log_2 n-log_* n+O(1), where log_* n is the number of iterated logarithms needed to fall below 1?
For 0≤ m≤ k, define χ_m(k;K_n)=max∑_j=1^mχ(G_j)+∑_j=m+1^kω(G_j)| (G_1,…,G_k) is a k-decomposition of K_n. Thus χ_0(k;K_n)=ω(k;K_n) and χ_k(k;K_n)=χ(k;K_n). Mixed decomposition conjecture. Let m and n≥ 1 be non-negative integers. Then…
∀ε>0 ∃ C=C(ε)>0 ∃ n_0 ∀ n≥ n_0 ∀ d≥ Clog^2 n, every n-vertex d-regular (ε,d)-expander contains a Hamilton cycle.
Let Δ_n-1^(d) denote the d-skeleton of the (n-1)-dimensional simplex. A pure d-dimensional shellable complex on n vertices is extendably shellable if every shelling of a subcomplex can be extended to a shelling of the entire complex.…
Let F be a field. For a directed graph G on n vertices, its minrank over F, denoted by minrk_F(G), is the minimum rank over F of a matrix representing G. An alternating odd cycle is a directed graph whose underlying undirected graph is an…
Let P denote the set of all prime numbers. For n≥ 2, let p_i_i=1^n be an originator consisting of prime numbers, and let d_j^k_j≥ 1, for 1≤ k≤ n-1, be the circuit induced by this originator. Here d_j^k denotes the entries obtained by…
Let G be a connected graph of order n. Write δ for the minimum degree of G, let k=2, and let m be defined by m=1 if δ=3 and m=0 if δ≥ 4. The minimum edge condition conjecture. If δ≥ 3 and |E(G)|≥ binomn-m-(3-m)(δ+1)2+(3-m)binomδ+12+4, then…
(Conlon--Fox--Sudakov) Is r_f(H,H) ≤ c_k(d) n for all n-vertex d-degenerate (in the above sense) k-uniform hypergraph H?
There exists c>0 such that the following holds. If H is an n-vertex, 3-uniform hypergraph with at least n^3-c/d edges, then H contains some/every 3-uniform, 3-partite linear hypergraph on d vertices with at least d^2/100 edges.
Let A be a finite Sidon set and A+A=s_1<…<s_t. Is it true that 1/t∑_1≤ i<t(s_i+1-s_i)^2 → ∞ as lvert Arvert→ ∞?
Let G be a graph, and let K_2 denote the complete graph with two vertices. A graph is 1-planar if it has a drawing in the plane in which every edge is crossed by at most one other edge. A cactus is a connected graph in which every edge…
A line grid graph is a graph obtained as the line graph of a grid graph. A graph is 12-representable if there is a word over its vertices in which every pair of distinct vertices occurs alternately exactly twelve times. Let F denote the…
What is known (or can be shown) about the Ehrhart positivity of polytopes related to Birkhoff polytopes (e.g., transportation polytopes)?
Let T be a tree of order n≥ 2. A subtree root is a zero of the subtree polynomial of T. Consider the annulus z∈Ccolon 1/2≤ |z+1/2|≤ 1/2+√[n-1]n-1. Annulus conjecture. The subtree roots of T are contained in this annulus. This is presented…
For every finite block graph G, define L(G)=maxω(G),⌈frac|V(G)|+1α_min(G)+1⌉, where ω(G) is the clique number and α_min(G)=min_v∈ V(G)max|I|: I⊆ V(G) is independent and v∈ I. The conjecture asserts that L(G)≤χ_=(G)≤ L(G)+1, where χ_=(G) is…
Prove that general SVP and SIVP are hard in the worst case to approximate within small polynomial factors.
Let P_n be the path on n vertices, and let overset2uplus~P_n denote its double blow-up, with corresponding vertices (0,u) and (1,u) for each vertex u of P_n. Let n=2^t r-1, where t≥ 2 and r is an odd prime number. If u is a multiple of…