Partite Saturation Problems |
| |
| Authors: | Barnaby Roberts |
| |
| Affiliation: | DEPARTMENT OF MATHEMATICS, LONDON SCHOOL OF ECONOMICS, LONDON, UNITED KINGDOM |
| |
| Abstract: | ![]()
We look at several saturation problems in complete balanced blow‐ups of graphs. We let  denote the blow‐up of H onto parts of size n and refer to a copy of H in  as partite if it has one vertex in each part of  . We then ask how few edges a subgraph G of  can have such that G has no partite copy of H but such that the addition of any new edge from  creates a partite H. When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in 5 . Our main result is to calculate this value for  when n is large. We also give exact results for paths and stars and show that for 2‐connected graphs the answer is linear in n whilst for graphs that are not 2‐connected the answer is quadratic in n. We also investigate a similar problem where G is permitted to contain partite copies of H but we require that the addition of any new edge from  creates an extra partite copy of H. This problem turns out to be much simpler and we attain exact answers for all cliques and trees. |
| |
| Keywords: | graph saturation extremal graph theory |
|
|
denote the blow‐up of H onto parts of size n and refer to a copy of H in 
as partite if it has one vertex in each part of 
. We then ask how few edges a subgraph G of 
can have such that G has no partite copy of H but such that the addition of any new edge from 
creates a partite H. When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in 5 . Our main result is to calculate this value for 
when n is large. We also give exact results for paths and stars and show that for 2‐connected graphs the answer is linear in n whilst for graphs that are not 2‐connected the answer is quadratic in n. We also investigate a similar problem where G is permitted to contain partite copies of H but we require that the addition of any new edge from 
creates an extra partite copy of H. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.