Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Problem 3.7 (Brought by B. Green and T. Tao). Take a finite subset of the squares of integers, |A| = N. What lower bound can you get on A + A? One can get better than cN via Freiman's theorem. B. Green comments: I am not sure who posed…
Can we find a minimum k-way cut in a capacitated hypergraph in polynomial time, if k is fixed?
For n≥ 5, let C^n_1,2 be the circulant graph obtained from the cycle on n vertices by adding the edges joining each vertex to the vertex two steps away, with indices taken modulo n. Let g_G(t) denote Speyer's matroid polynomial. The zigzag…
For an integer p≥ 3, let ex(n,K_r) denote the maximum number of edges in an n-vertex K_r-free graph. For integers n and m, define f_p+1(n,m) to be the minimum, over all n-vertex K_p+1-free graphs G with m edges, of the number of non-edges…
The crossing number cr(G) of G is the minimum number of crossings in all drawings of G in the plane. Conjecture cr(K_m,n) = floorfrac m2 floorfrac m-12 floorfrac n2 floorfrac n-12
Does L_p([0,1]) embed coarsely into \ell_p? Does there exist a free measure-preserving action of a free group on a manifold whose warped cone admits a wall structure? Can one construct a slowly growing box space with bounded successive…
Determine whether the lattice dimension in the stated small-root constructions can be reduced.
Let U be a Cartesian product and let S⊆ U be an ample set. Write Box(S) for the boxes associated with S, and let ||Box(S)|| denote their prism complex. Collapsibility conjecture. The prism complex ||Box(S)|| of each ample set S⊆ U is…
Let G be a k-connected graph, and let C_1 and C_2 be any two longest cycles of G. Scott Smith's conjecture. The cycles C_1 and C_2 intersect in at least k vertices: |V(C_1) ∩ V(C_2)| ≥ k. This conjecture is presented as a potential…
Let F be a proper graph class closed under isomorphism and vertex minors. Is there a polynomial-time algorithm that, given G\in F, computes the size of a maximum clique of G?
Let c_2(G) denote the minimum cardinality of a subgraph complementation system for a graph G, and fix a natural number k. A minimal forbidden induced subgraph for the property c_2(G)≤ k is a graph F such that c_2(F)>k but every proper…
Let k≥ 2 and A_k⊆ [0,1] be the set of α such that there exists some β(α)>α with the property that, if G_1,G_2,… is a sequence of k-uniform hypergraphs with liminf frace(G_n)binomlvert G_nrvertk >α then there exist subgraphs H_n⊆ G_n such…
Suppose that A ⊂ F_3^n is a set of density α. Under what conditions on α is A guaranteed to contain a 3-term progression with nonzero common difference in 0, 1^n?
Let C_10 find x satisfying x^e≡ apmod n under gcd(e,φ(n))=gcd(a,n)=1. Is complete integer factorization randomized polynomial-time reducible to C_10?
For a graph G, let b_2(G) denote its biclique partition number over the field of two elements, and let K_n denote the complete graph on n vertices. Let k be a positive integer. Buchanan–odd-cover conjecture. b_2(K_2k+1)=k+1, and…
Let G be an n-vertex graph, and write δ(G) for its minimum degree. A Hamiltonian cycle is a cycle spanning all vertices of G. The bounded-defect cycle conjecture. If δ(G)≥ 3 and G contains a Hamiltonian cycle, then G contains another cycle…
Let W_2,n denote the set of binary words of length n, and let V_n=U(0,1)∩W_2,n. The density of the binary Ulam set is measured by |V_n|/|W_2,n|=|V_n|/2^n. Density limit conjecture. There exists some 0<r<1 such that…
Analyze gradient flows for the network optimal-transport metrics W_\kappa^2 and their limiting Wasserstein and Fisher--Rao metrics.
Let P⊆R^2 be a finite point set. For a line l, let L(P)∩ l denote the set of points where lines from L(P) intersect l. Assume that no more than |P|^1-δ points of P lie on any line, and let l_1 and l_2 be distinct arbitrary lines. For every…
Let G be a graph of order n≥ 2, and let L(G) and M(G) denote its line graph and middle graph, respectively. The line-middle graph inequality conjecture asserts that γtilde _c(L(G)) ≤ γtilde _c(M(G)). The inequality is supported by the…