Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let n be a positive integer, let u be a partition of n, and let I be an interval whose endpoints are consecutive entries in the Farey sequence of n. Write λ^T for the transpose partition of λ, and let D_I^1 and D_I^2 denote the quantities…
Let f be a 2-polymatroid function on S that has a matroid representation M=(S × 1,2,r) with the following property: |C∩ (e,1),(e,2)| ≤ 1 for every e ∈ S and every circuit C of M. Is it true that β(f) ≤ β^*(f)+1, i.e. the minimum cover by…
Let A_n:=α(n;1,2,…,n), where α is the generalized monotone-triangle enumeration. Let n≥1, let i range over 0,…,n, and define W_n,i=α(2n+1;i,2,…,n+1,1,2,…,n), i=1,…,3n+2. Block-repetition conjecture. The identities…
Classify graphs with representation number exactly 3.
Let G be a connected graph of order n, and let b(G) denote its burning number. Bonato, Janssen, and Roshanbin's conjecture. b(G)≤ ⌈√n⌉. This conjecture would improve the general bound b(G)≤ 2⌈√n⌉-1 and seeks the sharp order-of-magnitude…
Conjecture Let H be a k-uniform hypergraph. If H is a critical k-forest, then it is a k-tree.
Let G be a connected cubic graph with n vertices. Write the Tutte polynomial as T_G(x,y)=∑_i,jt_i,j(G)x^iy^j. Cubic Tutte relation conjecture. The second derivative of Speyer's polynomial satisfies g_G”(0)=2n t_0,1(G)-4t_0,2(G). This would…
Problem 4.12 (T. Tao). For which real numbers α the set C4 + αC4 has zero Lebesgue measure, where C4 is as in the previous problem?
For a hypergraph H, does m_2^=3 imply that m_3^ is finite? What is the minimum number of partial triangulations of n points in general position in the plane, and is it the Catalan number C_{n-2}=\frac{1}{n-1}\binom{2n-4}{n-2}? The report…
Let f be a psd-stable polynomial in symmetric variables, and let Z^β be a monomial appearing in a psd-stable polynomial. A diagonal monomial is a monomial Z^α appearing in f whose variables are diagonal variables. The distance between…
Does k(1-π(K_k+1^k)) tend to ∞ as k→∞?
Let P_n^k denote a k-path graph of order n, let K_k-1 be the complete graph on k-1 vertices, let P_n-k+1 be the path on n-k+1 vertices, and let ∨ denote the graph join. For a graph G, write A_α(G)=α D(G)+(1-α)A(G) for α∈[0,1], where A(G)…
Let f_2(n) denote the minimum number of arcs in an oriented graph with weak diameter 2 on n vertices, and let x_n be the upper bound constructed in the paper. An oriented clique is an oriented graph in which every pair of distinct vertices…
Let k≥ 2 and let T∈YT(n), where n≥ k^2+2k. Here M_k(T) denotes the collection of k-minors of the standard Young tableau T. Reconstruction conjecture. The collection M_k(T) determines T. The quadratic bound is suggested by the cases checked…
Let M and RW be the colored shuffled-word and reduced-word sets, and let ψ: M→RW be a map whose linear extension makes the diagram in Proposition commute. Let ξ be the operator on words that removes the first letter. Commuting-map…
What polynomial-time computable upper bounds UB(G) for the minimum-bisection objective OPT(G) are valid for every graph and asymptotically tight on random graphs?
Problem 3.17 (N. Katz). Does there exist a finite subset A ⊂ Z, |2A| = k|A|, so that for the function f (n, k ) defined in the previous problem every proper A′ ⊂ A satisfies |nA ′| ≥ f (n, k )|A′|?
Let G(n,1/2) be the Erdős–Rényi random graph on n vertices, with each edge present independently with probability 1/2. An irreducible non-metrizable path system is a path system that is both irreducible and non-metrizable. Asymptotic…
Determine, for any k>r>2, the value of fracex_r(n,K_k^r)binomnr, where ex_r(n,K_k^r) is the largest number of r-edges which can placed on n vertices so that there exists no set of k vertices which is covered by all binomkr possible r-edges.
Let θ∈C^m. There is a positive constant c, depending only on θ and m, with the following property. Let k be an integer with 0≤ k≤ m. For infinitely many integers T≥ 1, there exists an algebraic set Z⊂C^m, defined over Q, of dimension k,…