Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let k∈N, let α∈(0,frac13), and let G be a graph. Write δ(G) and Δ(G) for its minimum and maximum degrees, respectively. Besomi–Pavez-Signé–Stein conjecture. If δ(G)≥ (1+α)k/2 and Δ(G)≥ 2(1-α)k, then G contains every tree with k edges. The…
Let p_n and q_n be the parameters of the p_n-random q_n-proportion Bulgarian solitaire, and consider the asymptotic regime in which p_nq_n^2n→0 as n→∞. Triangular limit-shape conjecture. The limit shape of the p_n-random q_n-proportion…
Let n be a positive integer. A spherical parking function of length n has a degree, and a birooted tree on vertex set [n] has a number of surface inversions, where a surface inversion is a pair of non-root vertices (α,β) such that β is a…
Let W_n,k(x)=∑_m=0^kw_n,k,mx^m, where w_n,k,m counts Dyck paths of semilength n with k occurrences of UD and m occurrences of UUD. For real-rooted polynomials, G(x)preccurlyeq F(x) denotes the interlacing relation, and a finite sequence is…
Let H be the graph property of admitting a Hamilton cycle, and let s(n, H) denote the score of the corresponding saturation game on graphs with n vertices. Hamiltonicity saturation-score conjecture. s(n, H) = Θ(n^2). The conjecture…
Turn H^2(G_K,K_s^*) into an explicitly computational group.
Let G and H be connected graphs on the same vertex set, and let f: V(G) → V(H) be a bijection. The groups tilde A(G,H,f), bar A(G,H,f), and hat B(G,H,f) are the automorphism groups and subgroups defined in the source. Semidirect-product…
Let f(n,m) be the largest integer such that every graph with n vertices and m edges has a chordal subgraph with at least f(n,m) edges. For k≥ 2, let t_k(n) denote the number of edges in the balanced complete k-partite graph on n vertices.…
The sequence of Stirling numbers of the first kind count the number of permutations in S_n decomposing into k disjoint cycles. Precisely, n k := #σ ∈ S_n | σ has k distinct cycles. We say a sequence a_i of nonnegative numbers a_i is…
Let a,b,c,d∈N satisfy ableqslant cd and a=min(a,b,c,d). Let genfrac[]0ptnk denote the Gaussian binomial coefficient and let N_0[q] be the polynomials in q with nonnegative integer coefficients. Troyka's conjecture.…
Let G be a graph of order n, and let c(G) denote its cop number. Weak Meyniel's conjecture. There exists an ε>0 such that c(G)=O(n^1-ε). This weaker form of Meyniel's conjecture, also known as the Soft Meyniel conjecture, remains widely…
Let G be a graph. Write I(G) for its inversion graph and diam(I(G)) for its inversion diameter, and let Δ(G) denote the maximum degree of G. Havet–Horsch–Rambaud's conjecture. For every graph G, diam(I(G))≤ Δ(G). Havet, Horsch and Rambaud…
Let T be a tree, let t be a positive integer, and let J_t(T) denote the t-connected ideal of T. Let H be the hypergraph corresponding to J_t(T), and write ν( H) for its matching number. Regularity conjecture for t-connected ideals. One has…
Let G be an edge-coloured connected graph, and let d^c_G(v) denote the number of distinct colours on edges incident to a vertex v. Write δ^c(G)=min_v∈ V(G)d^c_G(v) for the minimum colour degree. A subgraph is properly coloured when…
Let D be a demazure diagram, meaning a finite cell diagram satisfying the demazure condition described in the paper, and let K_D denote its Kohnert polynomial. The nonnegative expansion conjecture. The polynomial K_D expands as a…
For an integer n ≥ 1 let f(n) = max|S| : S ⊆ 1,…,n^2, no three distinct points of S are collinear, where collinearity is with respect to lines of arbitrary slope in the real plane, not only lines parallel to the grid axes or diagonals;…
Investigate a,b-decompositions for “nice” h^*-polynomials.
For a finite graph H, let ind(H) denote its inducibility, and let K_|H| and overlineK_|H| be respectively the complete and edgeless graphs on |H| vertices. The Large Inducibility Conjecture. limsup ind(H): H ∉ K_|H|, overlineK_|H| = 1/e.…
For a graph H, let δ_χ(H) and δ_hom(H) denote its chromatic and homomorphism thresholds, and let δ_polymhyphen rem(H) denote its polynomial removal threshold. For the odd cycle C_2k+1 with k≥ 2, the odd-cycle removal-threshold conjecture.…
Let m=m(n,k) be minimal such that in any collection of sets A_1,…,A_m⊆ 1,…,n there must exist a sunflower of size k - that is, some collection of k of the A_i which pairwise have the same intersection. Estimate m(n,k), or even better, give…