Problems

For D_3(m) = vecC_m square vecC_m square vecC_m, can the full arc set be partitioned into three directed Hamilton cycles for every integer m ≥ 3?

For every finite connected simple graph G, is the order of the largest induced tree at least girth(G) - 1 + ecc(G, center(G)), where the last term is the eccentricity of the centre set? Answered affirmatively, with a Lean proof.

For every finite connected graph, is girth(G) + 1 at most the product of its largest induced-tree order and its second-smallest degree?

Do arbitrarily large 4-chromatic edge-critical graphs exist with minimum degree bounded below by a positive constant times the number of vertices?

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

Ji, Li and Wang conjectured in 2024 that every parallel chip-firing game on a finite connected graph whose chip count lies strictly between 2|E|-|V| and 2|E| has period exactly 2, generalizing the middle rung of Levine's devil's staircase…

Borsuk's conjecture asked whether every bounded set in R^n can be partitioned into n+1 subsets of smaller diameter. It is false in dimension 63: there is a set of 321 points in R^63 whose smaller-diameter subsets have at most 5 points, so…

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_max on every…

Must every connected graph satisfy the proposed upper bound on its independence number in terms of residue and largest induced-bipartite-subgraph order? The family overlineK_2r+1 ∨ (K_r sqcup K_r) violates it for every r ≥ 3.

Must every graph with n vertices and δ n^2 edges contain large subgraphs in which every two edges lie on specified short cycles? A dense high-girth construction refutes the statement when δ may shrink with n.

The Kajitani–Ueno–Miyano conjecture asserts that every finite uniformly dense matroid has a cyclic basis ordering. The conjecture is proved for all matroids of rank three. The new result establishes the previously unresolved divisible…

Chromatic quasisymmetric functions of natural unit interval graphs were conjectured to have log-concave coefficients in the elementary basis. A connected 13-vertex example refutes it: for the Hessenberg function…

Simon conjectured that every skeleton of a simplex is extendably shellable. False: for every d ≥ 3 there is a pure d-dimensional shellable simplicial complex that is not shelling completable.

The target-free clique conjecture asserts that the supports of stable fixed points of a nondegenerate combinatorial threshold-linear network are exactly its target-free cliques, the bidirected cliques no outside vertex receives an edge…

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

A generalization of Boppana's entropy inequality, of the kind used in union-closed-sets arguments, proved and formalized: the sharp form with the extremal constant characterized via the unique positive solution of an explicit equation.

R_dih(P_a^alt, K_b) = 1 + (a-1)(b-1) for all a ≥ 4, b ≥ 1 — the a ≥ 4 slice of Conjecture 4.9 (Damnjanović–Đorđević, arXiv:2607.06817). Combined with the a = 3 case (see sibling entry), this resolves Conjecture 4.9 in full for a ≥ 3.

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

R_dih(P_3^alt, K_b) = R_cyc(P_3^alt, K_b) = 2b - 1 for all b ∈ N — the a = 3 slice of Conjecture 4.9 (Damnjanović–Đorđević, arXiv:2607.06817) and Conjecture 4.23 (Bašić–Damnjanović–Stevanović–Stošić, arXiv:2604.16188).

There exists a Hadamard matrix of order 668: a matrix H∈-1,1^668×668 such that HH^ T=668I_668. Equivalently, the 668 rows of H are pairwise orthogonal.