Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let T(n,k) be the largest number of points in an n by k regular grid such that no three selected points form an isosceles triangle of nonzero area. Three-column exact-value conjecture. For n>4, T(n,3)=n+1 if n is odd, and T(n,3)=n+2 if n…
Let K_n_1,n_2,…, n_t be the complete t-partite graph with part sizes n_1,n_2,…,n_t. If this graph is the graph of a polytope, then the set of its part sizes satisfies n_1, n_2, …, n_t ⊂ 1, 2 . Espenschied's conjecture. If K_n_1,n_2,…, n_t…
Problem 2.8 (T. Wooley). Suppose A is a subset of the naturals. We say that A is an additive basis of order h for a polynomial sequence {f (n): n = 1, 2,... } if hA contains this sequence. If f is linear, and A is any order h basis for f…
Let G be a connected graph, let ν(G) denote its matching number, and let I(G;x) denote its independence polynomial. For a positive integer ν and an integer q, consider graphs with matching number ν and prescribed value I(G;-1)=q.…
(27) Adrien Kassel: "How does chip-firing on planar metric graphs relate to questions in analysis?"
Let m≠ n, let s be a finite sequence, and let C_m,n(s,-) be the length-preserving bijection on finite sequences over m,n. For even n>0 and j>0, let t=1^2j-1. Maximal-orbit conjecture for C_1,n. The orbit of t under the map C_1,n(1,-) has…
Conjecture that interpolation by a two-layer neural network using few parameters automatically forces the represented function to have a large Lipschitz constant, thereby making overparameterization a law of robustness.
Let P_9 denote the path on 9 vertices, let C_9 denote the cycle on 9 vertices, and let H be the graph shown in Figure H. A graph is (P_9,C_9,H)-free if it contains none of these graphs as an induced subgraph. For a graph G, let γ(G) be its…
Let P_k denote the path on k vertices, let G be a graph, and let c(G) denote its cop number. A graph is P_k-free if it contains no induced subgraph isomorphic to P_k. Sivaraman's conjecture. For all k≥ 5, if G is P_k-free, then c(G)≤ k-3.…
Let C_N be the set of all cubic graphs of order N that are cospectral with at least one other cubic graph, and let C^*_N⊆ C_N consist of the graphs produced by one of the constructions in Section 3. Asymptotic prevalence conjecture. lim_N…
For every finite tree T with n≥ 1 vertices, let w_k(T) be the number of walks of length k in T. Then, for every integer k≥ 1, n w_k+1(T)-2(n-1)w_k(T)≥ 0. The claimed equality cases are: if n≥ 3, equality holds if and only if T is a star…
Let G be a d-regular Cayley graph with spectral measure μ. Is μ a weak limit of spectral measures of finite d-regular graphs?
Question Does every strongly regular graph have either itself or a complete graph as a core?
For each n, let S_n be the symmetric group, and let z_I(S_n), z_I I(S_n), and z(S_n) denote respectively the proportions of character-table zeros of type I, of type II, and of all zeros in the character table of S_n. Equality conjecture.…
Let G be a graph. We say that G has K_t as an odd minor if there exist vertex-disjoint trees T_1,…,T_t⊆ G and functions χ_i:V(T_i)→black,white for which each χ_i is a proper 2-coloring of T_i, and for every i≠ j there are vertices x_i∈…
Let F be a finite family of distinct finite sets that is union-closed, i.e. A,B∈F Longrightarrow A∪ B∈F, and suppose F≠∅ and F≠∅. For an element x of the ground set U(F)=bigcup_A∈FA, put d(x)=#A∈F : x∈ A. Then there exists x∈ U(F) with…
Let G be a graph. An independent set S is inclusion minimal if no proper subset of S is independent with the same relevant property, and let d(S) and d_c(G) denote the graph parameters used above. The claim concerns the number of inclusion…
Conjecture Let G be a finite graph, let e,f ∈ E(G), and let F be the edge set of a forest chosen uniformly at random from all forests of G. Then P(e ∈ F | f ∈ F) ≤ P(e ∈ F)
Let C_m be a cycle of even length m≥6, let P_n be a path of odd order n≥5, and let C_mbowtie P_n denote their bow-tie graph. 3-extendability conjecture. For any even integer m≥6 and any odd integer n≥5, the graph C_mbowtie P_n is…
There exists a positive absolute constant C with the following property. Let α_1,…,α_n be nonzero algebraic numbers and logα_1,…,logα_n logarithms of α_1,…,α_n respectively. Assume that the numbers logα_1,…,logα_n are Q-linearly…