Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For a graph G, let Λ(G)=ℓ∈N| G contains a cycle of length ℓ, and let G-X denote the graph obtained by deleting the vertices in X. Distinct-length cycle packing-cover conjecture. There exists a function f(k)∈O(klog k) such that every graph…
Let Dr(a,p,b) denote the average number of spins in the full two-player Dreidel game starting with a nuts for the first player, p coins, and b nuts for the second player, and set Q(a,b):=Dr(a,2,b). Dreidel conjecture. The average number of…
Does every collection of n matchings of size n in a graph contain a rainbow matching of size n-1?
Is it true that, for every k≥ 3, there is a constant c_k>0 such that ex(n,G_k) ≪ n^3/2-c_k, where G_k is the bipartite graph between y_1,…,y_k and z_1,…,z_binomk2, with each z_j joined to a unique pair of y_i?
The supplied source identifies a source-corrected Written on the Wall II (WOWII) Graph Conjecture 160 and refers to an exact corrected statement, but does not provide that statement's mathematical content. Therefore, the conjecture cannot…
Conjecture 2 (Conforti, Rao) In every balanced graph, there exists an edge that can be deleted, so that the resulting graph remains balanced. Contributed by Gerard Cornuej` ols K.1 Balanced circulants Given interer k ≥ 1 and m ≥ 1, let us…
Let n be a 3-dimensional shape, and let D_3(Q_n^3) denote the graph of dimer configurations on Q_n^3 connected by local moves of length at most 3. Connectivity conjecture. For all 3-dimensional shapes n, the graph D_3(Q_n^3) is connected.…
Pach, Tóth: Define the "crossing number" of a graph to be the minimum number of (topological) crossings of edges in any straight-line embedding in the plane. Define the "pairwaise crossing number" of a graph the be the minimum number of…
Let B_p^(m)(n,k) denote the number of m-ary words of length n having exactly k occurrences of an m-ary word p of length ell with r≥ 2 runs. Let k∈Z^+ and write q_1,…,q_m-1 for polynomials in n. The m-ary polynomial-form conjecture. For…
Given an elliptic curve with Weierstrass equation y^2=4x^3-g_2x-g_3, a nonzero period ω, the associated quasi-period η of the zeta function and a complex number u which is not a pole of wp, we have trdegQ (g_2,g_3,π/ω,wp(u),ζ(u)-(η/ω)u)≥ 2.
Let Γ be a graph on n vertices containing a perfect matching. A maximal independent set is an independent vertex set that is not properly contained in any larger independent set. The perfect-matching maximal-independent-set conjecture. Γ…
Is recognition of primitive roots modulo a prime in randomized polynomial time R?
Let Y be a graph on n≥ 2k≥ 4 vertices. A k-bridge is a set of k edges whose deletion disconnects the graph, and it is non-trivial when neither resulting component is an isolated vertex. The graph FS(K_k,n-k,Y) is the friends-and-strangers…
Here, M_F is the result of contracting F in M, M^F is the restriction of M to F and overlineχ_M^F(t) is the reduced characteristic polynomial of M. Is this polynomial should be real rooted for any matroid?
Let C be a clutter on ground set V, and let B be its blocker. Is it true that C is nonideal if and only if there exist p: C → V and q: B → V such that p(X)∈ X for every X ∈ C, p(Y)∈ Y for every Y ∈ B, if p(X)=q(Y), then |X ∩ Y|>1?
Let Q_d be the d-dimensional hypercube, and let Z_(d-2)(Q_d) denote its (d-2)-leaky forcing number. Hypercube leaky forcing conjecture. Z_(d-2)(Q_d)=2^d-1. The paper establishes an upper bound for this quantity, but the matching lower…
Let S_n be the symmetric group of permutations on [n]. For w in S_n, let S_w be its Schubert polynomial. Let lambda be the two-row Young diagram corresponding to a k-Grassmannian permutation tau in S_n_1, and let s_lambda(x_1,dots,x_k) be…
Let m be an infinite cardinal and κ be the successor cardinal of 2^ℵ_0. Can one colour the countable subsets of m using κ many colours so that every X⊆ m with lvert Xrvert=κ contains subsets of all possible colours? ", "difficulty": "L1"…
For every set of N/2 red and N/2 blue points on a circle, let ℓ(N) be the largest number such that there is a non-crossing alternating path with ℓ(N) vertices. Kynčl–Pach–Tóth alternating path conjecture. |ℓ(N)-2/3N|=o(N). The conjecture…
Let G be a primitive basic permutation group. Say that G satisfies condition (c) of Theorem 4 or condition (d) of Theorem 4 when it has the respective properties listed there. Road closure conjecture. If G does not satisfy condition (c) or…