Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a network, and let v≠ w be vertices of G. The paper defines the property that the pair v,w is amicable in G through its associated polynomial interlacing conditions. Amicability conjecture. For every network G and every pair of…
Let α be the middle real root of 401α^3-1744α^2+2240α-768=0. For odd n=2m+1, let L_m^fat and L_m^thin denote the relaxation optima on the fat and thin colour classes, respectively. For even n=2m, let L_m^even denote the relaxation optimum…
Given the Weil polynomial of an abelian-threefold isogeny class over a finite field, determine whether the class contains a Jacobian.
Let G be a graph on n vertices, and let I_f^2(G) be the entropy associated with the exponential weight sequence. A generalized star is the tree structure described in the claim, with a central region and branches; its diameter and number…
For n≥ 2, let [n]=1,…,n be a set of alternatives. For each linear ranking π=(π(1),…,π(n)) of [n], define its deterministic best-worst choice vector v_π∈R^n(n-1), indexed by ordered pairs (i,j) with i,j∈[n] and i≠ j, by (v_π)_ij=1 if π(1)=i…
Let G be a planar graph. Determine conditions for which a zero forcing set S exists. If such a set S exists, determine bounds on the size of the zero forcing set S of G.
Let β_1,…,β_n be p-adic algebraic numbers in the domain of convergence of the p-adic exponential function exp_p. Then the n numbers exp_pβ_1,…, exp_pβ_n are algebraically independent over Q.
Let n be an arbitrary integer and let p be a prime factor of n. Let ω_1=e^2π i/p, define ω_i=ω_1^i for 0≤ i≤ p-1, and set B=1,ω_1,…,ω_p-1^n⊆ C^n. Let K(n,p) be the minimum k for which there exist vectors v_1,…,v_k∈ B such that for every w∈…
\begin{enumerate} \item[(a)] Find 0/1-polytopes with non-unimodal, non-log-concave, etc. h^*-vectors. \item[(b)] Find 0/1-polytopes with non-unimodal, non-log-concave, etc. f-vectors. \item[(c)] Find 0/±1-polytopes with non-unimodal,…
Let Γ⊂[k-1]×[n-k-1] be centrally symmetric and convex. For f∈Θ_k,n, let Γ'(f) denote the associated centrally symmetric convex set, and let c-equivalence be the equivalence relation on such f. Let σ be the cyclic-shift map. Cyclic…
For integers d≥ 2 and p≥ 1, let C_k^(d) be the set of d-Catalan trees with k internal vertices, and let a length-p shuffle class be the class obtained by rearranging the subtrees branching from an ancestral path of length p. Write 1 for…
Determine the worst-case computational complexity of approximate counting and sampling for models such as the ferromagnetic Potts model and the hard-core model on bipartite graphs; in particular, is there a polynomial-time algorithm or an…
Let ind(k,ℓ) denote the limiting maximum proportion of k-vertex subsets inducing exactly ℓ edges. Super-linear edge-statistics conjecture. For all pairs (k,ℓ) satisfying min ℓ, binomk2 - ℓ = ω(k), we have ind(k,ℓ) = o(1). The paper proves…
Let a hull be a graph arising as the hull of a set of transformations under the paper's construction, and let n be its number of vertices. At-most-n-1 generators conjecture. Every hull on n vertices can be generated with at most n-1…
Conjecture Every bridgeless cubic graph has two perfect matchings M_1, M_2 so that M_1 ∩ M_2 does not contain an odd edge-cut.
Let r≥ 3. There exists c_r>r^-r such that, for any ε>0, if n is sufficiently large, the following holds. Any r-uniform hypergraph on n vertices with at least (1+ε)(n/r)^r many edges contains a subgraph on m vertices with at least c_rm^r…
There exists an integer k_0 such that, for every integer k≥ k_0, every graph G of order n satisfying α(G-S)≥ α(G) for every subset S⊆ V(G) with |S|=k and α(G)=lfloorn-k+1/2⌋ is isomorphic to either K_k+1 or K_k+2, where α(G) denotes the…
Let b_k,ℓ be the doubly indexed sequence defined recursively from the coefficients c_k,ℓ by setting b_k,ℓ=0 when k<0 or ℓ<0, and, for k,ℓ≥ 0, using the auxiliary quantities x_k,ℓ=∑_substacki,j≥ 0 i+j≤ kfracb_i,k-i-jb_j,ℓ(i+1)(i+j+2),…
Let t≥ 1 be a positive integer, and let Γ=bigoplus_i=1^tΓ_i, where each Γ_i is a group. A bigoplus_i=1^tΓ_i-labeled graph is a graph whose edges are labeled by this direct sum, and a cycle is (Γ_1,…,Γ_t)-non-zero when it is non-zero in…
Let K(v_i) mathchoice includegraphics[height=2ex]Bridge includegraphics[height=2ex]Bridge includegraphics[height=2ex]Bridge includegraphics[height=2ex]Bridge C(v_j) be a bridge sum of a complete graph on n vertices and a cycle graph on ν…