Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-25T18:28:46.483Z Has data issue: false hasContentIssue false
  • English
  • Français

Weakly Saturated Hypergraphs and Exterior Algebra

Published online by Cambridge University Press:  12 December 2001

OLEG PIKHURKO
OLEG PIKHURKO
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, University of Cambridge, Cambridge CB3 0WB, United Kingdom; (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Given an r-graph F, an r-graph G is called weakly F-saturated if the edges missing from G can be added, one at a time, in some order, each extra edge creating a new copy of F. Let w-sat(n, F) be the minimal size of a weakly F-saturated graph of order n. We compute the w-sat function for a wide class of r-graphs called pyramids: these include many examples for which the w-sat function was known, as well as many new examples, such as the computation of w-sat(n,Ks + Kt), and enable us to prove a conjecture of Tuza.

Our main technique, developed from ideas of Kalai, is based on matroids derived from exterior algebra. We prove that if it succeeds for some graphs then the same is true for the ‘cones’ and ‘joins’ of such graphs, so that the w-sat function can be computed for many graphs that are built up from certain elementary graphs by these operations.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 10 , Issue 5 , September 2001 , pp. 435 - 451
Copyright
2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)