Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T01:05:03.295Z Has data issue: false hasContentIssue false
  • English
  • Français

G-Intersection Theorems for Matchings and Other Graphs

Published online by Cambridge University Press:  01 July 2008

J. ROBERT JOHNSON  and
JOHN TALBOT
J. ROBERT JOHNSON
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK (e-mail: r.johnson@qmul.ac.uk)
JOHN TALBOT
Affiliation:
Department of Mathematics, University College London, London WC1E 6BT, UK (e-mail: talbot@math.ucl.ac.uk)
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.

If G is a graph with vertex set [n] then $\mathcal{A}\subseteq 2^{[n]}$ is G-intersecting if, for all $A,B\in \mathcal{A}$, either A ∩ B ≠ ∅ or there exist a ∈ A and b ∈ B such that a ~Gb.

The question of how large a k-uniform G-intersecting family can be was first considered by Bohman, Frieze, Ruszinkó and Thoma [2], who identified two natural candidates for the extrema depending on the relative sizes of k and n and asked whether there is a sharp phase transition between the two. Our first result shows that there is a sharp transition and characterizes the extremal families when G is a matching. We also give an example demonstrating that other extremal families can occur.

Our second result gives a sufficient condition for the largest G-intersecting family to contain almost all k-sets. In particular we show that if Cn is the n-cycle and k > αn + o(n), where α = 0.266. . . is the smallest positive root of (1 − x)3(1 + x) = 1/2, then the largest Cn-intersecting family has size $(1-o(1))\binom{n}{k}$.

Finally we consider the non-uniform problem, and show that in this case the size of the largest G-intersecting family depends on the matching number of G.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 559 - 575
Copyright
Copyright © Cambridge University Press 2008

References

[1]Azuma, K. (1967) Weighted sums of certain dependent random variables. Tôhoku Math. J. 19 357–367.CrossRefGoogle Scholar
[2]Bohman, T., Frieze, A., Ruszinkó, M. and Thoma, L. (2000) G-intersecting families. Combin. Probab. Comput. 10 376–384.Google Scholar
[3]Bohman, T. and Martin, R. (2003) A note on G-intersecting families. Discrete. Math. 260 183–188.CrossRefGoogle Scholar
[4]Bollobás, B. (1986) Combinatorics, Cambridge University Press.Google Scholar
[5]Erőos, P. L., Frankl, P. and Katona, G. O. H. (1985) Extremal hypergraph problems and convex hulls. Combinatorica 5 11–26.Google Scholar
[6]Erőos, P., Ko, C. and Rado, R. (1961) Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. 2 12 313–320.Google Scholar
[7]Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13–30.CrossRefGoogle Scholar