This is known in diplospeak as a casus belli, or a "provocation sufficient to cause a war." There is, of course, wide disagreement between nations (especially those in conflict) on what a casus belli is. Some examples, however, are fairly unsdisputed. The first two below are equivalent to artfuldodger's examples:

  • Territorial encroachment: When the military forces of one nation set foot uninvited on another nation's soil.
  • Bombardment: Any ordnance of one nation detonating on another's soil *or* military forces if the latter are abroad.
  • Attack:Any attempted attack on a nation's military forces at home or abroad. This can get problematic: "Hey! No shooting us! We're going to war!" "But I didn't hit anything! It was a warning shot!" "Bullshit, you just missed is all!" ...etc. etc.

Unfortunately, the true definition of a casus belli is 'whatever the leaders of a nation want it to be,' since they have the power and in most cases authority to begin wars.

This question really leads into the more complicated one of sovereignty. What is a nation? What is a sovereign right or title of that nation? What violates that? For the answers, we'll have to go back as far as the birth of modern sovereignty, the Magna Carta...