Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-11T22:32:41.665Z 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: victor.falgas-ravry@math.umu.se)
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.

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 

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