Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G_1 be a cycle graph of length 5, and let G_n be the graphs defined recursively in the source via the discrete suspension construction. For each n, let ψ:A_n(G_n)→ hc_n(G_n) be the natural homomorphism from discrete homotopy to…
For any ε>0 there exists S_0>0 (depending on ε, γ_1,…,γ_m and K) such that, for any S≥ S_0 and any underlineζ∈K, there exists underlines∈Z^m with |underlines|≤ S and max_1≤ i≤ n |γ_i(underlines)-ζ_i|≤ S^-1-(1/n)+ε.
Let G be a graph. It is walk-regular if [A^r]_ii=[A^r]_jj for all vertices i,j and every positive integer r, and it is β-subgraph regular if [e^β A]_ii=[e^β A]_jj for all vertices i,j. Kloster–Král–Sullivan conjecture. The graph G is…
For a graph G, let R_3(G)=R(G,G,G) denote its three-color diagonal Ramsey number, and let P_n be the path on n vertices. Faudree–Schelp conjecture. R_3(P_n)=2n-2+(nbmod 2) holds for all n≥ 1. This conjecture extends the theorem known for…
Determine ex(n,B_5,2) and ex(n,B_6,2) exactly for all large n.
Let C_n^p denote the pth power of the cycle graph C_n, and let Δ_2^t(C_n^p) be its 2-total cut complex. The 2-total cut complex conjecture. For p≥ 3 and n≥ 3p+1, Δ_2^t(C_n^p)≃ S^n-4. This conjecture is based on computed homology groups for…
Given a graph F and integers r,n, how many and what kinds of cycles longer than n can occur in a graph H with H\to(F)^r and with every induced cycle of length at most n inherited from a copy of F?
Let G be a graph in G(k), where G(k) denotes the class of connected k-regular graphs whose vertices have at most k vertices at distance two, and suppose that G is locally connected, meaning that the neighborhood of every vertex induces a…
Let k be a positive integer. A U-cycle of isomorphism classes of graphs on k nodes is a cyclic sequence in which every k-window represents a distinct isomorphism class of graphs on k nodes, and every such isomorphism class occurs as a…
Problem 4.2 (V. S´ os). Let A be strictly increasing infinite sequence of integers, and denote by An the initial n-element segment of A. Suppose that |An + An| < Cn. What can be said about the structure of A?PALO ALTO PROBLEMS 11
Explicitly describe the cocycle c_u, equivalently fast-compute invariants of local algebras split by the generalized-dihedral extensions specified in the slides.
Let X be a finite set of taxa. An r-state character on X is a partition of X into at most r states. A set C of characters is compatible if there is a tree on X that displays every character in C; such a tree is a perfect phylogeny for C.…
Conjecture Every simple connected graph on n vertices can be decomposed into at most 1/2(n+1) paths.
For every pair of integers k≥ 3 and n≥ k+1, the minimum of |v∈ V(G):deg_G(v)=k| over all graphs G of order n satisfying δ(G)=k and δ(H)<k for every nonempty proper induced subgraph H of G is max⌈2n/2k-1⌉, k^2-k-2-(k-3)n, where such a graph…
A thick te-interlace is a totally equimodular interlace satisfying the paper's thickness condition; a matrix is full-dimensional when it has the full dimension specified by that condition. Two matrices are equivalent up to resigning and…
Let (G,P_0) be a non-degenerate unmixed Markovian weighted graph whose normalized curvature flow converges to a not totally degenerate limit (G,P^∞). Let W⊂ V be the vertices incident to non-degenerate edges of the limit, let G_W be the…
For a_1,a_2\geq 1, does every (a_1+a_2+2)-edge-connected graph G have edge-disjoint spanning subgraphs G_1,G_2 such that G_j is a_j-edge-connected for j=1,2?
: Let S_(n) be a subset of 2^(n), interpreted as a family of truth assignments to x_(1),...,x_(n). Let S_(n)-SAT be the problem of determining satisfiability over the possible assignments in S_(n). Call S_(n) "exponential" if S_(n) > ą^(n)…
Conjecture Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.
Let a graph class be well-quasi-ordered (wqo) by the induced subgraph relation if it contains no infinite antichain under that relation, and let it be labelled well-quasi-ordered (lwqo) if the analogous property holds for graphs whose…