Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Polynomial Freiman Ruzsa conjecture implies Polynomial Bogolyubov Ruzsa conjecture. Prove that polynomial Freiman Ruzsa conjecture implies Polynomial Bogolyubov Ruzsa conjecture.
Let G be a graph, and let Δ(G) denote its clique complex. Say that G is strong I-contractible when it can be reduced by the permitted strong I-contractions. A graph has trivial homology when all its reduced homology groups vanish. The…
The cycle set of a graph G on n vertices is a set A⊆ 3,…,n such that there is a cycle in G of length ℓ if and only if ℓ ∈ A. Let f(n) count the number of possible such A. Prove that f(n)=o(2^n). Prove that f(n)/2^n/2→ ∞.
Let A be an n × n 0-1 matrix, and suppose that the facets of the polyhedron P=x: A x ≤ 1, x ≤ 1 are coloured by n colours such that a facet with extreme direction -e_i does not get colour i, and every colour appears twice. Can we find in…
Let G be a graph without isolated edges. A weighting of the edges is a function ω:E(G)→1,2,3, and the induced vertex weight is ω(v):=∑_u∈ N(v)ω(uv). The 1-2-3-Conjecture. For every graph G without isolated edges, there is a weighting…
Let G be a finite, simple, undirected, connected graph of order n. A mouse moves along the graph, and a cat probes vertices, receiving relative-distance information that determines the possible mouse positions. The cat can localize the…
Conjecture An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the n vertices' trees, the star with n vertices has the most endomorphisms, while the path with n vertices has the least…
To obtain the desired quantitative bounds of our containers, we apply the hy- pergraph container lemma together with a “balanced supersaturation” result of collinear triples in F2q . And we leverage the pseudorandomness of the point-line…
Determine whether natural de Rham cup-product pairings can be used to improve zeta-function computations.
For points x,y in Teichmuller space, determine the asymptotics as R tends to infinity of the number of points in the mapping class orbit of y lying in the Thurston-metric ball of radius R about x, and relate or unify this counting problem…
Let G=(V,E) be a finite simple graph. A split of G is a pair (X,Y) of disjoint sets whose union is V. It is external if, after deleting all edges between X and Y, every vertex has degree at most half its degree in G. A graph is cubic if…
Let T be a locally finite tree, and write S≡^sharpT when S and T are mutually topological minors, meaning S≤^sharpT and T≤^sharpS. Count the isomorphism classes of such trees S. Topological Tree Alternative Conjecture. For a given locally…
For odd integers n and k with n≥ 3, consider the cycle C_n and the consecutive label set k,k+1,…,k+n-1. A prime labeling assigns these labels bijectively to the vertices of C_n so that adjacent vertices receive relatively prime labels.…
Let G be a graph, let J_G be its binomial edge ideal, and say that J_G is of linear type when its Rees algebra is generated by the degree-one part in the standard sense. Linear-type conjecture for trees and unicyclic graphs. If G is a tree…
Let d_k(n) be the expected distance from the origin after taking n random steps from the origin in Z^k (conditional on no self intersections) - that is, a self-avoiding walk. Is it true that lim_n→ ∞fracd_2(n)n^1/2= ∞? Is it true that…
Let G be a graph that is critically s-chromatic, meaning that its chromatic number is s and deleting any vertex lowers the chromatic number. For a subset W of the vertices of G, let G[W] denote the graph obtained by expanding every vertex…
Let λ_n denote the class of minimally n-convergent graphs, and let the components of a graph be its connected components. A component is unicyclic when it contains exactly one cycle. Unicyclic-components conjecture. If G∈λ_n, then G has…
Let a graph be finite, loopless, and without multiple edges, and let μ(G) denote the mean subtree order of a multigraph G, namely the average order of its subtrees. Suppose G is a connected graph that is not complete. Then there is a graph…
Given a crossing supermodular function p:2^V→ Z satisfying p(∅)=p(V)=0, what is the minimum number of pairwise non-parallel arcs (i.e. only one copy of the arc uv is allowed for any pair u,v∈ V, but opposite pairs are allowed) covering p,…
For a simple graph G, let A_G denote its graphic arrangement. A graph is strongly chordal if it has no induced n-sun for n≥ 3. An arrangement is flag-accurate when it admits a flag satisfying the required accuracy condition. Strongly…