Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A link-pattern is a noncrossing pairing of the 2n vertices, and A_n(π) denotes the number of fully packed loop states having link-pattern π. For each i=1,2n, let h_i be the operation that reconnects the links incident to vertices i and i+1…
A graph is pseudo 2-factor isomorphic if all of its 2-factors have the same parity of number of cycles. A star product is the cubic graph operation that deletes one degree-3 vertex from each factor and joins the three resulting pairs of…
Let s be a tree degree sequence of length n>2, and let T_s denote the trees with degree sequence s. Write ν_m(T_s) and ν_M(T_s) for the minimum and maximum matching numbers among these trees. Intermediate matching number conjecture. For…
Propp: Show that the inversion permutation, i.e., the one which takes s to 1/s mod p, has longest increasing subsequence of length 2√ p(1+o(1)), i.e., the length it would have if the permutation were truly random.
Let G be a bridgeless connected graph, and let γ(G) denote its vertex-cover number. Define the minimum oriented diameter by oversetlongrightarrowdiam_min(G)=mindiam(overset→G):overset→G is an orientation of G. Minimum oriented diameter…
Let G be a connected graph, and let lcapt(G) denote its localization capture time, namely the minimum number of rounds needed for the minimum number ζ(G) of cops to locate an omniscient robber on G. A family of graphs is well-localizable…
Conjecture Every simple 3-uniform hypergraph on 3n vertices which contains no complete 3-uniform hypergraph on four vertices has at most frac12 n^2(5n-3) hyperedges. Conjecture Every simple 3-uniform hypergraph on 2n vertices which…
Given a symmetric crossing supermodular function p:2^V→ R and positive integers n_1,n_2,…,n_k, does there exist a hypergraph H=(V,E) covering p and having exactly k hyperedges of sizes n_1,n_2,…,n_k?
Let G be a connected graph and let U⊆ V(G). Write Δ^G_U for the nucleus complex associated with G and U, and let widetilde H_k(Δ^G_U;R) denote its reduced homology group in degree k. Homology concentration conjecture. The group widetilde…
Let G be a finite group. The common-zero graph Γ_v(G) has the non-linear irreducible characters of G as vertices, with two characters adjacent when they have a common zero, meaning that both vanish at some element of G. Common-zero…
Let J ⊆ Z^n be a jump system so that either every element of ∑_i=0^n a_i: a ∈ J is even, or every element of it is odd. For every k ∈ N, let c_k be the number of points in J with the sum of the coordinates equal to 2k. Is c_0, …, ultra-log…
Consider a family G_n,L of non-planar connected graphs as above. Let Q_ℓ be the smallest Q>0 for which the transfer matrix widetildesf T_L,ℓ,(ℓ) for the fully symmetric representation (ℓ) of ℓ marked blocks has at least two dominant…
Let G be a forest, let R be the polynomial ring associated to its vertices, let NI(G) denote its neighborhood ideal, and let a_G be the invariant defined in the paper. Regularity conjecture. reg(R/NI(G))=a_G. This conjecture proposes an…
A graph is 3-connected if deleting fewer than three vertices leaves it connected. A chord of a cycle is an edge joining two nonconsecutive vertices of the cycle. Thomassen's chord conjecture. Every longest cycle in a 3-connected graph has…
Suppose that we know that some posinomial f(x) does not vanish whenever it is evaluated when x is in the right half-plane, does that imply that f(x) is log concave on the positive orthant?
However, it is still an open problem to characterize the robustness of neural networks for signal reconstruction for worst-case and for distribution shifts. In this note, we describe open problems on the worst-case robustness and on…
Let O(n) be the set of partitions of n into odd parts and let D(n) be the set of partitions of n into distinct parts. For t≥ 1, let a_t(n) and b_t(n) denote the total numbers of hooks of length t in the partitions in O(n) and D(n),…
How does gonality change if each edge of the graph is subdivided k times?
Let G and H be graphs, and let kgeqslant 0 be a half-integer. A graph H is a k-shallow topological minor of G if a subgraph of G is isomorphic to a subdivision of H in which each edge is replaced by a path with at most 2k internal…
Any 2k-edge-connected (possibly infinite) multigraph admits a k-edge-connected orientation.