Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a planar self-dual graph without cut vertex, and let n be an odd natural number. The spanning-tree characterization conjecture for planar self-dual graphs. Then n is the number of spanning trees in G if and only if n is the sum of…
A rotor type is a finite sequence of directions; a rotor type is palindromic if it reads the same forwards and backwards, and block-repetitive if it is a concatenation of uniform blocks of a common length. A rotor type is boppy if it is…
Let T_n denote the class of trees on n vertices, and let W[T_n] be the set of their Wiener indices. Cardinality conjecture. The cardinality of W[T_n] equals 1/6n^3+O(n^2). This is one of the conjectures concerning the Wiener inverse…
- Kadrawi–Levit conjecture on the locations of log-concavity breakdowns in tree independence sequences
Let T be a tree, let α(T) denote its independence number, and let (a_i)_i=0^α(T) be its independent set sequence. Log-concavity is broken at k when a_k^2<a_k-1a_k+1. Kadrawi–Levit's conjecture. For every ℓ≥ 1, there is a tree T=T(ℓ) for…
Is the odd-class-number condition in the stated lower bound for Heegner points necessary?
Throughout, graphs are finite, simple, and undirected; k and m are positive integers, the order of a graph is its number of vertices, and κ(G) denotes its connectivity. A graph is k-connected when κ(G)≥ k. A tree has order m when it has m…
Let p_n be the n-th prime, with p_0=1, and let PD_n=(p_ℓ-p_ℓ-1)_ℓ=1^n be the first n prime gap sequence. A prime gap graph on n≥ 2 vertices is a simple graph whose vertex degrees are exactly the entries of PD_n. Toroczkai's existence…
Let p_n and q_n be the parameters of the p_n-random q_n-proportion Bulgarian solitaire, and consider the critical asymptotic regime in which p_nq_n^2n→ C for some constant C>0. Piecewise-linear limit-shape conjecture. The limit shape is…
Let α be a unit interval parking function, let F denote the Foata transform, and let spot_α denote the outcome permutation of α. Foata transform conjecture. For any unit interval parking function α, spot_F(α)=F(spot_α). The conjecture…
Let G be an n-vertex graph of average degree d, where 1≤ d≤ (1/2-ε)n. Verstraete's conjecture. disc^+(G)=Ω(d^1/2n). This conjecture concerns the positive discrepancy of graphs whose average degree is at most approximately half the number…
A covering code of radius R is a set of binary n-words so that every binary n-word can be reached from one of the codewords by changing at most R bits. How big is the smallest covering code of radius R with n bits? It is known to be a…
A minimum universal set is a collection of 12 colored MacMahon cubes that can be used to build all 30 target cubes. The paper has exhibited at least 10 such sets, including Haraguchi's set and additional shifted or symmetric examples.…
Let G be a graph, and let dem(G) denote its distance-edge-monitoring number. Let c(G) be the cyclomatic number of G. Distance-edge-monitoring conjecture. For every graph G, dem(G)≤ c(G)+1. The source presents this as a conjecture addressed…
Let G be a finite simple graph with vertex set V(G), edge set E(G), and maximum degree Δ(G). A total coloring of G is an assignment of colors to the elements of V(G)∪ E(G) such that no two adjacent vertices receive the same color, - no two…
For a finite set S of pinnacle values, let q_n(S):=∑_I⊂ S2^|I|p_n(I). Write S=s_1,…,s_p with n≥ s_p, define q'_n(S)=2^n-12^s_p-22^-s_p-12^s_p-2-22^-s_p-3…, and set D(S)=(d_1,…,d_p-1):=(s_1-1,s_2-s_1,…,s_p-1-s_p-2). Define abstract…
Let G be a graph with minimum degree δ(G)≥ 2. Define t(G) as the minimum size of a vertex set whose deletion leaves an induced forest, let LIF(G) denote the maximum order of an induced forest in G, and set f(G)=fracLIF(G)t(G). Lower-bound…
Let F(n,α) denote the smallest m such that there exists a 2-colouring of the edges of K_n so that every X⊆ [n] with lvert Xrvert≥ m contains more than α binomlvert Xrvert2 many edges of each colour. Prove that, for every 0≤ α< 1/2, F(n,α)~…
Construct improved practical trapdoor pairings.
Let (σ,π) be a pair of compositions, let ℓ(σ) and ℓ(π) denote their lengths, and let sf RSK_σ,π be the associated RSK operator. Non-real eigenvalue conjecture. If ℓ(σ),ℓ(π)≥ 3, then sf RSK_σ,π has a non-real eigenvalue. The conjecture has…
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Prove that R(Q_n) ≪ 2^n.