Asaf Ferber

collaborators

9 papers

math.CO2025

Sunflowers in set systems with small VC-dimension

JÃ³zsef Balogh, Anton Bernshteyn, Michelle Delcourt +2

A family of $r$ distinct sets ${A_{1}, \dots, A_{r}}$ is an $r$ -sunflower if for all $1 ⩽ i < j ⩽ r$ and $1 ⩽ i^{'} < j^{'} ⩽ r$ , we have $A_i \cap A_j = A_…

math.CO2025

On the edge expansion of random polytopes

Asaf Ferber, Michael Krivelevich, Marcelo Sales +1

A $0/1$ -polytope in $R^{n}$ is the convex hull of a subset of ${0, 1}^{n}$ . The graph of a polytope $P$ is the graph whose vertices are the zero-dimensional faces of $P$ and…

math.CO2025

Sharp Threshold for Cliques in Random 0/1 Polytope Graphs

Catherine Babecki, Tycho Elling, Asaf Ferber

We study graph-theoretic properties of random $0/1$ polytopes. Specifically, let $Q_{p}^{n} \subseteq {0, 1}^{n}$ be a random subset where each point is included independently with prob…

cs.DS2025

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring

Asaf Ferber, Liam Hardiman, Xiaonan Chen

We present three sublinear randomized algorithms for vertex-coloring of graphs with maximum degree $I^$ . The first is a simple algorithm that extends the idea of Morris and Song to…

math.CO2025

Minimum degree edge-disjoint Hamilton cycles in random directed graphs

Asaf Ferber, Adva Mond

In this paper we consider the problem of finding ``as many edge-disjoint Hamilton cycles as possible'' in the binomial random digraph $D_{n, p}$ . We show that a typical $D_{n, p}$ co…

math.CO2024

Hamiltonicity of Sparse Pseudorandom Graphs

Asaf Ferber, Jie Han, Dingjia Mao +1

We show that every $(n, d, I^»)$ -graph contains a Hamilton cycle for sufficiently large $n$ , assuming that $d \geq lo g^{6} n$ and $I^» \leq c d$ , where $c = \frac{1}{70000}$ . This significa…