Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let P_n be the path graph on n vertices, and let C_P_n denote its optimal 1-variational constant, namely the smallest constant such that Var M_P_nfleqslant C_P_nVar f for every real-valued function f on P_n. Path-graph conjecture. For…
Is there some c>0 such that every measurable A⊆ R^2 of measure ≥ c contains the vertices of a triangle of area 1?
Problem 3.1 (J. Bourgain). Find explicitly a function f: Fp × Fp → Fp such that for every A, B ⊆ Fp with |A|, |B| ∼ p1/2 we have |f (A × B)| ≥ p1/2+ ≤.8 COLLECTED BY ERNIE CROOT AND VSEVOLOD F. LEV
Let Q_n denote the n-dimensional hypercube graph, and let R_m denote the Fibonacci-run graph of parameter m. Hypercube embedding conjecture. The smallest integer m for which Q_n can be embedded into R_m is m=⌈5n-4/2⌉. This is motivated by…
Let g be an affine Kac–Moody algebra, let V be a weight module, and let C be the set of normal quasicones arising as annihilators of vectors in V. Let S denote the set of strategies, where a strategy is a finite composition of root…
Let G(n,δ) be the family of n-vertex graphs with minimum degree at least δ, and let i_t(G) denote the number of independent sets of size t in G. For K_δ,n-δ, one has i_t(K_δ,n-δ)=binomn-δt+binomδt. Galvin's conjecture. Except perhaps for…
Let C:f=0 be a line arrangement in P^2. The invariant ν(C) is a combinatorial invariant of C. Terao-type conjecture. The invariant ν(C) is combinatorially determined. This is presented as a stronger version of H. Terao's conjecture that…
Let G=∏_i=1^n K[u_i,t_i] be a direct product of balanced complete multipartite graphs. The independence number α(G) is the largest size of an independent set, and IR(G) is the maximum size of an irredundant set. Burcroff's conjecture.…
One application is an important special case of a famous open question of Lovász [17] from 1969 concerning the Hamiltonicity of a certain class of well-behaved graphs (see e.g., [10] and its references for more background on the problem).…
Let b_2(n) denote the minimum cardinality of an odd cover of the complete graph on n vertices. Let k≥2 be an integer satisfying k≡2,3pmod4. Buchanan et al.'s conjecture. For such k, b_2(2k)=k+1. This conjecture specifies the remaining…
For α,β∈N with α≤β and β even, fix a set U of β vectors in C^α generically. A Latin Rectangle for U is an α×β matrix whose entries are drawn from U, with no entry occurring more than once in any row or column. For a Latin Rectangle L, let…
Let DB_max(n) denote the de Bruijn sequence of order n defined in the source, and let the discrepancy of a binary sequence be the maximum, over all prefixes, of the absolute difference between the numbers of 1s and 0s. Maximum discrepancy…
Let G be a finite graph and let H be a subgraph of G with at most k components, where k is a natural number. The notions S-Eulerian and semi S-Eulerian mean, respectively, that H has an S-Eulerian circuit or an S-Eulerian trail: a closed…
Does every set of n distinct points in R^2 contain at most n^1+O(1/loglog n) many pairs which are distance 1 apart?
Let a gameboard be a graph on which the Game of Cycles is played, and let its total number of edges be the number of edges in the graph. Assume that no vertex of the gameboard has degree 1. Parity conjecture. Player 1 has a winning…
Let G_1 be the Euclid–Mullin graph associated with the initial node 1, whose edges and loops are defined by the graph construction in the paper. Infinitely many loops conjecture. The graph G_1 contains infinitely many loops. This is…
Tusnady's problem Let d_n be the discrepancy of n points in R^2 wrt all alix-aligned rectangles i.e. the set system comprises of all axis-aligned rectangles in R^2 as sets, maximised over all choices of n points. Tusnady's problem then…
Let ngeqslant 3 be an integer. A graph G is n-hyper-irregular if it is F-irregular for every graph F, not necessarily connected, with order |F|leqslant n and size |E(F)|geqslant 2. Super-strong conjecture on F-irregular graphs. For each…
The numbers π, ζ(3),ζ(5),…,ζ(2n+1),… are algebraically independent over Q.
Understand and control how the shape of a polynomial affects Coppersmith-type small-root algorithms.