## Abstract

For a graph G, let f(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as G ranges over all graphs on m edges that contain no copy of H. In this paper we study this function for various graphs H. In particular we show that for any graph H obtained by connecting a single vertex to all vertices of a fixed nontrivial forest, there is a c(H)> 0 such that f(m,H) ≥ m/2 + c(H)m^{4/5}, and that this is tight up to the value of $c(H)$. We also prove that for any even cycle $C_{2k}$ there is a c(k)> 0 such that f(m,C_{2k}) ≥ m/2 + c(k) m^{(2k+1)/(2k+2)}, and that this is tight, up to the value of $c(k)$, for 2k ∈ {4,6,10\}. The proofs combine combinatorial, probabilistic and spectral techniques.

Original language | English (US) |
---|---|

Pages (from-to) | 629-647 |

Number of pages | 19 |

Journal | Combinatorics Probability and Computing |

Volume | 14 |

Issue number | 5-6 |

DOIs | |

State | Published - Nov 1 2005 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics