Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let H_n be an n-dimensional Hilbert space, let I be an index set with |I|=k=mn for some m∈N, and let F=f_i_i∈ I⊆ H_n∖0 be a tight frame with factor poset F_F. Factor-poset size conjecture. |F_F|≤ ∑_ℓ=0^m binommi^n. Moreover, this bound is…
Let G be a graph, let H be obtained from G by deleting an edge, and let μ(G) and μ(H) denote their Markov widths. Edge-deletion monotonicity conjecture. If H is obtained from G by deleting an edge, then μ(H)≤μ(G). The statement extends the…
Let ε >0. Is it true that, if k is sufficiently large, then R(G)>(1-ε)^kR(k) for every graph G with chromatic number χ(G)=k? Even stronger, is there some c>0 such that, for all large k, R(G)>cR(k) for every graph G with chromatic number…
Let G be a graph, and let S_e and S_o denote the sets of lengths of even and odd cycles contained in G, respectively. Let d≥ 3. Faudree–Gould–Jacobson–Magnant conjecture. If G is a 2-connected graph on n≥ 2d vertices with minimum degree…
A prime graph is a graph with no nontrivial module, and an infinite prime graph is a prime graph with infinitely many vertices. Let G_μ denote the graph associated with a 0-1 sequence μ on an interval of Z, and let the finitely many graphs…
A 1-3 tree is a tree whose vertices have degrees 1 or 3, and a leaf-leaf path is a path with leaf endpoints. Many-short-paths conjecture. There is a constant α>0 and a function C(n) tending to infinity such that every 1-3 tree of order n…
For n≥1, let YF_n be the set of Fibonacci words of weight n. For u,v∈YF_n, let N_u,v be the corresponding multiplicity, and arrange these entries in lexicographic order into the matrix bf N_n. Write usucceq v for the dominance order on…
Problem Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?
Let the graphs G=(V,E) and H be fixed. An edge set F⊆ E is called H-free if (V,F) does not contain H as a subgraph. We say that F is strongly maximal if for any H-free edge set I⊆ E we have |I ∖ F| ≤ |F ∖ I|. If H is the path of length…
Let X^D_K be the set under consideration, let T⊂X^D_K be a subset, and write S(T) for the sum of its elements. Define Ψ^D_K=2^D(K+1)-1-2^D-1. Subset-sum conjecture. For any subset T⊂X^D_K with |T|=2^D× n elements, S(T)=Ψ^D_K× n. The claim…
Let C be the set of all pairs of non-empty sets of cycles, and let R(Ga_1,Ga_2) be the corresponding generalised Ramsey number. For (Ga_1,Ga_2)∈C, let m(Ga_1,Ga_2) be the number defined by m(Ga_1,Ga_2)=max…
Let k, m, and b be integers with k≥ 2, m≥ k, and, for k≥ 3, k-2≤ b≤ km-4k+4/k-2, where k(m-b) is even. Define f(k,m,b)(q)=binommk_q-q^k(m-b)/2+b-2k+2binombk-2_q. Here binommk_q denotes the q-binomial coefficient. Reiner–Stanton conjecture.…
Let G=(V,E), G_1=(V_1,E_1) and G_2=(V_2,E_2) be graphs. Say that G is a t-sum of G_1,G_2 along an edge e when G=(G_1∪ G_2)-e, G_1∩ G_2=K_t, e∈ E_1∩ E_2. Here R_d denotes the d-dimensional rigidity matroid, and an R_d-circuit is a circuit…
Let G be a graph whose vertices all have the same 1-subgraph centrality; equivalently, [e^A]_ii is independent of the vertex i. The degree, closeness, eigenvector, and betweenness centralities are vertex centrality measures.…
How many polyominoes on n squares are there? A polyomino is a connected interior-disjoint union of axis-aligned unit squares joined edge-to-edge, in other words, an edge-connected union of cells in the planar square lattice. The order of a…
Suppose ρ_2n+2^n-1/n(A)< Kρ_2n(A) . Then there is H⊂ (n-1)A, |H|≥ fracρ_2n^1/n-1K^c so that E_4(H)≥ frac|H|^3|A|^εK^c'.
Let R_k^B(n) denote the number of signed permutations of size n whose burnt-pancake distance from the sorted stack is k. Summation identity conjecture. If k,n≥1, then R_k^B(n)=∑_j=1^k(∑_i=0^k-j(-1)^ibinomi+j-1ibinomni+j)R_k^B(j). The…
Let t be a real number, and let G be a graph. A graph is minimally t-tough when τ(G)=t and τ(G-e)<t for every edge e∈ E(G), where τ(G) denotes its toughness. It is Generalized Kriesell's conjecture that every minimally t-tough graph has a…
Conjecture 6.13. Any simple digraph with no directed cycles of length at most k has a vertex v such that |N + k (v)| ≥ | N + k−1 (v)|. Serge Burckel also asked the following structural question:
Let F be a forest on n vertices, let π be an ordering of its edges, and let α_F,π∈C[S_n] be its chromatic operator. A chromatic operator is positive semistable when all its eigenvalues have nonnegative real part. Forest chromatic-operator…