Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For integers n and k with k≥ 1 and n≥ 2k+1, let the Kneser graph K(n,k) be the graph whose vertices are the k-element subsets of [n]:=1,2,…,n, with an edge between two vertices exactly when the corresponding sets are disjoint. Kneser graph…
Steinerberger introduced the Buffon discrepancy problem, asking how accurately a one-dimensional set of length L in a convex body Ω can match the Crofton-predicted line-intersection counts, and proved an O(L^1/3) upper bound via a…
Let G be a d-regular graph. For a graph H, let M_H(λ)=∑_k m_k(H)λ^k be its matching partition function, where m_k(H) is the number of matchings of size k, and let v(H) denote its number of vertices. Let K_d+1 be the complete graph on d+1…
The type C_n cluster configuration space M_C_n is obtained by folding from M_0,2(n-1)-3. Its dihedral coordinates are indexed by pairs of chords and centrally symmetric chords, and its extended u-relations are obtained from those of…
Let a,b be positive integers such that b/2a>1 is an integer. In the (a:b) mindegree-1 Maker-PhantomBreaker game on E(K_n), Maker seeks to claim at least one edge incident with every vertex, while PhantomBreaker claims edges according to…
Let T_k,n denote the Graßmann-Tamari poset on the relevant Graßmannian tableaux. The usual Tamari order is recovered when k=2. Graßmann-Tamari lattice conjecture. For general k, the Graßmann-Tamari poset T_k,n is a lattice. The conjecture…
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Prove that R(Q_n) ≪ 2^n.
Conjecture 6. 2 6. (Shen [32]) Let G be a digraph with n vertices and minimum outdegree at least one. If δ+ G (v) + δ+ G (u) ≥ 2r for every edge (u, v ) in G, then the girth g of G is at most dn/r e.Note: This was proved by Shen for r = 2…
Let G be a graph. A connected 2,4-factor is a connected spanning subgraph of G in which every vertex has degree either 2 or 4. Connected 2,4-factor conjecture. Every 2-tough graph of order at least three admits a connected 2,4-factor. This…
A finite set X⊂R^d is Ramsey if, for every k, there exists an integer n such that every k-colouring of R^n contains a monochromatic isometric copy of X. A finite set is transitive if a group acts transitively on it; a set is isometric to a…
Given a Kahler class Omega on M, does it contain an extremal Kahler metric, and if so is that representative unique?
Let two groves be strictly informative if each satisfies the strict informativeness criterion for determining supertrees. Let the groves be collections of taxon sets, with intersection and union taken as collections of taxon sets. Strictly…
Let M be a matroid of rank n whose ground set S can be partitioned into n disjoint bases B_1,…,B_n. Is it true that B_1,…,B_n always have n disjoint transversals that are bases of M?
Fix a positive integer m for which the equation m^2 + m_1^2 + m_2^2 = 3 mm_1m_2 has a solution in positive integers (m_1,m_2) with 0<m_1≤ m_2≤ m. Then such a pair (m_1,m_2) is unique.
What is the complexity of the union of ``fat'' objects in R^3?
Let cmathcalF be an r-wise fractional L-intersecting family, where L=a/b. The family is r-wise fractional L-intersecting if every r distinct members have pairwise fractional intersections in L. Linear bound conjecture. Then |F| = O((r-1)n…
Let R(k,l) be the Ramsey number, so the minimal n such that every graph on at least n vertices contains either a K_k or an independent set on l vertices. Prove, for fixed k≥ 3, that lim_l→ ∞R(k,l+1)/R(k,l)=1.
Let a(n) be the integer sequence from Theorem, and define its binary reduction by β(n)=a(n)bmod 2. A binary sequence is normal if every finite binary string of length ℓ≥ 1 occurs in it with limiting frequency 2^-ℓ. Normality conjecture.…
Let G be a d-regular graph with n vertices, where d≥ 2. Its irregularity strength s(G) is the least positive integer k for which there is a weighting ω:E(G)→1,2,…,k such that the weighted degrees σ_ω(v)=∑_u∈ N_G(v)ω(uv) are distinct for…
Let G be a connected graph on n vertices. Write R for the polynomial ring associated with G, J(G) for its cover ideal, reg(R/J(G)) for the Castelnuovo–Mumford regularity, and h_R/J(G)(t) for the numerator of the Hilbert series of R/J(G).…