Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let L_i) and L_j be layers of the directed hypercube, with i<j and r:=j-i. Let (S,T;φ) be a matched pair with S⊆ L_i and T⊆ L_j. Generalized Lehman–Ron conjecture. There are r collections of vertex-disjoint paths between S and T such that…
For positive integers n and nonnegative integers d, let G_n(d) be the graph whose vertices are the monomials of degree d in n variables, with two monomials adjacent exactly when their least common multiple has degree d+1. Let a_n(d) denote…
Extract useful information from incorrect guesses in factoring attacks based on partially known bits.
For every plane near-triangulation G whose outer face is bounded by a 5-cycle, n_G^\star is a nonnegative linear combination of n_{G_1},\ldots,n_{G_{11}}; computational evidence verifies this for at most 26 faces.
For an integer t≥ 1 and integers m_1,m_2,…,m_t≥ 3, let F=C_m_1+C_m_2+…+C_m_t denote the vertex-disjoint union of cycles of lengths m_1,…,m_t, a 2-regular graph on n=m_1+m_2+…+m_t vertices. Write OP(m_1,m_2,…,m_t) for the following…
Given an ordered pair (λ,μ) of partitions with the same number of parts, define λ^*_k=λ_k-k+#ℓ| μ_ℓ-ℓ≥λ_k-k, and μ^*_ℓ=μ_ℓ-ℓ+1+#k| λ_k-k>μ_ℓ-ℓ. For any partition ν, the starred-transformation conjecture. c_ λ μ^ ν≤ c_ λ^* μ^*^ ν. This is a…
For each integer n≥ 0, determine whether there exists a bijection A:0,1^n→1,…,2^n such that, for every pair of distinct coordinates i,j∈1,…,n and every choice of the remaining coordinates, the face sum…
Let G be a graph. A broadcast f has positive-support vertices V_f^+=v∈ V(G):f(v)>0 and strength-one vertices V_f^1=v∈ V(G):f(v)=1. Write ir_b(G) for the minimum cost of an irredundant broadcast on G, and γ_b(G) for the minimum cost of a…
What are local separators of large networks? The report passage is retained verbatim as the relevant context for this extracted problem.
Let A be an n × n 0-1 matrix, and suppose that the facets of the polyhedron P=x: A x ≤ 1, x ≤ 1 are coloured by n colours such that a facet with extreme direction -e_i does not get colour i, and every colour appears twice. Can we find in…
Which probability distributions on the set H_k of k-vertex graph isomorphism types can occur as the k-profile of a graph, and which global conclusions about G can be drawn from its distribution pi_k(G)?
Let Z_n denote the cyclic group of order n. A circular Costas sequence is equivalent to an injective map φ:Z_n→Z_n+1 whose difference maps Δ_φ,k:Z_n→Z_n+1, i↦φ(i+k)-φ(i) are injective for every nonzero k∈Z_n. A Welch sequence is obtained…
A graph is well-balanced oriented when it has an orientation in which, for every pair of vertices, the maximum number of edge-disjoint directed paths from the first vertex to the second equals the maximum number in the reverse direction.…
Galvin: Let f(p;n,k) = C(n,k) p^(k) (1-p)^(n-k). If p is not 0, 1/2, or 1, is it possible for f(p;n,k) = f(p;n,l) and f(p;n,k') = f(p;n,l') for distinct k, k', l, l'? This is connected with the question of which permutations can arise as…
Let G be a connected, infinite, locally finite graph. A 2-connected ball of radius 2 is the subgraph induced by the vertices in such a ball that is 2-connected. For a path uwv with uv∉ E(G), let d_G(u) and d_G(v) denote the degrees of its…
Let G be a connected graph of order n, and let a representation of G mean a graph representation in the sense of the paper. The extremal representation conjecture. The number of representations of a graph of order n is maximized by the…
Does the Pitman-Stanley polytope have real-rooted h^*-polynomial?
Let t≥ 2 be an integer, and let m_1,…,m_t be integers larger than one, exactly k of which are even. For graphs H_1,…,H_t, the star-critical Ramsey number r_*(H_1,…,H_t) is the minimum integer k such that K_N-K_1,N-1-k→(H_1,…,H_t), where…
Given a digraph D=(V,A), two (not necessarily disjoint) subsets S,T⊆ V and a connectivity requirement k, develop a strongly polynomial time combinatorial algorithm for finding a minimum cardinality arc-set whose addition makes D…
Let G be a graph. An edge of G is a Kuratowski edge if it belongs to a subgraph homeomorphic to K_3,3 or K_5. Kuratowski-edge conjecture. If every edge of G is a Kuratowski edge, then G can be made crossing-critical by a suitable…