Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let f(n) be the maximum possible chromatic number of a triangle-free graph on n vertices. Estimate f(n).
Let K_4n+1 be a complete graph on 4n+1 vertices, where 4n=m_1· m_2 and both m_1 and m_2 are even. A graphical pair ((G,g),(H,h)) without loops consists here of graphs G and H that are m_1-regular and m_2-regular, respectively. Matrix…
For integers n and c, let f(n,c) be the least integer d such that every n-vertex graph with minimum degree at least d contains a cycle with at least c chords. Kára and Král's conjecture. f(31,31)=8. Their known bounds are 8≤ f(31,31)≤9, so…
Let G=(V,E) be an undirected graph, and T ⊆ V a set of nodes of odd degree. When does an orientation D of G exist which is i) smooth (the in-degree and out-degree of every node differ by at most one), ii) well-balanced (that is λ_D(u,v) ≥…
Let D be a digraph without loops or two-cycles. Give each vertex a nonnegative real weight, and call a vertex weakly expanding when the weight of its second out-neighborhood is at least the weight of its first out-neighborhood. Weighted…
Let G be an r-regular bipartite graph with v=2n vertices, let m_i denote its number of i-matchings, and define d(i)=ln(m_i/r^i)-ln(fracoverlinem_i(v-1)^i), where overlinem_i is the number of i-matchings in the complete graph on the same…
Let P ⊂ R^d be a lattice polytope with d ≥ 3. Write g_r( P) for the coefficients of its Ehrhart polynomial, let vol( P) denote its volume, and define N_r,d=minC^d_r,i:lceild-1/2⌉≤ i≤ d-2. Here stirl(d+1,r+1) denotes the Stirling-number…
For every positive integer t, every K_{t+1}-topological-minor-free graph and every odd K_{t+1}-minor-free graph admits a vertex coloring with t colors in which every monochromatic component has bounded size.
Let n=4k+7 with k≥ 2, and let Cone=Cone(Cone_2k+1∪Cone_2k+3). Cone asymptotic-size conjecture. Is lim_n→∞frac|Cone|2^n-2=1? Numerical checks through k=249 found ratios below 1 and increasingly close to it. The conjecture asks whether this…
For a triangle-free graph G on Fin(n), define h_2(G) to be the smallest number of edges that must be added to G so that the resulting graph remains triangle-free and has diameter at most 2; that is, every two distinct vertices are adjacent…
Let P=(T;U,V) be a 3M-DAP, with parameters t,v,s_t,s_v,x_t,x_v, and let f(P) denote its optimal value. Type-2 zero-problem lower-bound conjecture. If (v-1)t-v>0 and s_t>(v-1)s_v, then f(P)>(v-1)x_t-x_v/(v-1)t-v. The source says that this…
Conjecture For every prime p, there is a constant c(p) (possibly c(p)=p ) so that the union (as multisets) of any c(p) bases of the vector space ( Z_p)^n contains an additive basis.
Let f be a finite sum of quadratic monomial rotation-symmetric Boolean functions, and let W_f(n) denote the Hamming weight of its induced Boolean function on n variables. Let R(f) be the associated rules matrix, and let λ_1,…,λ_N be the…
Let G=(V,E) be an undirected graph, and let (V^-,E^-) and (V^+,E^+) be two copies of G. For each v∈ V, write v^- and v^+ for its copies, and form the bunkbed graph by adding bidirected vertical edges between v^- and v^+ for every v∈ V.…
Let G be a simple graph. A pendant path of G is a path such that one of its end vertices has degree 1, the other end has degree at least 3, and all its internal vertices have degree 2. For a positive integer k, let p_k(G) be the number of…
Prove that sufficiently many elliptic curves E/F_p have smooth group order #E(F_p).
Let k>3 be an integer. Let A be an extremal 2k,k-polyform with h tiles, let tildeA be the associated 2k,3-polyform, and let P_min^2k,k(h) denote the minimum perimeter among 2k,k-polyforms with h tiles. A polyform is crystallized when it…
Let H(n,3) be the Hamming graph on Z_3^n, and let U⊆ Z_3^n induce a subgraph of maximum degree 1. Write α(H(n,3)) for the independence number of H(n,3). Ansensio–García-Marco–Knauer conjecture. All such subsets satisfy |U|=α(H(n,3))+O(1).…
Let a grand zigzag knight's path be a path whose number of steps has an expected value determined by the corresponding family of paths ending on the x-axis at size n. Asymptotic expected-length conjecture. An asymptotic approximation for…
Let a maximal planar graph be a planar graph to which no edge can be added while preserving planarity, and let a spanning 2-tree be a spanning subgraph that is a 2-tree. Spanning 2-tree conjecture. Every maximal planar graph with order n≥3…