Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T02:44:31.509Z Has data issue: false hasContentIssue false
  • English
  • Français

G-Intersecting Families

Published online by Cambridge University Press:  12 December 2001

TOM BOHMAN ,
ALAN FRIEZE ,
MIKLÓS RUSZINKÓ  and
LUBOš THOMA
TOM BOHMAN
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, USA; (e-mail: tbohman@moser.math.cmu.edu, alan@random.math.cmu.edu, thoma@andrew.cmu.edu)
ALAN FRIEZE
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, USA; (e-mail: tbohman@moser.math.cmu.edu, alan@random.math.cmu.edu, thoma@andrew.cmu.edu)
MIKLÓS RUSZINKÓ
Affiliation:
Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, PO Box 63, Hungary 1518; (e-mail: ruszinko@sztaki.hu)
LUBOš THOMA
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, USA; (e-mail: tbohman@moser.math.cmu.edu, alan@random.math.cmu.edu, thoma@andrew.cmu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be a graph on vertex set [n], and for X ⊆ [n] let N(X) be the union of X and its neighbourhood in G. A family of sets [Fscr] ⊆ 2[n] is G-intersecting if N(X) ∩ Y ≠ [empty ] for all X, Y ∈ [Fscr]. In this paper we study the cardinality and structure of the largest k-uniform G-intersecting families on a fixed graph G.

Information

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