Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a nontrivial connected graph, and let H be a 3-connected graph. The generalized 3-connectivity of a graph G, denoted by κ_3(G), and its vertex-connectivity, denoted by κ(G), satisfy the following conjecture. Li et al.'s…
Conjecture If A is the adjacency matrix of a d-regular graph, then there is a symmetric signing of A (i.e. replace some +1 entries by -1 ) so that the resulting matrix has all eigenvalues of magnitude at most 2 √d-1.
Let m and n be positive integers. Write K_m+nK_1 for the disjoint union of a complete graph on m vertices and n isolated vertices, and let K_m,n be the complete bipartite graph with parts of sizes m and n. Cameron–Mol's conjecture. If n is…
Let f:0,1^n→0,1 be an n-variable monotone Boolean function, and let L∈ GL_n(F_2) be an invertible linear transformation. Define (Lf)(x)=f(Lx). Keller–Pilpel's conjecture. The total influence of f should satisfy I(f)leqslant I(Lf). The…
Let W_n,k(t) be the polynomials considered in the paper. A finite sequence of real-rooted polynomials is Sturm-unimodal if it increases by interlacing up to one index and then decreases by reverse interlacing. Sturm-unimodality conjecture.…
Let a critical graph be a graph minimal with respect to having no good edge-labeling. Let C_3 be the 3-cycle and let K_2,3 be the complete bipartite graph with parts of sizes 2 and 3. Araújo–Cohen–Giroire–Havet conjecture. There is no…
Conjecture 6. 1 2. (Thomass´ e) Let G be a digraph with no directed cycle of length at most three. Then there is a vertex v ∈ V (G) with δ+(v) at most the number of non-neighbors of v. The following generalization of second neighborhood to…
A graph G is toroidal if it admits an embedding in the torus, i.e. there is a drawing of G on the closed orientable surface of genus 1 in which vertices are distinct points, edges are arcs joining their endpoints, and no two edges meet…
Are the nim-sequences of all finite octal games eventually periodic?
Let G be a finite connected vertex-transitive graph. A graph is Hamilton connected if it has a Hamilton path between any two vertices, and Hamilton laceable if it is bipartite and has a Hamilton path between any two vertices from different…
Let G^H(n) be the Hasse diagram associated with the divisors of n, let V_l(n) denote its vertices at level l, and let W_v(n) denote the node width. Node width at middle level. The node width should equal the number of vertices at the…
Is it easier to count communities than find them? A pair (G, H) of correlated Erdős-Rényi random graphs on n vertices is generated by drawing independently for each of the n(n − 1)/2 couples on vertices a pair of correlated Bernouilli…
For an integer e, let f(e) be the largest integer such that every graph with e edges contains a bipartite subgraph with at least f(e) edges. Is limsup_e→∞(f(e)-(frac e2+frac√8e+1-18))=∞?
For what functions g(N)→ ∞ is it true that lvert A∩ 1,…,Nrvert ≫ fracN^1/2g(N) implies limsup 1_A* 1_A(n)=∞?
Let A⊆ R^d be a set of n points such that all pairwise distances differ by at least 1. Is the diameter of A at least (1+o(1))n^2?
Let T be a tree, and let w(T) and π(T) denote its undirected optical index and path-packing number, respectively. The optical-index ratio conjecture. For any tree T, 1leqw(T)/π(T)≤3/2. The lower bound is immediate from the definitions,…
Let G be a bridgeless graph with m edges. A cycle cover of G is a multiset of cycles from G such that every edge of G belongs to at least one cycle, and its length is the sum of the lengths of its cycles. Short cycle cover conjecture.…
Let x_1, x_2 be two Q-linearly independent complex numbers and y_1, y_2 be also two Q-linearly independent complex numbers. Further let β_ij \ ( i=1,2, j=1,2), γ_1 and γ_2 be six algebraic numbers with γ_1not=0. Assume that the five…
Let F(N) be the size of the largest subset of 1,…,N which does not contain any set of the form n,2n,3n. What is lim_N→ ∞F(N)/N? Is this limit irrational?
Let α be a weak composition, let J_α^(β) be the generating function for diagrams produced from Skyline(α) by the K-Kohnert rule, with each diagram weighted by β^g(D)x^D, where g(D) is the number of g's in D and x^D is its column weight.…