Problems

Determine the Shannon capacities of odd cycles beyond C_5, or improve the best explicit bounds. Lovasz's theta function settled C_5 in 1979 and every longer odd cycle has stayed open since. The current records, all obtained with model…

Let A(k) be the largest possible number of moves in a north-east lattice path whose visited vertices contain no k collinear points. Gerver (1979) and Gerver and Ramsey (1979) bounded A(k) by exp(Ω(log(k)^2)) ≤ A(k) ≤ exp(O(k^4)), and…

Korsky, Saffat and Aiylam bounded the growth constant c(G) for integer-valued Lipschitz functions on G(n,d/n) between 1/(2d) and 4log^2 d/d up to lower-order terms. The random-graph side is sharpened.

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…

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…

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.…

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?