Graph-theory open problems

Fox, Jacob

Author · 107 problems

Title Source Status Imp. Posted
Complete bipartite subgraphs of perfect graphs opg open ★★ 2008-06-17
Arithmetic triangle removal lemma with restricted differences arxiv open 2026-05-13
Coloring triangle-free degenerate graphs via LLL arxiv open 2026-01-21
Density bound for S-difference-free sets arxiv open 2026-05-13
Exponential order of K_r-free degenerate χ=d+1 graphs arxiv open 2026-01-21
Fractional chromatic number of K_r-free d-degenerate graphs arxiv open 2026-01-21
Non-transitive tournament color-avoiding path bound arxiv open 2026-01-21
Sub-exponential vertex threshold for degenerate coloring arxiv open 2026-01-21
Sub-linear χ_f for K_r-free degenerate graphs arxiv open 2026-01-21
Clique Ramsey minimizer K_t-Ramsey graphs arxiv partial 2025-10-01
Polynomial 3-graph Ramsey numbers via blowup characterization arxiv open 2025-10-29
q-color triangle Ramsey numbers of Kₙ arxiv open 2025-10-01
Tower-height lower bound for s-tightly connected k-graphs arxiv open 2025-10-29
Acyclic high-chromatic subgraph existence in tournaments arxiv open 2024-05-30
Acyclic subgraph chromatic number in tournaments arxiv open 2024-05-30
Anti-Sidorenko orientation of every tree arxiv partial 2024-02-13
ESₗ(n) joint dependence on ℓ arxiv open 2024-05-06
Hereditary Turán theory in (c,t)-sparse graphs arxiv open 2024-06-08
Induced Turán number for C_{2ℓ} in sparse graphs arxiv solved 2024-06-08
Monochromatic linear subspace two-coloring over 𝔽₂ⁿ arxiv open 2024-12-30
Multicolor Ramsey tower-exponent 3-graphs arxiv open 2024-04-29
Off-diagonal tripartite Ramsey 2^O(n log n) bound arxiv open 2024-04-02
Pair-complexity lower bound for 3-graph Ramsey arxiv open 2024-04-02
Polynomial close Rödl property for hereditary families arxiv open 2024-04-19
Purely exponential off-diagonal 3-graph Ramsey rate arxiv open 2024-04-02
Subexponential Ramsey bound for linear 3-graphs arxiv open 2024-04-02
Super-polynomial growth of 3-uniform complete Ramsey arxiv open 2024-04-02
Tower height for k-uniform Ramsey growth rate arxiv partial 2024-04-29
Dense linear subhypergraph with quadratic edges arxiv open 2023-12-31
Linear disjoint edges in complete topological graphs arxiv open 2023-12-02
Mixed blowup coloring of K_{r(k)-1}[2] arxiv open 2023-06-27
Multi-color √m graph Ramsey bound arxiv open 2023-08-21
n^{1/4} tight bound for non-averaging sets arxiv solved 2023-11-02
p-Goodness Threshold Not Tight for Books arxiv open 2023-07-14
Pendant edges suffice for k-critical bonbons arxiv open 2023-06-27
Polite integers in Ramsey multiplicity arxiv open 2023-06-27
Ramsey bound for 3-uniform sparse hypergraphs arxiv open 2023-12-31
Regularity-free proof of Nikiforov–Rousseau goodness theorem arxiv open 2023-07-14
Set-coloring Ramsey number equals A_q(r,s)+1 arxiv open 2023-08-14
Turán exponent of Latin square hypergraphs arxiv open 2023-12-31
Turán Exponent via d_max for k-partite Hypergraphs arxiv open 2023-12-31
3-uniform Ramsey K⁴⁻ vs star Θ(n²/log n) arxiv open 2022-10-07
Asymmetric and classical Sidorenko property equivalence arxiv open 2022-10-30
Directed forcing characterization via homomorphism arxiv open 2022-10-30
Directed Sidorenko property for K₂-homomorphic bipartite arxiv open 2022-10-30
Directed surplus in random ℬ-free orientations arxiv open 2022-04-19
Equivalent growth of N_DFL and 1/δ_TRL arxiv open 2022-01-13
Exact threshold Ramsey multiplicity for paths arxiv open 2022-08-07
Exponential constant in list Ramsey numbers arxiv open 2022-01-23
Geometric anti-concentration for nonzero vectors arxiv partial 2022-06-14
Grid Ramsey number rectangle vs clique arxiv open 2022-10-07
K⁴₃ Ramsey equals G_{2×2} Graded Ramsey Order arxiv open 2022-10-07
Linear K_{r-1}-free subgraph in K_r-free segment graphs arxiv open 2022-10-25
List Ramsey exact value for chromatic families arxiv open 2022-01-23
Near-acyclic r-free digraphs for r > 2n/3 arxiv solved 2022-04-19
O(1/√n) bound for o-minimal Littlewood-Offord arxiv partial 2022-06-14
Parameters governing acyclic digraph Ramsey growth arxiv partial 2022-01-21
Property (*) range extension to d = o(n/log n) arxiv open 2022-07-27
R(n;r,s) vs R'(n;r,s) near Turán density equality arxiv partial 2022-06-22
Tightness of cᵣ upper bound for r ≥ 3 arxiv open 2022-09-22
Edges covered by k vertex neighborhoods arxiv open 2021-03-19
Exact exponent constant for tournament path powers arxiv open 2021-02-16
Exact m(n,k) for H-free k-colorability arxiv open 2021-03-19
Exponential sunflower bound for bounded VC-dimension arxiv partial 2021-03-25
F-counting lemma in C₄-free graphs arxiv open 2021-06-06
Grid arithmetic progression discrepancy tightness arxiv partial 2021-10-28
Odd cycle Ramsey multiplicity exact formula arxiv open 2021-09-20
Order of fₖ(N; s, t) in hypergraph Turán arxiv open 2021-03-18
Petersen and dodecahedral countability in C₄-free arxiv open 2021-06-06
Polynomial bound for x₁+x₂+2x₃=x₄+3x₅ sets arxiv open 2021-09-25
Ramsey rate for link hypergraphs via odd girth arxiv open 2021-03-18
Randomized star-contraction clique minor strategy arxiv open 2021-02-08
Sharpness of h(n,k,Kᵣ) upper bound arxiv open 2021-03-19
Sharpness of n^{3/2} bound for C₅-free triangle-free arxiv open 2021-09-25
Tight bound on odd-wheel-free k-colorability arxiv open 2021-03-19
K₃ polynomial anticomplete pair property arxiv open 2020-12-07
Linear anticomplete pairs in sparse H-free graphs arxiv partial 2020-12-07
Local concentration of subgraph counts in G(n,p) arxiv partial 2020-11-18
Sparse pairs in H-free ε-bounded graphs arxiv partial 2020-12-07
Unavoidable G-dependence in blowup Ramsey prefactor arxiv solved 2020-04-06
Behrend-style sets avoiding mixed-sign affine patterns arxiv open 2019-07-02
Exponential constant in r(n,m) for 𝔽₃ⁿ subspaces arxiv open 2019-11-21
Induced arithmetic removal for higher complexity patterns arxiv open 2019-11-08
Induced arithmetic removal over abelian groups arxiv open 2019-11-08
Mandache corner bound for all abelian groups arxiv solved 2019-07-02
Polynomial clique/independent set in bounded VC-dimension graphs arxiv solved 2019-12-05
Polynomial δ-ε dependence for complexity 1 systems arxiv open 2019-11-08
Tower height bounds for nₚ(α,β) at small primes arxiv open 2019-11-21
Triangle count bound via book number in dense graphs arxiv partial 2019-10-20
Θ(√m) excess for hypergraph r-cuts arxiv disproved 2019-06-27
Alteration method generalization for r̃(m,n) arxiv partial 2018-11-04
Clique count bound for Kₜ-immersion-free graphs arxiv open 2018-08-07
Diagonal and off-diagonal online random Ramsey growth rates arxiv open 2018-11-04
Diameter-free bound for Euclidean Ramsey partition arxiv open 2018-03-20
EGZ constant growth in (ℤ/kℤ)ⁿ fixed k arxiv open 2018-04-17
Euclidean Ramsey unit-distance vs isometric copy arxiv partial 2018-03-20
Exact exponent of maximal cliques in c-closed graphs arxiv open 2018-04-20
Eⁿ non-arrow (ℓ₃, ℓ_m) for large m arxiv partial 2018-03-20
Optimal clique count exponent for K_t-subdivisions arxiv open 2018-08-07
Optimal exponent in arithmetic k-cycle removal arxiv partial 2018-09-04
Polynomial query complexity for permutation property testing arxiv open 2018-04-04
Polynomial δ Dependence in Rödl's Theorem arxiv partial 2018-03-09
Subgraph query complexity for K_m arxiv partial 2018-11-04
Edge-contraction clique-monotone graph characterization arxiv open 2016-03-23
l=1 case of Set Mapping Theorem arxiv open 2016-02-11
Ordered Ramsey exponent gap for matchings arxiv open 2016-04-25
Ordered Ramsey number matching vs triangle magnitude arxiv partial 2016-04-25