wovepaper — the arXiv observatory

papers

Publications (22)

math.MG2007

On metric Ramsey-type phenomena

Yair Bartal, Nathan Linial, Manor Mendel +1

The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky's theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a…

math.MG2004

Limitations to Frechet's Metric Embedding Method

Yair Batal, Nathan Linial, Manor Mendel +1

Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embeddi…

math.CO2017

Asymptotically Almost Every $2 r$ -regular Graph has an Internal Partition

Nathan Linial, Sria Louis

An internal partition of a graph is a partitioning of the vertex set into two parts such that for every vertex, at least half of its neighbors are on its side. We prove that for ev…

math.CO2012

An upper bound on the number of high-dimensional permutations

Nathan Linial, Zur Luria

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensiona…

cs.CC2009

Are stable instances easy?

Yonatan Bilu, Nathan Linial

We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. Th…

math.PR2014

Chernoff's Inequality - A very elementary proof

Nathan Linial, Zur Luria

We give a very simple proof of a strengthened version of Chernoff's Inequality. We derive the same conclusion from much weaker assumptions.

math.CO2016

Monotone Subsequences in High-Dimensional Permutations

Nathan Linial, Michael Simkin

This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the ErdÅs-Szekeres theorem: For every $k \geq 1$ , every order- $n$ $k$ -dimens…

math.CO2011

An Upper bound on the number of Steiner triple systems

Nathan Linial, Zur Luria

Let STS(n) denote the number of Steiner triple systems on n vertices, and let F(n) denote the number of 1-factorizations of the complete graph on n vertices. We prove the following…

math.CO2009

Sum complexes - a new family of hypertrees

Nathan Linial, Roy Meshulam, Mishael Rosenthal

A k-dimensional hypertree X is a k-dimensional complex on n vertices with a full (k-1)-dimensional skeleton and \binom{n-1}{k} facets such that H_k(X;Q)=0. Here we introduce the fo…

math.CO2003

Finite metric spaces--combinatorics, geometry and algorithms

Nathan Linial

Finite metric spaces arise in many different contexts. Enormous bodies of data, scientific, commercial and others can often be viewed as large metric spaces. It turns out that the…

math.CO2017

On regular hypergraphs of high girth

David Ellis, Nathan Linial

We give lower bounds on the maximum possible girth of an $r$ -uniform, $d$ -regular hypergraph with at most $n$ vertices, using the definition of a hypergraph cycle due to Berge. The…

math.CO2005

How neighborly can a centrally symmetric polytope be?

Nathan Linial, Isabella Novik

We show that there exist k-neighborly centrally symmetric d-dimensional polytopes with 2(n+d) vertices, where k(d,n)=Theta(d/(1+log ((d+n)/d))). We also show that this bound is tig…

math.CO2016

Discrepancy of High-Dimensional Permutations

Nathan Linial, Zur Luria

Let $L$ be an order- $n$ Latin square. For $X, Y, Z \subseteq {1, ..., n}$ , let $L (X, Y . Z)$ be the number of triples $i \in X, j \in Y, k \in Z$ such that $L (i, j) = k$ . We conjectur…

math.CO2004

Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap

Yonatan Bilu, Nathan Linial

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let $G$ be a graph on $n$ v…

math.CO2011

On the Lipschitz Constant of the RSK Correspondence

Nayantara Bhatnagar, Nathan Linial

We view the RSK correspondence as associating to each permutation $I ¨ \in S_{n}$ a Young diagram $I^» = I^» (I ¨ )$ , i.e. a partition of $n$ . Suppose now that $I ¨ $ is left-multiplied by $t$ …

cs.DM2012

Tight products and Expansion

Amit Daniely, Nathan Linial

In this paper we study a new product of graphs called {\em tight product}. A graph $H$ is said to be a tight product of two (undirected multi) graphs $G_{1}$ and $G_{2}$ , if $V(H)=V(G_…

math.CO2005

A counterexample to a conjecture of BjÃ¶rner and LovÃ¡sz on the $I ¨ $ -coloring complex

Shlomo Hoory, Nathan Linial

Associated with every graph $G$ of chromatic number $I ¨ $ is another graph $G^{'}$ . The vertex set of $G^{'}$ consists of all $I ¨ $ -colorings of $G$ , and two $I ¨ $ -colorings are adjacent wh…

math.GT2009

The expected genus of a random chord diagram

Nathan Linial, Tahl Nowik

To any generic curve in an oriented surface there corresponds an oriented chord diagram, and any oriented chord diagram may be realized by a curve in some oriented surface. The gen…

math.CO2012

On the vertices of the d-dimensional Birkhoff polytope

Nathan Linial, Zur Luria

Consider the Birkhoff polytope of n by n doubly-stochastic matrices. As the Birkhoff-von Neumann theorem famously states, its vertex set coincides with the set of all n by n permut…

math.CO2004

On Metric Ramsey-type Dichotomies

Yair Bartal, Nathan Linial, Manor Mendel +1

The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of…

math.PR2016

On the phase transition in random simplicial complexes

Nathan Linial, Yuval Peled

It is well-known that the $G (n, p)$ model of random graphs undergoes a dramatic change around $p = \frac{1}{n}$ . It is here that the random graph is, almost surely, no longer a forest, a…

math.PR2009

Eigenvectors of random graphs: Nodal domains

Yael Dekel, James R. Lee, Nathan Linial

We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relative…

Publications (22)

On metric Ramsey-type phenomena

Limitations to Frechet's Metric Embedding Method

Asymptotically Almost Every 2r-regular Graph has an Internal Partition

An upper bound on the number of high-dimensional permutations

Are stable instances easy?

Chernoff's Inequality - A very elementary proof

Monotone Subsequences in High-Dimensional Permutations

An Upper bound on the number of Steiner triple systems

Sum complexes - a new family of hypertrees

Finite metric spaces--combinatorics, geometry and algorithms

On regular hypergraphs of high girth

How neighborly can a centrally symmetric polytope be?

Discrepancy of High-Dimensional Permutations

Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap

On the Lipschitz Constant of the RSK Correspondence

Tight products and Expansion

A counterexample to a conjecture of BjÃ¶rner and LovÃ¡sz on the I¨-coloring complex

The expected genus of a random chord diagram

On the vertices of the d-dimensional Birkhoff polytope

On Metric Ramsey-type Dichotomies

On the phase transition in random simplicial complexes

Eigenvectors of random graphs: Nodal domains

Asymptotically Almost Every $2 r$ -regular Graph has an Internal Partition

A counterexample to a conjecture of BjÃ¶rner and LovÃ¡sz on the $I ¨ $ -coloring complex