Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-14T03:24:30.838Z Has data issue: false hasContentIssue false
  • English
  • Français

Sperner's Problem for G-Independent Families

Published online by Cambridge University Press:  15 October 2014

VICTOR FALGAS-RAVRY
VICTOR FALGAS-RAVRY*
Affiliation:
Institutionen för matematik och matematisk statistik, Umeå Universitet, 901 87 Umeå, Sweden (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G. We consider the problem of determining the size of a largest antichain in Q(G). When G is the edgeless graph, this problem is resolved by Sperner's theorem. In this paper, we focus on the case where G is the path of length n − 1, proving that the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

Keywords

Primary 05D05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 3 , May 2015 , pp. 528 - 550
Copyright
Copyright © Cambridge University Press 2014 

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.)

References

[1]Bollobás, B. (1965) On generalized graphs. Acta Mathematica Hungarica 16 447–452.Google Scholar
[2]Cohen, G., Fachini, E. and Körner, J. (2010) Skewincidence. IEEE Trans. Inform. Theory 57 7313–7316.Google Scholar
[3]Dilworth, R. P. (1950) A decomposition theorem for partially ordered sets. Ann. of Math. 51 161–166.CrossRefGoogle Scholar
[4]Engel, K. (1997) Sperner Theory, Cambridge University Press.Google Scholar
[5]Erdős, P., Ko, C. and Rado, R. (1961) Intersection theorems for systems of finite sets. Quart. J. Math. 12 313–320.CrossRefGoogle Scholar
[6]Hall, M. (1948) Distinct representatives of subsets. Bull. Amer. Math. Soc. 54 922–926.Google Scholar
[7]Holroyd, F. C. (1999) Problem 338 (BCC16. 25): Erdős–Ko–Rado at the court of King Arthur. Discrete Math. 197 812.Google Scholar
[8]Hsu, W. J. (1993) Fibonacci cubes: A new interconnection topology. IEEE Trans. Parallel and Distributed Systems 4 3–12.Google Scholar
[9]Hsu, W. J., Chung, M. J. and Das, A. (1997) Linear recursive networks and their applications in distributed systems. IEEE Trans. Parallel and Distributed Systems 8 673–680.Google Scholar
[10]Katona, G. O. H. (1968) A theorem of finite sets. In Theory of Graphs (Erdős, P. and Katona, G. O. H., eds), Academic Press, pp. 187–207.Google Scholar
[11]Kruskal, J. B. (1963) The number of simplices in a complex. In Mathematical Optimization Techniques (Bellman, R., ed.), University of California Press, pp. 251–278.CrossRefGoogle Scholar
[12]Lubell, D. (1966) A short proof of Sperner's lemma. J. Combin. Theory 1 299.CrossRefGoogle Scholar
[13]Meshalkin, L. D. (1963) Generalization of Sperner's theorem on the number of subsets of a finite set. Theory Probab. Appl. 8 203–204.Google Scholar
[14]Schrijver, A. (1978) Vertex-critical subgraphs of Kneser graphs. Nieuw Archief voor Wiskunde 26 454–461.Google Scholar
[15]Sperner, E. (1928) Ein Satz über Untermengen einer endlichen Menge (in German). Mathematische Zeitschrift 27 544–548.Google Scholar
[16]Stojmenovic, I. (1998) Optimal deadlock-free routing and broadcasting on Fibonacci cube networks. Utilitas Math. 53 159–166.Google Scholar
[17]Talbot, J. (2001) Lagrangians of hypergraphs and other combinatorial results. PhD thesis, University College London.Google Scholar
[18]Talbot, J. (2003) Intersecting families of separated sets. J. London Math. Soc. 68 37–51.Google Scholar
[19]Yamamoto, K. (1954) Logarithmic order of free distributive lattice. J. Math. Soc. Japan 6 343–353.Google Scholar