Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Many questions remain open: how does the dimension of the layers grow if rank grows? Can one tell from a graph how many vertices are contained in the in intersection of a component with a given layer? 3. How to navigate the galaxy?…
Let M be a matroid, W a finite group of symmetries of M, and OS^*(M) its Orlik--Solomon algebra as a graded W-representation. Is it true for every i that OS^i(M)\otimes OS^i(M) contains OS^{i-1}(M)\otimes OS^{i+1}(M) as a subrepresentation?
Let α(G) denote the stability number of a graph G, let ω(G) denote its clique number, and call G free of a family of graphs if it contains none of them as an induced subgraph. Consider the family consisting of the six-vertex bipartite…
Let G be a graph and t a positive integer. A t-biclique covering is a collection of complete bipartite graphs covering every edge of G at least once and at most t times; let bp_t(G) be the minimum size of such a covering. Let χ(G) be the…
Let G be a connected subcubic graph, let n(G) denote its number of vertices, and let u_ac(G) denote its acyclic matching number. The acyclic matching conjecture. There is a constant c such that ν_ac(G) ≥ 3n(G)/11-c for every connected…
Let P_m be the path graph on m vertices and C_n the cycle graph on n vertices. For a graph G, let Ind(G) be its independence complex, define Z(G)=1-χ(Ind(G)), and set f_n(t)=∑_m=0^∞ Z(P_m× C_n)t^m. Generating-function denominator…
Let C_n(1,3) be the circulant graph on vertex set Z_n in which vertices at cyclic distances 1 or 3 are adjacent. An identifying code is a dominating vertex set whose closed neighborhoods intersected with the code are distinct for all…
Let HC_n be the set of Hamiltonian cycles on n vertices, and let TSP(n)=convx^v| x∈ HC_n be the symmetric traveling salesperson polytope, where x^v denotes the characteristic vector of the Hamiltonian cycle x. Its skeleton is the graph…
Let G be an n-vertex graph, and let e(G) denote its number of edges. Say that G contains k cycles of consecutive even lengths when it contains such a collection of cycles. Verstraëte's conjecture. If G is an n-vertex graph not containing k…
Let L_ P(A,B) be the universal Lie algebra of classical mechanics generated by A and B, and let T be the vector space spanned by the relevant classical-mechanics trees. Consider the linear map Θ:L_ P(A,B)longrightarrow span( T).…
Let P_E^ℓ N^ℓ be a path of length 2ℓ whose first ℓ edges are red and whose remaining ℓ edges are blue. Let K(a,n) be the graph formed by a clique on a vertices together with n-a isolated vertices, and let I(P_E^ℓ N^ℓ,β) denote the maximum…
Let M be a k-base matroid, meaning that its ground set can be partitioned into k bases, and let P be a partition of E(M) such that |X|≤ k-1 for every X∈P. Rainbow base factorization conjecture. Then M can be factorized into k rainbow…
Show that there is a function f(c), tending to zero as cdownarrow1/2 and to one as c→∞, such that a random graph with n vertices and cn edges contains a path of length at least f(c)n with probability tending to one.
Construct groups in which inversion is infeasible under reasonable cryptographic assumptions.
Let l∈N. An l-card of a graph is an induced subgraph obtained by deleting l vertices, and the corresponding deck is the multiset of all such cards. A graph is l-reconstructible if it is determined by this deck. Kelly's conjecture. For l∈N,…
Let M(n) denote the number of distinct multinomial coefficients arising from partitions of n. Exact-asymptotic-constant conjecture. lim_n→∞log M(n)/√ n=π/3√2. The paper explains that this would follow from the two proposed partition…
Let G be a connected graph on n vertices, where n≥ 3. Write R(G)=∑_uv∈ E(G)(d(u)d(v))^-1/2 for its Randić index and let α'(G) denote its matching number. Define p=lfloorn+4/7⌋, q=⌊6n+2/7⌋. Aouchiche–Hansen–Zheng conjecture. One has…
Can one decide in deterministic polynomial time whether a coprime integer a is a square modulo a composite n?
a) discrepancy of k-permutations For k=3, [NNN'12] showed a lower bound of Ω(log n) where n is the number of elements in the ground set. For general k, we know that the answer lies in [√k+log n,√klog n]. An open question is to clsoe this…
Let G be a graph of order n. A set D⊆ V(G) is a locating-total dominating set if every vertex has a neighbor in D, and any two vertices outside D have distinct neighborhoods within D. Write γ_t^L(G) for the minimum size of such a set. A…