Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Problem If G is a 3-connected finite graph, is there an assignment of lengths ℓ: E(G) → mathb R^+ to the edges of G, such that every ℓ-geodesic cycle is peripheral?
For a graph G, let reg_even(G) be the largest degree of an even-regular spanning subgraph of G. For integers n and δ, define reg_even(n,δ):=minreg_even(G): |G|=n, δ(G)=δ. Nash-Williams's conjecture. If G is a graph on n vertices with…
Let G be a graph with m edges, and let sp(G)=mc(G)-m/2 denote its surplus, where mc(G) is the number of edges in a largest bipartite subgraph of G. For a fixed graph H, let sp(m,H) be the smallest value of sp(G) over all H-free graphs G…
Let N=2n+1 be odd, let N_n denote the norm of the ground state, and normalize the state by ψ_0… 01… 1=1. Let A_n=∏_j=0^n-1(3j+1)!/(n+j)!. Norm formula conjecture. The norm is N_n=frac√3^n2^n 2·5…(3n-1)/1·3…(2n-1) A_n. The formula agrees…
Let G be a bridgeless graph and let d≥ 2. The quantity φ_d,p(G) is the d-dimensional p-normed flow index. Monotonicity conjecture. As a function of p, φ_d,p(G) is continuous, increasing on [1,2], and decreasing on [2,∞]. Continuity is…
(4) Sam Hopkins: "This question concerns a recent preprint of Venkatesh and Viswanath [34], which shows that for a finite graph G on n ver-tices, the dimension of the root space associated to the root that is the sum of all simple roots in…
For a positive integer k, let C_k denote the cycle on k vertices, and let m(C_k) be its threshold Ramsey multiplicity. Threshold Ramsey multiplicity conjecture. For any sufficiently large odd integer k, m(C_k)=(k-1)!/2. The preceding…
Does every family of at least c^k k! sets of size k contain a sunflower of size 3, for some absolute constant c?
Let G=(V,E) be a connected graph with |V|=n, |E|=m, and let k be a positive integer. Density-dependent antimagic conjecture. If Δ(G)=n-k and m≥ f(k)n for some positive function f, then G is antimagic. This is motivated by the paper's…
For a fixed integer m≥ 2, let H_n^[m](1,1) denote the (1,1)-Hoggatt sums. The (1,1)-Hoggatt-sum infinite log-convexity conjecture. For every fixed m≥ 2, the sequence H_n^[m](1,1)_n≥ 1 is infinitely log-convex. This generalizes the…
Take the SBM with k communities of equal size. Take a random second-largest eigenvector e_2 ∈ R^2E of the non-backtracking operator B. Pass to a vector x ∈ R^V. Use this to recover a coloring correlated with the truth.
Does a Moore graph with girth 5 and degree 57 exist?
Let M be a random combinatorial matrix, and let Ω_0, Ω_r, and Ω_c be respectively the events that M has a zero column, contains two identical rows, and contains two identical columns. Singularity-obstruction conjecture. If c∈(0,1/2) is…
Let d53e be the symmetric group on n letters, and let w_0^(k,i) denote the family of permutations specified in the paper. For d70e i d53e, let G(d70e) be the graph of reduced words, with vertices corresponding to reduced words and braid…
Are there infinitely many n such that, for all k≥ 1, τ(n+k)≪ k?
Let C_n be a cycle, let X be an optimal function on C_n, and let d denote graph distance. Then X is an optimal function in the subgaussian sense described in the source. Bobkov–Houdré–Tetali conjecture. There exists a vertex x_0∈ V(C_n)…
Among graphs of minimum vertex degree at least 3, what is x=\limsup_{\operatorname{diam}(G)\to\infty}\frac{\operatorname{girth}(G)}{\operatorname{diam}(G)}? In particular, is x>1?
Let SP be the class of series-parallel posets, and let T(P;x,y) denote the Tutte polynomial of the greedoid induced by a poset P. The Gordon–McMahon conjecture asserts that, for all P,Q∈SP, T(P;x,y)=T(Q;x,y) if and only if P≅ Q.
An internal partition of a graph is a partition into two nonempty parts in which every vertex has at least as many neighbors in its own part as in the other. Is it true that, for every d, only finitely many d-regular graphs have no…
Let G be a graph of order n, with vertex set V(G) and edge set E(G). A 2-coloring of G is a partition E(G)=E(R)∪ E(B), where R and B are spanning subgraphs of G. Write C_k⊂ R or C_k⊂ B when the red or blue graph contains a cycle of length…