Problems
No problem here has yet been reviewed by a person.
If W(k) is the least N such that every two-colouring of 1, …, N contains a monochromatic k-term arithmetic progression, must W(k+1) - W(k) → ∞?
For a single-source unsplittable flow, find the optimal universal additive constant C s.t. every feasible fractional flow x with arc costs c should admit an unsplittable routing y with c^top y ≤ c^top x and y_a ≤ x_a + C · D on every arc.…
Can the edges of a finite connected multigraph, given a closed eulerian trail, be partitioned into circuits so that no circuit contains two edges used consecutively in the trail? The proof in fact four-colours the edges to satisfy the…
Which finite triple systems occur in every triple system of uncountable chromatic number? The claimed characterization: exactly those that, after removing isolated vertices, are linear, have every hyperedge-node of their Levi graph meeting…
Pavez-Signe (2024) conjectured a Dirac-type condition for spanning H-subdivisions and asked whether the subdivision paths can additionally be required to have similar lengths; Lee (2025) resolved the existence conjecture in the stronger…
Let N(k, ℓ) be the least N such that every f : [N] → -1, 1 has a k-term arithmetic progression P with |∑_n ∈ P f(n)| ≥ ℓ. In particular, is N(k, 2) ≤ C^k?
For a finite forbidden triple system G, what exact uncountable chromatic cardinalities occur among G-free triple systems, and how do those spectra interact? The revised manuscript answers the three exact-cardinal questions and claims a…
The quartet distance counts the four-leaf subsets on which two binary phylogenetic trees display different topologies. Bandelt and Dress conjectured the maximum over trees on n leaves. Proved: it is (2/3 + o(1))binomn4, by reducing…
Coble and Barg introduced binary Coxeter codes, the span of indicators of standard cosets of fixed rank in a finite Coxeter system, generalizing Reed-Muller codes, and proposed a conjectural value for the minimum distance of a general…
Donner proved in 1992 that the list color function P_ℓ(G,k) equals the chromatic polynomial P(G,k) once k is large. Kaul and Mudrock asked whether the analogue holds for Hanlon's unlabeled chromatic polynomial, and could not settle even…
Gao, Huo and Ma asked whether for every fixed k ≥ 3 there is a function f_k(n) → ∞ such that every n-vertex (k+1)-critical graph contains f_k(n) consecutive cycle lengths. The paper settles this and two related problems on cycle lengths…
Let f_3(N) be the least size forcing a set A ⊆ 1,…,N to contain distinct a,b,c with a+b, a+c and b+c all in A. The upper bound f_3(N) ≤ 5N/8 + O(1) matches the standard construction [N/8,N/4] ∪ [N/2,N], so f_3(N) = 5N/8 + O(1).
If G is connected, cubic and diamond-free, must the zero-forcing number satisfy Z(G) ≤ γ(G) + 2? A connected cubic triangle-free 14-vertex graph has Z = 7 and γ = 4.
VibeMathed records no statement for this problem. See erdosproblems.com for the original.
Must every r-differential poset have at least as many elements in each rank as Y^r, the r-th Cartesian power of Young's lattice? For r = 3 the new construction has fourth-rank size 50 against 51 for Y^3.
For every finite family F of graphs, is there a single G ∈ F with ex(n;G) ≪_F ex(n;F)? A counterexample refutes the Erdős-Simonovits compactness conjecture.
At the conjectured density, must every k-uniform hypergraph contain a short nontrivial even cover - a set of hyperedges covering each vertex an even number of times - with no superfluous polylogarithmic factors? Known up to polylog factors…