Problems

Around the Kemeny median problem, which stays open for m=3 and m=5 voters, the paper refutes three conjectures on tournament inducibility: both conjectures of Milosz, Hamel and Pierrot (the 3-cycle extension for odd m≥5, and FAS=HS_3 at…

Is the chromatic symmetric function X_G Schur positive for every claw-free graph G? Two explicit 12-vertex line graphs have Schur coefficients -64 and -40 at s_(3,3,3,3).

For positive integers d and k, let n_k(d) be the maximum order of a graph of maximum degree at most d and diameter at most k. It is shown that lim_d → ∞n_k(d)/d^k = 1 for every fixed k, thereby resolving the asymptotic degree-diameter…

Erdos Problem #593 asks which finite triple systems occur in every uncountably chromatic triple system. The answer is exactly the class generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and…

Treglown conjectured, in a complementary form, that for every positive integer k every digraph D with mind^+(v), d^-(v) ≤ k-1 for all v has an equitable acyclic k-colouring. This implies the acyclic colouring versions of the…

With N = 2^k - 1 and wt(n) the binary Hamming weight, Tu and Deng conjectured that for every 1 ≤ t ≤ N-1 at most 2^k-1 pairs (a,b) satisfy a + b ≡ t pmod N and wt(a) + wt(b) < k. Proved in full.

The dimension-five case asks whether, for every nonnegative 5×5 real matrix A whose entries sum to 5, the Dittert functional Φ(A)=∏_i r_i+∏_j c_j-per(A) is uniquely maximized at U_5=J_5/5. The submitted artifact claims the stronger…

A graph G on n vertices with k edges is t-edge-balanced if every graph on n vertices with t edges is contained in exactly the same number of subgraphs of K_n isomorphic to G. Infinite families were known for t = 2, but no example was known…

Is the fractional chromatic number of every d-degenerate triangle-free graph at most (1+o(1))d/log d, with a matching lower bound, as conjectured by Martinsson and Steiner? The upper bound is confirmed constructively for graphs of girth at…

Let g(r) be the fewest edges in an r-uniform intersecting hypergraph with cover number r. Erdos and Lovasz proved g(r) ≥ 8r/3 - 3. An elementary argument gives g(r) ≥ 3r - 4, and building on it with Kahn's small-codegree edge-colouring…

Boots and Royle, and independently Cao and Vince, conjectured that the join of an edge with a path on n-2 vertices is the unique planar graph of maximum adjacency spectral radius for every n ≥ 9. Tait and Tobin proved it for sufficiently…

A Cayley graph is minimal when no proper subset of its connection set generates the group. Babai asked whether minimal Cayley graphs have bounded chromatic number. Resolved negatively: finite minimal Cayley graphs exist with arbitrarily…

VibeMathed records no statement for this problem. See erdosproblems.com for the original.

For every connected graph, is the variance of its positive adjacency eigenvalues at most its order divided by its average distance? Exact dumbbell-graph certificates refute the bound under both conventions for average distance.

For a differential poset P, must the weighted 2-multichain series M_P,2(q) be a rational multiple of F_P(q)^2, the square of its rank generating series?

Frankl, Peng, Rodl and Talbot asked in 2007 whether the set of Turan densities of families of r-graphs contains intervals. It does: for every r ≥ 3 the set contains non-degenerate intervals, including one of the form [1-δ_r, 1].

Han and Xiong extended the Gaussian binomial coefficient to positive rational index and conjectured that its integer trace, the integer-exponent part of the resulting power series, is coefficientwise largest at the integer point. Ono's…

Is the zero forcing number of every connected graph with maximum degree 3 at most its independence number plus one? A connected 24-vertex subcubic graph with independence number 9 and zero forcing number 11 refutes this 2017 TxGraffiti…

VibeMathed records no statement for this problem. See erdosproblems.com for the original.

Erdős asked whether every n-point set in Euclidean space whose pairwise distances are mutually at least 1 apart must have diameter at least (1+o(1))n^2. Disproved: an explicit high-dimensional construction beats the conjectured constant.