Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
As a Q-algebra, Z is the direct sum of Z_p for p≥ 0.
Reduce computational problems on arbitrary lattices to corresponding problems on cyclic or ideal lattices.
Let n≥ 3 and let (d_1,…,d_n) be a sequence of integers satisfying d_1≥…≥ d_n≥ 4, d_1+…+d_n is even, and ∑_i=1^k d_i≤ k(k-1)+∑_i=k+1^nmind_i,k for every k∈[n]. Here a triangular simple graph is a simple graph in which every edge is…
For an integer k at least 2 and a graph G, let n(G) denote the order of G. Define f_k(G) as the minimum cardinality of a set X of vertices of G such that G-X has either k vertices of maximum degree or order less than k. Caro and Yuster's…
Let m≥ 3 be an integer, let V=1,2,…,m-1, and let D^(m,V) denote the generating series for Dyck paths whose peaks avoid the heights in the congruence classes specified by (m,V). Write H(D^(m,V)) for the sequence of Hankel determinants of…
Let G be an n-vertex graph, and let z(G;k) denote the number of zero forcing sets of G having size k. Let P_n be the path on n vertices. Fixed-size zero forcing conjecture. If G is an n-vertex graph, then for all k, z(G;k)≤…
Let G=(V,E) be a connected graph, and let m=|E| be its number of edges. An edge-irregulator of G is a set S⊆ E such that G-S is locally irregular, meaning that every edge of G-S joins vertices of different degrees; write rm I_e(G) for the…
Let M(n) be the number of monotone Boolean functions of n variables, equivalently the number of antichains of subsets of an n-element set. Determine the exact values M(n) for n≥10.
Let G be a simple graph on n vertices, let Bbbk be a field, and set R=Bbbk[x_1,…,x_n,y_1,…,y_n]. For i,j∈ E(G), write f_i,j=x_iy_j-x_jy_i, define the binomial edge ideal J_G=(f_i,j| i,j∈ E(G))⊆ R, and set R_G=R/J_G. A graph is weakly…
Let G=(V,E) be a graph, let θ^(r)(G) be its order-r copositive hierarchy bound, and let S^⊥ denote the vertices adjacent to or equal to a stable set S. For every stable set S⊆ V with |S|=r, the graph G∖ S^⊥ is obtained by deleting S^⊥. The…
If 1, …, N is r-coloured, then for N ≥ N_0(r) there exist integers x, y ≥ 3 such that x+y and xy have the same colour. Find reasonable bounds for N_0(r).
A nowhere-zero r-flow (D(G),φ) on G is an orientation D of G together with a function φ from the edge set of G into the real numbers such that 1 ≤ |φ(e)| ≤ r-1, for all e ∈ E(G), and ∑_e ∈ E^+(v)φ(e) = ∑_e ∈ E^-(v)φ(e), for all v ∈ V(G). A…
Let H(n,3) be the Hamming graph with vertex set Z_3^n, where two vertices are adjacent when they differ in exactly one coordinate. Its Laplacian has eigenvalue 3n corresponding to the index i=n. For an eigenfunction f, let SND(f) denote…
Let k be one of 4, 5, or 6, and let H be a hexagonal line tiling. Consider the k-cut complex of H. Hexagonal line tiling shellability conjecture. For k=4,5, and 6, the k-cut complex of the hexagonal line tiling is shellable. The conjecture…
For positive semidefinite (PSD) zero forcing consider the minimum PSD propagation time pt_+(G):= minpropagation times given a minimum PSD zero forcing set and the maximum PSD propagation time PT_+(G):= maxpropagation times given a minimum…
Let G=G_1∪ G_2, where |V(G_1)∩ V(G_2)|≤ d+1, and let u,v∈ V(G_1)∩ V(G_2). A pair is R_d-linked when it is contained in an R_d-circuit. Jordán and Garamvölgyi's separator conjecture. If u,v is R_d-linked in both G_1 and G_2, then u,v is…
Let G be a graph with n vertices, and let μ(G) denote its mean subtree order. Let K_n be the complete graph on n vertices. Complete-graph extremality conjecture. For every graph G with n vertices, μ(G)≤μ(K_n). This is the maximum part of…
Let A be a nonnegative primitive tensor of fixed order m and dimension n. Its primitive degree γ(A) is the smallest positive integer r such that A^r is essentially positive, equivalently such that the majorization matrix M(A^r) is…
Let G be a graph. It is 2-divisible if, for every induced subgraph H of G, the vertex set V(H) can be partitioned into sets A and B such that ω(A)<ω(H) and ω(B)<ω(H). The NP-completeness conjecture. It is NP-complete to determine whether a…
Conjecture For all k there is an integer f(k) such that every digraph of minimum outdegree at least f(k) contains a subdivision of a transitive tournament of order k.