Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For a graph-based pattern system with stable vertex labels in {+,−,0}, which graphs support such stable patterns, and can a graph support several stable patterns not related by trivial symmetries?
Griggs, Lu: ("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_(2) as a subposet? (What is the maximum number of subsets of [n] so that there are no A, B, C, D with A <…
Is it true that if D=(V,A) is a digraph where every node has positive out-degree, then D has a quasi-kernel of size at most |V|/2?
Let G and H be nontrivial graphs. A graph is trivially well-dominated if its closed neighborhoods form a clique partition of its vertex set. A graph is well-dominated if all its minimal dominating sets have the same cardinality. The strong…
A graph Γ is minor-excluded if some finite graph is not a minor of Γ. Two graphs are quasi-isometric when their large-scale metric spaces are equivalent up to multiplicative and additive distortion. Planarity conjecture for minor-excluded…
Let G be a 2-connected graph of order n, and let δ(G) denote its minimum degree. Asymptotic interpolation conjecture. If kgeqslant3 and δ(G)geqslantn/k, then there exists an integer n_0=f(k) such that, whenever ngeqslant n_0, G has a…
Question Is every Cayley graph Hamiltonian?
Prove analogues of the stated Heegner-point results for points arising from nonmaximal orders.
Let G≠ K_2 be a graph with cyclomatic number c, defined by c=|E(G)|-|V(G)|+1. Here, dim(G) and edim(G) denote the vertex and edge metric dimensions of G, respectively. Cyclomatic-number bound. For every such graph, vert dim(G)-edim(G)vert…
Let m≥4, and let G be a graph with chromatic number at least m. An optimal coloring of G is a coloring using exactly χ(G) colors. The chromatic-critical-pair conjecture. If G has nonadjacent vertices u,v such that every optimal coloring of…
Let a(2k+1) be the total number of near-perfect matchings of the (2k+1)×(2k+1) grid, and write a(2k+1)=2^k c_k. Kong's modulo-8 conjecture. For all k, the integer c_k is congruent to 1 modulo 8. This is presented as a further conjecture of…
For r,e≥3, let d_r(e) be the least integer d such that every r-uniform hypergraph on n vertices with no e edges spanning at most d vertices has o(n^2) edges. Is d_r(e)=(r-2)e+3?
Let X_w denote the relevant combinatorial object, let prec' be the chosen term order, and let T( X_w,prec') be its tablet; let the support of a hieroglyph mean the positions occupied by its marked entries. Multiplicity-free bumpless pipe…
For an odd integer m≥ 3, determine the least integer f(m) such that, for every integer n≥ f(m) and every tree T_n on n vertices, the Ramsey number satisfies R(T_n,C_m)=2n-1. The conjectured exact value is f(m)=⌈2m-1/3⌉ for every odd m≥ 5.
Let x be a binary string of length m, and let κ^2(x) denote its autocorrelation coefficient. The alternating string is x=1010.... Alternating-string conjecture. The alternating string x=1010... minimizes the autocorrelation coefficient…
Let G be an abelian group with at least three involutions, and let r_1,…,r_t≥ 3 satisfy r_1+…+r_t=|G|-1. A subset is zero-sum if the sum of its elements is zero. Cichacz's conjecture. There is a partition G∖e=Z_1∪…∪ Z_t where every Z_i is…
Conjecture Every graph with minimum degree at least 7 contains a K_6-minor. Conjecture Every 7-connected graph contains a K_6-minor.
For every c,ε>0, is there an n_0 such that whenever n≥ n_0, A is an n-element set of integers, and G is a graph on A with at least n^1+c edges, one has max|A+_G A|,|A·_G A|≥ n^1+c-ε, where the two sets contain the sums and products along…
Let U be the set of integers nnot≡2pmod4 for which there are at most two distinct D(n)-quadruples. Is U finite?
Furthermore, we ob- tain a new asymptotically tight bound for Grinblat’s problem as a function of edge multiplicity of the corresponding multigraph. • We give the first asymptotic proof of a 30 year old conjecture of Alspach. The report…