Your friend is on Instagram notification I have installed Instagram and now it notifies me:


  Your friend bob is on Instagram as bob123.


I don't remember giving it permissions to access my contacts and when I go to Android Settings > Applications > Instagram it does not have any permissions enabled.

How does it know my contacts and how can I disable it? 

Note: I do not have Facebook connected. In fact it has a banner across the top of the app asking if I want to connect Facebook
The notifications indicate people who are friends with you on Facebook. If you used "Sign in with Facebook" option or used the e-mail address to sign up on Instagram that you used to sign up for Facebook too. Instagram is owned by Facebook, so they can know.