Graph-theory open problems

Noga Alon

Author (arXiv only) · 100 problems

Title Source Status Imp. Posted
4/3 constant in arithmetic progression packing arxiv open 2026-03-03
Prime AP packing asymptotic n³/ln n arxiv open 2026-03-03
AP packing asymptotics for k near √n arxiv open 2026-03-03
Asymptotic regimes of Mₖ(n) packing progressions arxiv open 2026-03-03
Trivial lower bound tight for AP packing arxiv open 2026-03-03
s-convex Tverberg partition number arxiv partial 2026-02-27
Generic d-norm distinct distances lower bound arxiv open 2025-11-07
Polynomial tree-α bound in K_{t,t}-free graphs arxiv open 2025-11-05
Tree-independence number via induced biclique number arxiv open 2025-11-05
Sumset small-doubling covering structure arxiv open 2025-09-02
Primality characterization of cyclic swap diameter arxiv partial 2025-08-06
Characterisation of maximum circular sorting permutations arxiv disproved 2025-08-06
Monotonicity of all-swaps graph diameter arxiv open 2025-08-06
Rainbow cycles in non-abelian additive structure arxiv open 2025-02-26
Hypercube partitions and matchings counting arxiv open 2024-11-07
Hypercube partition ratio growth rates arxiv partial 2024-11-07
2-subcube partition asymptotics in hypercube Q_d arxiv open 2024-11-07
f₂(d) asymptotic bound in hypercube partitions arxiv open 2024-11-07
Subexponential gap for dimension-2 subcube partitions arxiv open 2024-11-07
λ(d,1) asymptotic limit 1/e hypercube arxiv open 2024-10-27
Tight bounds for hypercube λ(d,s) arxiv partial 2024-10-27
Precise asymptotic of f(n,r,s) for s ≤ √r/log r arxiv open 2024-06-10
Transition threshold between f and g arxiv open 2024-06-10
Sharp threshold for rainbow stacking of edge-colorings arxiv open 2024-05-23
Rainbow stacking universality for odd Kₙ arxiv open 2024-05-23
Universality for bounded-density graph families arxiv open 2024-01-11
Top-k eigenvalue limit points of d-regular graphs arxiv solved 2023-10-13
Connectivity code of torus graphs C_t × C_s arxiv open 2023-09-06
Vanishing hat-success probability for intersecting families arxiv open 2023-08-21
Vanishing success probability for monotone hat strategies arxiv open 2023-08-21
Fractional independence in Kneser Hamming powers arxiv open 2023-08-21
Positive gap in hat-problem success probability arxiv open 2023-08-21
Binomial sampling gap for independence ratio arxiv partial 2023-08-21
Sign-pattern bound r-dependence gap arxiv open 2023-08-09
Zero-count gap for sums of square-root polynomials arxiv open 2023-08-09
Protrusive ordering not witnessed by 5 points arxiv solved 2023-08-09
n(2,d) asymptotic limit ½ arxiv partial 2023-03-03
Existence of limit n(2,d)/d² arxiv open 2023-03-03
Even-edge graphs and H-code density arxiv partial 2023-02-06
K₄ graph-code density vanishing arxiv partial 2023-02-06
Linear graph-code cardinality bounds for even H arxiv partial 2023-02-06
Binary vectors with cube-length forbidden symmetric difference arxiv open 2023-02-06
Odd-intersection edge coloring of Kₙ arxiv partial 2023-02-06
Sufficiency of E, R, T for Generic Multiplicity Matrices arxiv solved 2022-12-10
Turán extremal problem for H-free bounded matching arxiv partial 2022-10-26
p(n) range for hereditary subgraph concentration arxiv open 2022-10-23
Bipartite-missing hereditary ex(G(n,p), P) sharp asymptotics arxiv partial 2022-10-23
Polynomial saving in bipartite hereditary ex arxiv solved 2022-10-23
M_{F_{2c}}(n) gap for odd n arxiv open 2022-04-01
√n log n implicit labels for hereditary families arxiv open 2022-01-02
Implicit representation for sub-polynomial speed hereditary families arxiv open 2022-01-02
Sharp rank bounds for powers-of-two matrices arxiv open 2021-09-01
Optimal asymmetric list sizes in bipartite graphs arxiv open 2021-08-30
Asymmetric Krivelevich–Alon choosability for bipartite graphs arxiv open 2021-08-30
Near-uniform degree distribution in regular spanning subgraphs arxiv partial 2021-08-06
Irregular spanning subgraph with minimum degree bound arxiv partial 2021-08-06
Hat guessing number bounded by degeneracy arxiv open 2021-07-21
Hat guessing number growth in G(n,1/2) arxiv partial 2021-07-21
Hat guessing number under universal vertex addition arxiv open 2021-07-21
q-divisible subdivision f(H,q) growth rate arxiv solved 2021-06-29
Linearity of g(q) in divisible subdivisions arxiv solved 2021-06-29
Horizontal uniformity of runsort permuton density arxiv open 2021-06-28
Isolated-vertex threshold for FS(X,Y) connectivity arxiv partial 2021-06-15
Friends-and-Strangers FS(X,Y) isolated-vertex cutoff coincidence arxiv solved 2021-06-15
Chromatic number of G_{m,t} is Θ(t²) arxiv open 2021-04-04
Minimal complement count T(n) square-root growth arxiv open 2020-12-30
T(p) upper bound for prime groups arxiv open 2020-12-30
Optimal solid maximal supplement bound in abelian groups arxiv open 2020-12-30
Threshold for minimal complements in finite groups arxiv open 2020-12-30
Near-sunflower exponential bound for k-uniform families arxiv open 2020-10-12
Binary focal family upper bound non-tightness arxiv partial 2020-10-12
List Ramsey R_ℓ(K_{1,2}, k) parity gap arxiv open 2020-08-12
List vs ordinary Ramsey number equality for Kᵣ arxiv open 2020-08-12
ε-t-net size and computation arxiv open 2020-03-16
Expansion-corruption detection gap in networks arxiv open 2020-03-12
Q(s,r) asymptotics for growing s and r arxiv open 2020-02-26
Hat guessing number graph parameter bounds arxiv partial 2020-01-15
Hat guessing number of complete bipartite graphs arxiv open 2020-01-15
Optimal threshold for ℤᵈ lattice list-colorability arxiv open 2019-12-25
1/e upper bound on ind(k,ℓ) arxiv solved 2019-11-01
Inducibility upper bound 1/e for non-trivial graphs arxiv solved 2019-11-01
Quantum ergodicity failure in narrow spectral windows arxiv open 2019-08-10
α equals IR in multipartite direct products arxiv open 2019-04-04
NP-hardness of generalized Turán approximation arxiv open 2018-11-21
Exact leading coefficient of maxcode_L even L arxiv open 2018-05-14
Forest families eventually k-nice arxiv open 2018-04-16
Forest-containing families are infinitely k-nice arxiv open 2018-04-16
Kₘ extremal threshold in H-free G(n,p) arxiv partial 2017-11-19
Tight constant for clique chromatic G(n,½) arxiv solved 2017-11-05
Polynomial error term in H-free clique maximization arxiv open 2017-06-18
Monotone interference growth with network depth arxiv open 2017-06-09
Multitasker threshold at average degree log n arxiv open 2017-06-09
Regularity-free ordered graph removal lemma arxiv partial 2017-04-07
Polynomial dependence in ordered binary matrix removal arxiv partial 2017-04-07
Bounded-norm bipartite Johnson-Lindenstrauss reduction arxiv open 2017-04-02
Simultaneous fair representation in path partitions arxiv open 2016-11-10
Fair Matching Representation in K_{n,n} Partition arxiv partial 2016-11-10
Fair matching representation via edge partition arxiv open 2016-11-10
Fair representation matching in bipartite graphs arxiv open 2016-11-10
Rainbow cycle error term in K_n arxiv partial 2016-08-25