Problems
No problem here has yet been reviewed by a person.
A graph on n vertices is very well-covered if every maximal independent set has size n/2. Levit and Mandrescu conjectured that the independence polynomial i(G,x) of every very well-covered graph is unimodal, i.e. its coefficient sequence…
An asymptotic formula for p(k), the limiting probability that a random permutation has an invariant set of size k: it is asymptotically k^-δ(1+o(1)) times a smooth positive function, sharpening a line of estimates running through…
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).
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…
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…
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].
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…
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…
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…
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…
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.