38 citations · 173 across the 31 of their papers we have counts for
6 papers · 1 filter
A Note on the Inducibility of 4-vertex Graphs
Chaim Even-Zohar, Nati Linial
There is much recent interest in understanding the density at which constant size graphs can appear in a very large graph. Specifically, the inducibility of a graph H is its extrem…
From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, Shai Shalev-Shwartz
The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are efficiently learnable. There is presently a dearth of results showi…
Internal Partitions of Regular Graphs
Amir Ban, Nati Linial
An internal partition of an -vertex graph is a partition of such that every vertex has at least as many neighbors in its own part as in the other part. It has been…
Triply Existentially Complete Triangle-Free Graphs
Chaim Even-Zohar, Nati Linial
A triangle-free graph G is called k-existentially complete if for every induced k-vertex subgraph H of G, every extension of H to a (k+1)-vertex triangle-free graph can be realized…
Graphs with few 3-cliques and 3-anticliques are 3-universal
Nati Linial, Avraham Morgenstern
For given integers k, l we ask whether every large graph with a sufficiently small number of k-cliques and k-anticliques must contain an induced copy of every l-vertex graph. Here…
On high-dimensional acyclic tournaments
Nati Linial, Avraham Morgenstern
We study a high-dimensional analog for the notion of an acyclic (aka transitive) tournament. We give upper and lower bounds on the number of -dimensional -vertex acyclic tour…