Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G_M^+ denote the augmented return graph at modular depth M, incorporating the mixed-state excursion, exit, and return dynamics, and let K≥1 be the parameter indexing the net-positive regime. Augmented acyclicity conjecture. For every…
Determine the minimum number of elements in a set S so that such a propagation process covers the vertices of G after a time step t ∈ N.
Conjecture If G is a k-regular directed graph with no parallel arcs, then G contains a collection of k+1 choose 2 arc-disjoint directed cycles.
Let G be a connected graph. Write Z(G) for its zero forcing number, let dim(G) denote its metric dimension, and let c(G) be the number of edges that must be removed from G to obtain a forest. Cycle-rank conjecture. dim(G) ≤ Z(G)+c(G). This…
Given n, can one find r,s∈N with n=r^2s and s squarefree in deterministic polynomial time?
Must every graph of infinite chromatic number contain cycles of length 2^n for infinitely many integers n?
Let G and H be graphs. A pair (G,H) is Ramsey-infinite if it has infinitely many Ramsey-minimal graphs. An odd star is a star with an odd number of leaves, and a K_2-component is a connected component isomorphic to K_2.…
How does gonality change if each edge of the graph is subdivided k times?
Let δ_k(r) be the rth element on the kth row of the Proth-Gilbreath triangle generated by the sequence of primes, where r≥ 1 is an integer. Modular equidistribution conjecture. With finitely many exceptions, the sequence δ_k(r)_k≥ 1pmod 4…
Let A_n be the weighted Laplacian matrix with off-diagonal entries -w_ij and diagonal entries ∑_i w_ij, and define r_n(w)=Trlnφ(A_n), R_n(w)=exp(r_n(w))=detφ(A_n), where φ(t)=sinh(t/2)/(t/2). Let R_g=(R_g,n)_n≥ 1 denote the homogeneous…
For k and ℓ positive integers, the (mixed) van der Waerden number w(k,ℓ) is the least positive integer n such that every (red-blue)-coloring of [1,n] admits either a k-term red arithmetic progression or an ℓ-term blue arithmetic…
Let G be a multigraph. Its cover index ξ(G) is the maximum number of pairwise disjoint edge covers of G, and its minimum degree is δ(G). Define the co-density by Φ(G)=min 2|E^+(U)|/|U|+1: U⊆ V, |U|≥ 3 and odd , where E^+(U) consists of the…
Non-linear Roth Let P be any (non-linear) polynomial, A⊂ F_p with |A|>p^0.99. Does there always exist distinct x,y such that x,y,y+P(x)-P(y)∈ A?
Let G be a finite graph. Write drn(G) for its derangement representation number and p(G) for its order, and let F=overlineK_2,overlineK_3,P_3. Derangement representation conjecture. For every finite graph G except the graphs in F, drn(G)≤…
Consider the Trail of Lost Pennies on the finite trail llbracket -j-1,k+1rrbracket in its symmetric standard form. Finite-trail equilibrium-count conjecture. The number of time-invariant Nash equilibria equals max2(j+k)-5,1. The formula is…
If G is a finite vertex-transitive expander, must every almost automorphism of G be close to an automorphism?
Rudin's problem for F_p[x], p>2 Suppose A⊂ F_p[x] is of finite size, and every element of A is a square. Show that |A+A|≥ |A|^1+ε for some constant ε.
Let C(G) denote the number of cycles in a graph G. For alpha∈(0,1], let n be sufficiently large, let G be a graph on n vertices, and let d=α n be its average degree. Dense-cycle upper-bound conjecture. Every such graph satisfies…
Conjecture Every K_t-minor-free graph is c t-list-colourable for some constant c≥1.
For graphs G and H, the Ramsey number r(G,H) is the smallest positive integer N such that every red/blue edge-coloring of the complete graph K_N contains either a red G or a blue H. A book B_n is a graph consisting of n triangles sharing a…