38 citations · 173 across the 31 of their papers we have counts for
33 papers
More Vertices of the Tristochastic Polytope
Nati Linial, Zur Luria, Maya Trakhtman
The doubly stochastic matrices constitute a polytope in , and by Birkhoff's theorem, its vertex set coincides with the set of order- permutation ma…
Metric Approximations of Consistent Path Systems
Daniel Cizma, Nati Linial
A path system in a graph is a collection of paths, with exactly one path between any two vertices in . A path system is said to be consistent if it is cl…
Time to Cycle
Nir Lavee, Nati Linial
Consider the random process that starts with vertices and no edges, where the edges of are added one at a time in a uniformly chosen random order $e_1, e_2,\ldots, e_{\bi…
On the Number of Path Systems
Daniel Cizma, Nati Linial
A path system in a graph is a collection of paths, with exactly one path between any two vertices in . A path system is said to be consistent if it is intersection-closed. W…
Strictly Metrizable Graphs are Minor-Closed
Maria Chudnovsky, Daniel Cizma, Nati Linial
A consistent path system in a graph is an collection of paths, with exactly one path between any two vertices in . A path system is said to be consistent if it is intersecti…
Higher-order Delsarte Dual LPs: Lifting, Constructions and Completeness
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones +2
A central and longstanding open problem in coding theory is the rate-versus-distance trade-off for binary error-correcting codes. In a seminal work, Delsarte introduced a family of…
The Structure of Metrizable Graphs
Maria Chudnovsky, Daniel Cizma, Nati Linial
A consistent path system in a graph is an intersection-closed collection of paths, with exactly one path between any two vertices in . We call metrizable if every consis…
How Balanced Can Permutations Be?
Gal Beniamini, Nir Lavee, Nati Linial
A permutation is -balanced if every permutation of order occurs in equally often, through order-isomorphism. In this paper, we explicitly construct $…
On the Löwner-John Ellipsoids of the Metric Polytope
Raziel Gartsman, Nati Linial
The collection of all -point metric spaces of diameter constitutes a polytope , called the \emph{Metric Polytope}. In th…
A note on Fermat's Last Theorem for
Matan Eliashar, Nati Linial
Fermat's Last theorem (FLT) famously states that the equation has no solution in positive integers for any integer exponent . But does this theorem hav…
Linear Programming Hierarchies in Coding Theory: Dual Solutions
Elyassaf Loyfer, Nati Linial
The rate vs. distance problem is a long-standing open problem in coding theory. Recent papers have suggested a new way to tackle this problem by appealing to a new hierarchy of lin…
An approach to the girth problem in cubic graphs
Aya Bernstine, Nati Linial
We offer a new, gradual approach to the largest girth problem for cubic graphs. It is easily observed that the largest possible girth of all -vertex cubic graphs is attained by…
New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes
Elyassaf Loyfer, Nati Linial
We develop a new family of linear programs, that yield upper bounds on the rate of binary linear codes of a given distance. Our bounds apply {\em only to linear codes.} Delsarte's…
Larger Corner-Free Sets from Better NOF Exactly- Protocols
Nati Linial, Adi Shraibman
A subset of the integer planar grid is called corner-free if it contains no triple of the form . It is known that such a set has a vanishi…
Hyperpaths
Amir Dahari, Nati Linial
Hypertrees are high-dimensional counterparts of graph theoretic trees. They have attracted a great deal of attention by various investigators. Here we introduce and study Hyperpath…
Geodesic Geometry on Graphs
Daniel Cizma, Nati Linial
We investigate a graph theoretic analog of geodesic geometry. In a graph we consider a system of paths where connects vertice…
On the weight distribution of random binary linear codes
Nati Linial, Jonathan Mosheiff
We investigate the weight distribution of random binary linear codes. For and pick uniformly at random vectors in and let $C \le \mathbb{…
Universal Knot Diagrams
Chaim Even-Zohar, Joel Hass, Nati Linial +1
We study collections of planar curves that yield diagrams for all knots. In particular, we show that a very special class called potholder curves carries all knots. This has implic…
Efficient Generation of One-Factorizations through Hill Climbing
Maya Dotan, Nati Linial
It is well known that for every even integer , the complete graph has a one-factorization, namely a proper edge coloring with colors. Unfortunately, not much is kn…
Random simplicial complexes - around the phase transition
Nati Linial, Yuval Peled
This article surveys some of the work done in recent years on random simplicial complexes. We mostly consider higher-dimensional analogs of the well known phase transition in $G(n,…
On the Rigidity of Sparse Random Graphs
Nati Linial, Jonathan Mosheiff
A graph with a trivial automorphism group is said to be rigid. Wright proved that for a random graph is rigid whp. I…
Invariants of Random Knots and Links
Chaim Even-Zohar, Joel Hass, Nati Linial +1
We study random knots and links in R^3 using the Petaluma model, which is based on the petal projections developed by Adams et al. (2012). In this model we obtain a formula for the…
Extremal problems on shadows and hypercuts in simplicial complexes
Nati Linial, Ilan Newman, Yuval Peled +1
Let be an -vertex forest. We say that an edge is in the shadow of if contains a cycle. It is easy to see that if is "almost a tree", that is…
On the number of 4-cycles in a tournament
Nati Linial, Avraham Morgenstern
If is an -vertex tournament with a given number of -cycles, what can be said about the number of its -cycles? The most interesting range of this problem is where i…