Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let Γ_fr be the graph whose vertices are knot types and whose edges represent friendship, meaning that each knot is represented by a simple closed curve on a minimal genus Seifert surface of the other. Friendship-graph connectivity…
Let a triangle or square lattice graph be equipped with edge lengths, and consider the action obtained by summing the Ollivier-Ricci curvatures over its edges. The maximum-action conjecture states that the constant edge-length setting…
For an optimizer of the mailing problem in branched transportation, does it have finite graph structure in every ball outside the supports of the initial and target measures, and is the number of branches at a branching point uniformly…
All graphs below are finite, simple and undirected. For a graph G=(V,E), a vertex-deleted subgraph of G is a subgraph G-v obtained by deleting exactly one vertex v ∈ V together with all edges incident to it; it is an induced subgraph of G.…
Let rm gap(n) be the maximum gap among graphs on n vertices, let rm gap_2(n) be the corresponding maximum restricted to triangle-free graphs, and let s(t) and s_2(t) denote the associated sequences of positions defined in the paper.…
Let k≥ 2 and define n_k≥ 2k to be the least value of n such that n-i divides binomnk for all but one 0≤ i<k. Estimate n_k.
Let P be an n-element poset, and let ∂ denote promotion on labelings of P. Write deg(∂) for its degree of noninvertibility. Maximum noninvertibility conjecture. For any poset P, deg(∂)≤(n+2)(n+1)/6. In other words, the degree of…
Conjecture 4 (Hayward and Reed). An even-hole-free graph contains a vertex whose neighbourhood can be partitioned into two cliques.
Let nK_2 be a matching with n edges, and let C_4 be the cycle on four vertices. For graphs G, write G→ (nK_2,C_4) when every red-blue edge-colouring of G contains either a red copy of nK_2 or a blue copy of C_4, and let hat r_c(nK_2,C_4)…
Let G be a graph with maximum degree Δ. An equitable partition is a partition of the vertex set into parts whose sizes differ by at most one, and an induced forest is a vertex-induced subgraph that is a forest. Equitable induced-forest…
Conjecture: for surfaces S with f(S)=1 the motivating good-graph question has a negative answer, whereas for f(S)=2 or 3 there are surfaces with both positive and negative answers.
Griggs, Lu: For any poset P, define ex(n,P) to be the size of the largest subset of the Boolean lattice B_(n) which includes no (injective) copy of P as a (not-necessarily induced) subposet. Show that lim_(n→∞) ex(n,P) n^(1/2) 2^( -n)…
A curve C passing through lattice points (0,0)= p_0, p_1,…, p_k=(m,n) is Z-convex if the set of lattice points strictly above C, together with the points p_i+(-ε,ε) for sufficiently small ε>0, is Z-convex. Write k(C)=k and let F_C be the…
Let j≥ 1 and k≥ 2 be integers, and let G be a j-connected K_1,j(k-1)+1-free graph. Jackson–Wormald's conjecture. Then G has a (k-1)-walk. Jin and Li provided counterexamples for j≥ 2, whereas the case j=1 follows from the cited theorem;…
Call a digraph T a polytree if T is obtained from a (finite, undirected) tree by assigning to each edge one of its two possible directions, and call a digraph D a tournament if for every pair of distinct vertices u,v of D exactly one of…
Let A=x_1,…,x_k be an alphabet and wt:A→Z a weight function. For nonnegative integers n_1,…,n_k, let R^word(x_1^n_1… x_k^n_k) be the words with the prescribed multiplicities, and let D^word_wt(x_1^n_1… x_k^n_k) be those words whose levels…
Let T be a finite metric tree of total length L, and let r>0 satisfy L≥ 2r. Then there exists a probability distribution on 0-good ball covers of T, with all ball radii in [0,r], such that the expected radius measure of the random cover is…
Let ngeqslant 3 and let G be a connected graph on n nodes with at most ⌊fracbinomn22⌋ edges. Write P_n,G for the corresponding graph invariant, and let H range over graphs on at most n-1 nodes. Polynomial dependence conjecture. P_n,G is a…
For a full-rank integer lattice, is finding a nonzero vector of minimum Euclidean norm NP-hard?
Let G be a triangle-free graph satisfying CD(0,∞) with both the unweighted normalized and non-normalized Laplacians. An induced k-cycle conjecture. G contains no induced k-cycle for k≥ 5, except for C_n with n≥ 5 and several graphs. The…