We introduce a new notion called structural abstractions, which is particularly suitable for pebble games over finite ordered graphs. In an example, we show how to apply structural expansions and abstractions in constructions and how to play pebble games over ordered structural abstractions. The proof includes several observations and insights that are fundamental for any games over structural abstractions, which can be used to obtain lower bounds for a number of graph problems with order.
展开▼
