Alan Lew

activity

20182026

most citedComplexes of graphs with bounded independence number

8 citations · 11 across the 15 of their papers we have counts for

collaborators

18 papers

math.CO2026

Rigidity of expanders and pseudorandom graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph $G = (V, E)$ is called $d$ -rigid if, for a generic embedding of its vertices in $R^{d}$ , the only continuous motions of the vertices preserving the distances between al…

math.CO2026

Combinatorial sufficient conditions for graph rigidity and applications to random graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph $G = (V, E)$ is called $d$ -rigid if, for a generic embedding of its vertices in $R^{d}$ , every edge-length preserving continuous motion of the vertices preserves the di…

math.CO2025

Stiffness matrices of graph blow-ups and the $d$ -dimensional algebraic connectivity of complete bipartite graphs

Yunseong Jung, Alan Lew

The $d$ -dimensional algebraic connectivity $a_{d} (G)$ of a graph $G = (V, E)$ is a quantitative measure of its $d$ -dimensional rigidity, defined in terms of the eigenvalues of stiffness…

math.CO2025

On the $k$ -volume rigidity of a simplicial complex in $R^{d}$

Alan Lew, Eran Nevo, Yuval Peled +1

We define a generic rigidity matroid for $k$ -volumes of a simplicial complex in $R^{d}$ , and prove that for $2 \leq k \leq d - 1$ it has the same rank as the classical generic…

math.CO2024

Minimum degree conditions for graph rigidity

Michael Krivelevich, Alan Lew, Peleg Michaeli

We study minimum degree conditions that guarantee that an $n$ -vertex graph is rigid in $R^{d}$ . For small values of $d$ , we obtain a tight bound: for $d = O (n)$ , ever…

math.CO2023★ 1 cited

Rigid partitions: from high connectivity to random graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli

A graph is called $d$ -rigid if there exists a generic embedding of its vertex set into $R^{d}$ such that every continuous motion of the vertices that preserves the lengths o…

math.CO2023

Asymptotic behavior of Laplacian eigenvalues of subspace inclusion graphs

Alan Lew

Let $Fl_{n, q}$ be the simplicial complex whose vertices are the non-trivial subspaces of $F_{q}^{n}$ and whose simplices correspond to families of subspaces forming a f…

math.CO2023

Laplacian eigenvalues of independence complexes via additive compound matrices

Alan Lew

The independence complex of a graph $G = (V, E)$ is the simplicial complex $I (G)$ on vertex set $V$ whose simplices are the independent sets in $G$ . We present new lower bounds on the…

math.CO2023

Extensions of the Colorful Helly Theorem for $d$ -collapsible and $d$ -Leray complexes

Minki Kim, Alan Lew

We present extensions of the Colorful Helly Theorem for $d$ -collapsible and $d$ -Leray complexes, providing a common generalization to the matroidal versions of the theorem due to K…

math.CO2023

Garland's method for token graphs

Alan Lew

The $k$ -th token graph of a graph $G = (V, E)$ is the graph $F_{k} (G)$ whose vertices are the $k$ -subsets of $V$ and whose edges are all pairs of $k$ -subsets $A, B$ such that the symmetr…

math.CO2023

Rigidity expander graphs

Alan Lew, Eran Nevo, Yuval Peled +1

Jordán and Tanigawa recently introduced the $d$ -dimensional algebraic connectivity $a_{d} (G)$ of a graph $G$ . This is a quantitative measure of the $d$ -dimensional rigidity of $G$ wh…

math.CO2022

On the $d$ -dimensional algebraic connectivity of graphs

Alan Lew, Eran Nevo, Yuval Peled +1

The $d$ -dimensional algebraic connectivity $a_{d} (G)$ of a graph $G = (V, E)$ , introduced by Jordán and Tanigawa, is a quantitative measure of the $d$ -dimensional rigidity of $G$ that i…

math.CO2022

Sharp threshold for rigidity of random graphs

Alan Lew, Eran Nevo, Yuval Peled +1

We consider the Erdős-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed $d \geq 1$ , we show that with high…

math.CO2021

Leray numbers of tolerance complexes

Minki Kim, Alan Lew

Let $K$ be a simplicial complex on vertex set $V$ . $K$ is called $d$ -Leray if the homology groups of any induced subcomplex of $K$ are trivial in dimensions $d$ and higher. $K$ is…

math.CO2020

Representability and boxicity of simplicial complexes

Alan Lew

Let $X$ be a simplicial complex on vertex set $V$ . We say that $X$ is $d$ -representable if it is isomorphic to the nerve of a family of convex sets in $R^{d}$ . We define the…

math.CO2019★ 8 cited

Complexes of graphs with bounded independence number

Minki Kim, Alan Lew

Let $G = (V, E)$ be a graph and $n$ a positive integer. Let $I_{n} (G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set o…

math.CO2018

Collapsibility of simplicial complexes of hypergraphs

Alan Lew

Let $H$ be a hypergraph of rank $r$ . We show that the simplicial complex whose simplices are the hypergraphs $F \subset H$ with covering number at most…

math.CO2018★ 2 cited

Spectral gaps, missing faces and minimal degrees

Alan Lew

Let $X$ be a simplicial complex with $n$ vertices. A missing face of $X$ is a simplex $σ \in / X$ such that $τ \in X$ for any $τ ⊊ σ$ . For a $k$ -dimensional simplex $σ$ in $…

Rigidity of expanders and pseudorandom graphs

Combinatorial sufficient conditions for graph rigidity and applications to random graphs

Stiffness matrices of graph blow-ups and the d-dimensional algebraic connectivity of complete bipartite graphs

On the k-volume rigidity of a simplicial complex in Rd

Minimum degree conditions for graph rigidity

Rigid partitions: from high connectivity to random graphs

Asymptotic behavior of Laplacian eigenvalues of subspace inclusion graphs

Laplacian eigenvalues of independence complexes via additive compound matrices

Extensions of the Colorful Helly Theorem for d-collapsible and d-Leray complexes

Garland's method for token graphs

Rigidity expander graphs

On the d-dimensional algebraic connectivity of graphs

Sharp threshold for rigidity of random graphs

Leray numbers of tolerance complexes

Representability and boxicity of simplicial complexes

Complexes of graphs with bounded independence number

Collapsibility of simplicial complexes of hypergraphs

Spectral gaps, missing faces and minimal degrees

Stiffness matrices of graph blow-ups and the $d$ -dimensional algebraic connectivity of complete bipartite graphs

On the $k$ -volume rigidity of a simplicial complex in $R^{d}$

Extensions of the Colorful Helly Theorem for $d$ -collapsible and $d$ -Leray complexes

On the $d$ -dimensional algebraic connectivity of graphs