Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Find algebraic interpretation (e.g. Coxeter etc.) of s-lecture hall partitions.
Let λ, μ, and tildeμ be number partitions. For number partitions λ>μ, the inclusion i(μ,λ):δ_μ→δ_λ induces a homomorphism i(μ,λ)_*:widetilde H_*(δ_ Res μ)→widetilde H_*(δ_ Res λ). Noncanonicity conjecture. There exist number partitions λ,…
There is a positive function f(h,d,k) such that every graph G with h(G)>h>0 and maximum degree less than d has h(G_k)>f(h,d,k) for each k-net graph G_k. Is inf_k f(1,10,k)>0? In particular, what is the behavior of this bound for k-nets in…
Let r≥ 3. For an r-uniform hypergraph G let τ(G) denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in G. Determine the best possible t such that, if G is an…
Let F⊆ C be a closed infinite set, and let μ(F) be the infimum of lvert z: lvert f(z)rvert < 1rvert, as f ranges over all polynomials of the shape ∏ (z-z_i) with z_i∈ F. Is μ(F) determined by the transfinite diameter of F? In particular,…
Kislitsyn: "1/3 - 2/3 Conjecture" For every poset that is not a chain, there is some pair of elements x and y so that x appears above y in a random linear extension of the poset at least 1/3 of the time and at most 2/3 of the time. See…
Problem Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree r > 2?
Let G be a planar graph. A cycle packing is a set of vertex-disjoint cycles in G; let cp(G) denote its maximum size. A feedback vertex set is a set S of vertices such that G-S is a forest; let fvs(G) denote the minimum size of a feedback…
Given an elliptic curve over F_p and points P,Q such that P=nQ for some n, can such an n be found in deterministic polynomial time?
Let G be a simple graph with maximum degree Δ, and let rm la_ℓ(G) denote its local linear arboricity: the minimum number j such that G is covered by linear forests and every vertex belongs to at most j of them. Local linear arboricity…
Let A be an instance of the paper's network-coding problem with r receivers, where each receiver wants r data packets and every pair of receivers wants at most one data packet in common. Perfect network coding solution conjecture. The…
Let us say that two rectangles in the place are independent if both their x- and y-axis projections are disjoint. A set of rectangles is then independent if the rectangles are pairwise independent. Suppose that a collection of…
Conjecture If G has at most k edge-disjoint triangles, then there is a set of 2k edges whose deletion destroys every triangle.
Conjecture For every k≥ 2, there is an integer f(k) so that every strongly f(k)-connected tournament has k edge-disjoint Hamilton cycles.
For a positive integer k, define q(k):=min ∑_i=1^s(ω(2k_i+1)-1), where the minimum is over positive integers k_1,…,k_s with k_1+…+k_s=k and s≥ 1, and set q(0):=0. Here ω(m) denotes the Ramsey number parameter used in the paper. The…
Let a cubic graph be a graph in which every vertex has valence three, and let its complexity be the number of spanning trees. A cubic graph has maximal complexity if its complexity is maximal among cubic graphs of the same order.…
Assume that K=Q and that V(Q) is Zariski dense; is Z a union of connected components of V(R)?
A graph is cyclically 4-edge-connected if it has no cycle-separating edge-cut of fewer than four edges. A cubic graph has the Perfect-Matching-Hamiltonian property (PMH-property) if every perfect matching can be extended to a Hamiltonian…
Open problem: Unrelated graph balancing Nicole Megow Let G = (V, E) be an undirected graph. The report passage is retained verbatim as the relevant context for this extracted problem.
Conjecture If G is a 3-connected graph, every longest cycle in G has a chord.