Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a connected graph with n vertices. The cop number c(G) is the minimum number of cops needed for the Cop Player to have a winning strategy in G. Meyniel's conjecture. c(G)=O(√n). The conjecture is tight up to the constant factor,…
Let A_n be the n× n unit-primitive matrix, let I_n be the n× n identity matrix, and let P_n(x) be the polynomial defined by P_n(x)=∑_k=0^nP(n,k)x^k. Let U_n(x) denote the Chebyshev polynomial of the second kind, defined by U_0(x)=1,…
Let q≡ 3pmod 4 be a prime power, and let P^*_q^2 denote the Peisert graph of order q^2. A maximum clique is a clique of largest possible size. Mullin's conjecture. The only maximum clique in P^*_q^2 containing 0 and 1 is the subfield F_q.…
A heroic family of graphs is one for which there is a constant d(H)>0 such that every H-free graph has cochromatic number less than d(H). A complete graph is denoted by K, and a tree by T. Gyárfás–Sumner conjecture. For every complete…
Let (G_k) be a locally convergent sequence of bounded-degree graphs, each having separation profile of order at most the square root of the subgraph size. Must the local limit be recurrent?
For each positive real number r, let W_r,n be the set of restricted binary words of length n with parameter r. Existence conjecture. For given r ∈ R^+, the limit lim_n→∞frac|W_r,n+1||W_r,n| exists. For positive rational parameters, the…
Let f(n) be the maximal number of edges in a graph on n vertices such that all cycles have more vertices than diagonals. Is it true that f(n)≪ n?
Can the nonlinear Schrödinger (NLS) approximation be justified for original nonlinear wave systems on periodic graphs with quadratic nonlinearities and Kirchhoff vertex conditions?
For which classes of digraphs can we explicitly give a linear description of the convex hull of kernels?
Let ω be a word in which every letter occurs exactly twice, and let overlineG(ω) be the simple graph obtained from the Seifert-cycle multigraph by replacing multiple edges between two vertices with a single edge. Seifert-cycle tree…
Another major open problem in this area is the Erdős-Hajnal conjecture: Theorem 3. If G is an induced H-free graph, then G has edit distance at most \varepsilon|V (G)|2 from a graph G′ such that G′ has an induced homomorphism to an in-…
Question: (Conlon--Fox--Sudakov) Is r_f(H,H) ≤ c_k(d) n for all n-vertex d-degenerate (in the above sense) k-uniform hypergraph H?
Let A085680(n) denote the packing number of the double vertex graph of the path graph P_n, equivalently ρ(F_2(P_n)), where F_2(P_n) is the 2-token graph of P_n. Rob Pratt's conjecture asserts ∑_n≥ 0…
A two-rooted graph (H,s,t) is a graph H with two distinguished vertices s and t. A two-rooted graph is inherent if every graph containing a copy of H also contains an avoidable copy of (H,s,t). Let P=(s,t,v) be a two-edge path. Two-edge…
Let Γ=Γ_1∪Γ_2∪Γ_3 be the family of partitions defined in the paper, and call a partition complete when it has the completeness property defined there. Complete-partition classification conjecture. A partition λ is complete if and only if…
Let S be a split system on a multiset M. The quantity Δ( M) is the parameter appearing in the known finite characterization of compatibility for split systems on multisets. Compatibility conjecture. S is compatible if and only if every…
Let λ=(λ_1,λ_2,…,λ_k) be a partition whose k parts are all distinct. For σ∈ S_k, define σ(λ)=(λ_σ(1),λ_σ(2),…,λ_σ(k)), and let ℓ(σ) be the length of σ, namely the minimum number of adjacent transpositions (i,i+1) needed to generate it.…
Let r, n, and m be positive integers. A group of r children has n cookies, each with some amount of one or more of m possible kinds of frosting. Equitable distribution conjecture. It should be possible to cut at most (r-1)m cookies and…
Can the lifting attack be improved by allowing the number-field degree [K:Q] to grow?
For nearby moduli n_i=n_1+d_i and maps f_i(r)=r^e_ibmod n_i, prove the conjecture that with sufficiently many components at least one f_i is not polynomial-time invertible, thereby validating the proposed trapdoor-free RSA-like…