Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let B_n(t)=∑_i=0^e(n)a_i,e(n)x^i and define M(n)=maxa_i,e(n): i=1,2,…,e(n). Then the following equality holds: maxM(m): m∈[2^n-1,2^n]=maxC(n,0),C(n-1,1),…,C(n-k,k), where k is equal to n/2 if n is even and (n-1)/2 if n is odd. This…
Show that for any rational α ∈ [1,2) there exists a bipartite graph G such that ex(n;G)asymp n^α.
conjecture. Let us describe the formula in vague terms.1 Consider permutations x, y \in Sn+1 , which we view as permutations of 0, 1, . . . , n. Suppose that x \leq y in Bruhat order. The set of elements {z \in Sn+1 | x(n) = z(n)} has a…
Update Joux's 2002 work by developing a systematic taxonomy of pairing-related computational assumptions.
Problem 1.12 (R. Graham). Let S be a set of homogeneous linear equations which is partition regular, i.e. in any r-coloring of Z there is always a non-trivial monochromatic solution to S. What is the minimum number of monochromatic…
Let I(rm GA(t,k)') be the edge ideal of the complement of the generalized Andrásfai graph rm GA(t,k), and let β_i,i+j(I(rm GA(t,k)')) denote its graded Betti numbers. Betti-diagram shape conjecture. For all t,k≥ 3, β_i,i+j(I(rm GA(t,k)'))≠…
Let p(n) be a polynomial with positive coefficients. p(n)=a(n)+nb(n) uniquely where a(n) and b(n) are palidromic. Do a(n) and b(n) have nonnegative coefficients?
Let C and B be classes of graphs closed under taking induced subgraphs. Suppose that every 2-connected graph in C is either in B or has a proper 2-separator or a proper P_3-separator. Assume that, for some constant a, every graph in B has…
Let (G,z) be a non-trivial flow-critical tame canvas, and let C(G,z) denote its associated degree sequence. If deg(z)≥ 8 and G has a vertex of degree deg(z)-3, then the degree-sequence conjecture says that C(G,z)∈deg(z)-3,5,…
Let G be a simple 3-connected graph with |E(G)| ≥ 13. Detachable-pair classification conjecture. Either G has a pair of edges x,y such that either Gbackslash xbackslash y or G/x/y is a simple 3-connected graph; G is a wheel; G ≅ K_3,k for…
How often is the group of a random elliptic curve over F_q cyclic?
Let G be a connected graph. A graph has the complete identity property if every vertex can serve as the sink and the recurrent identity is the same configuration. If, for every vertex v∈ G, attaching a single tree of size 1 to v results in…
Let G_n,m be the mesh network with parameters n and m, and let b(G_n,m) denote its bondage number. Mesh-network bondage conjecture. For mgeqslant 5, b(G_n,m)leqslant 2. This conjecture extends the paper's determination of the bondage…
Let w be a word, and write w^m for its m-fold concatenation. A subword is most frequent if it maximizes the number of occurrences in w^m. Periodic-structure conjecture. There is a word v such that, for every sufficiently large m, some most…
Let M be a binary n× k matrix with non-negative integer entries, row sums k, and column sums n. Let M⊗ M^T be the matrix associated with the corresponding tensor-product adjacency structure. Weak balls conjecture. The (non-bipartite)…
Let P_n be the path on n vertices, and let ρ_R(P_n) denote its replication number. The notation O(n) means a quantity bounded in absolute value by a constant multiple of n for all sufficiently large n. The quadratic asymptotic conjecture.…
A superpermutation on n symbols is a string containing every permutation of the n symbols as a contiguous substring. Determine the minimum possible length of a superpermutation for every n>5.
Conjecture 3 (Ho` ang). If G is an even-hole-free graph then χ(G) ≤ 2ω(G) − 1. Hayward and Reed proposed the following.
Can we find a minimum k-way cut in a capacitated hypergraph in polynomial time, if k is fixed?
For every fixed positive integer c, is it true that lim_{t→∞} [size-oRam²_c(t)]/[size-Ram²_c(t)] = 0, where the numerator and denominator are the online and ordinary size Ramsey numbers in the coloring-Ramsey setting?