Noga Alon

activity

20192026

most citedMixing properties of colorings of the

Z^{d}

lattice

4 citations · 8 across the 17 of their papers we have counts for

collaborators

20 papers

math.CO2026

Hadwiger--Nelson Problem for Typical Norms

Noga Alon, Matija Bucić, James Davies

The classical Hadwiger-Nelson problem asks for the chromatic number of the unit distance graph of the Euclidean plane. Over the years, this problem has been considered for a variet…

math.CO2026

Spanning subhypergraphs with degree constraints

Noga Alon, Penny Haxell, Aleksa Milojević +1

An old result of Tutte states that any $d$ -regular graph contains a spanning subgraph in which every vertex has degree $k$ or $k + 1$ , for every $1 \leq k \leq d$ . We generalize this s…

math.CO2026

Pseudoshattering Pairs

Noga Alon, Varun Sivashankar

For two vectors $x, y \in [b]^{k}$ , consider the bipartite graph with two copies of $[b]$ in which $i$ on the left is joined to $j$ on the right if $(x_{t}, y_{t}) = (i, j)$ for some coordinat…

math.CO2026

Packing arithmetic progressions

Noga Alon, Michał Dębski, Jarosław Grytczuk +1

Let $F = {A_{1}, A_{2}, \dots, A_{k}}$ be a collection of finite arithmetic progressions, where each $A_{d}$ is an initial segment of the set $D_{d} = {d, 2 d, 3 d, \dots}$ of consecutiv…

math.CO2025

Distinct Directions and Distinct Distances in $R^{d}$

Noga Alon, Rom Pinchasi

We show that there exists an absolute positive constant $b (\geq \frac{1}{48})$ so that any set of $n$ points in $R^{d}$ that is $d$ -dimensional determines at least $b d n$ li…

math.CO2025

Sums along the edges of bounded degree graphs

Noga Alon, Itai Benjamini, Georgii Zakharov +1

Let $G$ be a graph on $n$ vertices and $(H, +)$ be an abelian group. What is the minimum size $S_{H} (G)$ of the set of all sums $A (u) + A (v)$ over all injections $A : V (G) \to H$ ? In…

math.CO2025

The spanning tree spectrum: improved bounds and simple proofs

Noga Alon, Matija Bucić, Lior Gishboliner

The number of spanning trees of a graph $G$ , denoted $τ (G)$ , is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper…

math.PR2025

Hitting k primes by dice rolls

Noga Alon, Yaakov Malinovsky, Lucy Martinez +1

Let $S = (d_{1}, d_{2}, d_{3}, \dots)$ be an infinite sequence of rolls of independent fair dice. For an integer $k \geq 1$ , let $L_{k} = L_{k} (S)$ be the smallest $i$ so that there are $k$ inte…

math.CO2024

Maximum shattering

Noga Alon, Varun Sivashankar, Daniel G. Zhu

A family $F$ of subsets of $[n] = {1, 2, \dots, n}$ shatters a set $A \subseteq [n]$ if for every $A^{'} \subseteq A$ there is an $F \in F$ such that $F \cap A = A^{'}$ .…

math.CO2024

On hypercube statistics

Noga Alon, Maria Axenovich, John Goldwasser

Let $d \geq 1$ and $s \leq 2^{d}$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_{n}$ and $n \geq d$ , let $λ (n, d, s, A)$ denote the fraction of subcubes $Q_{d}$ o…

math.CO2024

Rainbow Stackings of Random Edge-Colorings

Noga Alon, Colin Defant, Noah Kravitz

A rainbow stacking of $r$ -edge-colorings $χ_{1}, \dots, χ_{m}$ of the complete graph on $n$ vertices is a way of superimposing $χ_{1}, \dots, χ_{m}$ so that no edges of the same color ar…

math.CO2024

Sumsets in the Hypercube

Noga Alon, Or Zamir

A subset $S$ of the Boolean hypercube $F_{2}^{n}$ is a sumset if $S = A + A = {a + b ∣ a, b \in A}$ for some $A \subseteq F_{2}^{n}$ . We prove that the number of sumse…

math.CO2024

Erasure codes and Turán hypercube problems

Noga Alon

We observe that several vertex Turán type problems for the hypercube that received a considerable amount of attention in the combinatorial community are equivalent to questions abo…

cs.LG2023

Optimal Sample Complexity of Contrastive Learning

Noga Alon, Dmitrii Avdiukhin, Dor Elboim +2

Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sam…

math.CO2023

Universality for graphs with bounded density

Noga Alon, Natalie Dodson, Carmen Jackson +3

A graph $G$ is $universal$ for a (finite) family $H$ of graphs if every $H \in H$ is a subgraph of $G$ . For a given family $H$ , the goal is t…

math.CO2023

Connectivity Graph-Codes

Noga Alon

The symmetric difference of two graphs $G_{1}, G_{2}$ on the same set of vertices $V$ is the graph on $V$ whose set of edges are all edges that belong to exactly one of the two graphs $…

math.CO2023★ 3 cited

Essentially tight bounds for rainbow cycles in proper edge-colourings

Noga Alon, Matija Bucić, Lisa Sauermann +2

An edge-coloured graph is said to be rainbow if no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decad…

math.CO2023

Ordering Candidates via Vantage Points

Noga Alon, Colin Defant, Noah Kravitz +1

Given an $n$ -element set $C \subseteq R^{d}$ and a (sufficiently generic) $k$ -element multiset $V \subseteq R^{d}$ , we can order the points in $C$ by ranking each point $…

math.CO2023★ 1 cited

Unit and distinct distances in typical norms

Noga Alon, Matija Bucić, Lisa Sauermann

Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in discrete mathematics. They ask for the maximum numbe…

math.CO2019★ 4 cited

Mixing properties of colorings of the $Z^{d}$ lattice

Noga Alon, Raimundo Briceño, Nishant Chandgotia +2

We study and classify proper $q$ -colorings of the $Z^{d}$ lattice, identifying three regimes where different combinatorial behavior holds: (1) When $q \leq d + 1$ , there exist fr…

Hadwiger--Nelson Problem for Typical Norms

Spanning subhypergraphs with degree constraints

Pseudoshattering Pairs

Packing arithmetic progressions

Distinct Directions and Distinct Distances in Rd

Sums along the edges of bounded degree graphs

The spanning tree spectrum: improved bounds and simple proofs

Hitting k primes by dice rolls

Maximum shattering

On hypercube statistics

Rainbow Stackings of Random Edge-Colorings

Sumsets in the Hypercube

Erasure codes and Turán hypercube problems

Optimal Sample Complexity of Contrastive Learning

Universality for graphs with bounded density

Connectivity Graph-Codes

Essentially tight bounds for rainbow cycles in proper edge-colourings

Ordering Candidates via Vantage Points

Unit and distinct distances in typical norms

Mixing properties of colorings of the Zd lattice

Distinct Directions and Distinct Distances in $R^{d}$

Mixing properties of colorings of the $Z^{d}$ lattice