Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For a graph G, can one obtain efficiently computable bounds for the chromatic number \chi(G) that improve on the fractional chromatic number, and can such bounds be defined by compact semidefinite programs suitable for practical…
Let A be a set of n positive integers. Does A contain a sum-free set of size at least n/3 + Ω(n), where Ω(n) → ∞ as n → ∞?
Given a palindromic polynomial ∑_i=0^Nc_ix^i, consider the following conjecture: There exists a cone C such that (c_0,c_1,…,c_N)∈ C if and only if the roots of the polynomial are on the unit circle.
Conjecture 6.25. If D is a digraph on n vertices with ∑ v∈V(D) log(1 + 1 δ+ D (v)) ≥ n log(1 + 1 r ), then D has a cycle of length at most dn/r e.Counterexample: Take a transitive tournament of size n − 1, and replace the edge from the…
Can more forbidden minors be found for the class of graphs that admit a knotless embedding in 3-space?
Let D=(V,A) be a digraph with arc weights w i0,1^A. The weight of a dicut is the sum of the weights of its arcs, and the minimum dicut weight is the smallest such weight. The digraph packs k dijoins if it has k dijoins such that no arc e…
Let S_0 be a sequence of 2's and 3's of length n≥ 2, and let Ω(n) denote the maximal tail length achieved by a starting sequence of length n. Suppose that S_0 achieves Ω(n) and that Ω(n)>Ω(n-1). Properties P2, P3 and P4 are the properties…
Let A⊂N be an infinite set such that the triple sums a+b+c are all distinct for a,b,c∈ A (aside from the trivial coincidences). Is it true that liminf fraclvert A∩ 1,…,NrvertN^1/3=0?
For x_1,…,x_n∈ [-1,1] let l_k(x)=frac∏_i eq k(x-x_i)∏_i eq k(x_k-x_i), which are such that l_k(x_k)=1 and l_k(x_i)=0 for i eq k. Let x_1,x_2,…∈ [-1,1] be an infinite sequence, and let L_n(x) = ∑_1≤ k≤ nlvert l_k(x)rvert, where each l_k(x)…
Let B_2,n denote the two-spine book graph with n pages, and let HGP(G) be the proper hat-guessing number of a graph G. Two-spine book graph conjecture. For every n≥4, HGP(B_2,n)=minn+3,11. The preceding results establish the stated values…
Let S be a finite set of points in mathdsR^d, let r be a positive integer, and let G_T[S,r] denote the Tverberg r-partition graph of S. Let Tv(d,r)=(d+1)(r-1)+1. The bounded-excess connectivity conjecture. There exists a constant k(d)…
Let C(G) denote the cycle spectrum of a graph G, and let the circumference of G be the length of its longest cycle. Conjecture on optimal gaps. If k∈N with k≥ 2 and G is a 3-connected cubic planar graph of circumference at least k, then…
any higher sparsity level, this is not an essential restriction in this direction. In all results, we assume that all networks have the commonly used ReLU activation function given by ReLU(x) = max(0, x) and use specific properties of it.…
For all positive integers k and \ell, do there exist functions f(k,\ell) and s(k) such that every graph G with \chi(G)\geq f(k,\ell) has a subgraph G' for which either \chi(G')\geq k and G' has no odd cycle of length at most \ell, or G'…
Let m, n, s and t be positive integers. Let r be a non-negative integer with r+s+t≡ 1pmod2, and let j be an integer. Let B_m,k(q) and B_n,k(q) denote the q-binomial expressions defined earlier in the paper. The q-super Catalan conjecture.…
Let G be a graph with maximum degree Δ≥ 2. Write γ(G) for its domination number and ir(G) for its irredundance number. The asymptotic domination–irredundance conjecture. γ(G)≤ c_Δir(G), where (c_Δ)_Δ≥ 2 is a strictly increasing sequence…
For every connected graph G with n=|V(G)| vertices, the edges of G admit a decomposition into at most lceiln/2⌉ paths.
Let G_d be the radial Moore graph of degree d, and let the status of a vertex be the sum of its distances to all vertices of G_d. Maximal-status conjecture. The radial Moore graph G_d has maximal status for all d ≥ 3. The paper establishes…
Is there a natural relaxation for fort and forcing chain IPs?
Determine the computational hardness of the Pairing Inversion Problem.