On a generalization of Kelly's combinatorial lemma
On a generalization of Kelly's combinatorial lemma
Kelly s combinatorial lemma is a basic tool in the study of Ulam s reconstruction conjecture. A generalization in terms of a family of t-elements subsets of a v -element set was given by Pouzet. We consider a version of this generalization modulo a prime p. We give illustrations to graphs and tournaments
___
- [1] Achour M, Boudabbous Y, Boussairi A. Les paires de tournois {−3}-hypomorphes [Pairs of {−3}-hypomorphic tournaments]. C R Math Acad Sci Paris 2012; 350: 433437.
- [2] Bondy JA. Basic graph theory: paths and circuits, Handbook of combinatorics, Vol. 1, Ed. Graham RL, Gr¨otschel M and Lov´asz L. North-Holland, 1995, pp. 3110.
- [3] Bouaziz M, Boudabbous Y, El Amri N. Hereditary hemimorphy of {−k}-hemimorphic tournaments for k ≥ 5. J Korean Math Soc 2011; 48: 599626.
- [4] Bouchaala H. Sur la r´epartition des diamants dans un tournoi [Distribution of diamonds in a tournament]. C R Math Acad Sci Paris 2004; 338: 109112. (article in French with an abstract in English)
- [5] Boudabbous Y. Isomorphie h´er´editaire et {−4}-hypomorphie pour les tournois [Hereditary isomorphy and {−4}- hypomorphy for tournaments]. C R Math Acad Sci Paris 2009; 347: 841844. (article in French with an abstract in English)
- [6] Boudabbous Y, Dammak J. Sur la (−k )-demi-reconstructibilit´e des tournois finis [On the (−k )-halfreconstructibility of finite tournaments]. C R Acad Sci Paris S´er I Math 1998; 326: 10371040. (article in French with an abstract in English)
- [7] Boudabbous Y, Lopez G. Proc´ed´e de construction des relations binaires non (≤ 3 )-reconstructibles [A construction process for non-(≤ 3 )-reconstructible binary relations]. C R Acad Sci Paris S´er I Math 1999; 329: 845848. (article in French with an abstract in English)
- [8] Boudabbous Y, Lopez G. The minimal non-(≤ k )-reconstructible relations. Discrete Math 2005; 291: 1940.
- [9] Boussa¨ıri A, Ille P, Lopez G, Thomass´e S. Hypomorphie et inversion locale entre graphes [Hypomorphy and local inversion between graphs]. C. R. Acad Sci Paris S´er I Math. 1993; 317: 125128. (article in French with an abstract in English)
- [10] Chung FRK, Graham RL. Cohomological aspects of hypergraphs. Trans Amer Math Soc 1992; 334: 365388.
- [11] Dammak J. La (−5 )-demi-reconstructibilit´e des relations binaires connexes finies [The (−5 )-half-reconstructibility of finite connected binary relations]. Proyecciones 2003; 22: 181199. (article in French with an abstract in English)
- [12] Dammak J. Le seuil de reconstructibilit´e par le haut modulo la dualit´e des relations binaires finies [Threshold of top-down reconstruction of finite binary relations modulo duality]. Proyecciones 2003; 22: 209236. (article in French with an abstract in English)
- [13] Dammak J, Lopez G, Pouzet M, Si Kaddour H. Hypomorphy of graphs up to complementation. JCTB, Series B 2009; 99: 8496.
- [14] Ehrenfeucht A, Rozenberg G. Primitivity is hereditary for 2-structures. Theoret Comput Sc 1990; 70: 343358.
- [15] Fine NJ. Binomial coefficients modulo a prime. American Mathematical Monthly 1947; 54: 589592.
- [16] Fra¨ıss´e R. Lintervalle en th´eorie des relations; ses g´en´eralisations; filtre intervallaire et cloture dune relation [The interval in relation theory; its generalizations; interval filter and closure of a relation]. In: Pouzet M, Richard D, editors. Orders: Description and Roles; 1982; LArbresle, France. Amsterdam: North-Holland, 1984, pp. 313341. (article in French with an abstract in English)
- [17] Frankl P. Intersection theorems and mod p rank of inclusion matrices. J Combin Theory Ser A 1990; 54: 8594.
- [18] Gallai T. Transitiv orientierbare graphen. Acta Math Acad Sci Hungar 1967; 18: 2566.
- [19] Godsil C, Royle G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.
- [20] Gottlieb DH. A certain class of incidence matrices. Proc Amer Math Soc 1966; 17: 12331237.
- [21] Ille P. Indecomposable graphs. Discrete Math. 1997; 173: 7178.
- [22] Kantor W. On incidence matrices of finite projection and affine spaces. Math Zeitschrift 1972; 124: 315318.
- [23] Kelly D. Comparability graphs. In: Rival I, editor. Graphs and Orders; 1984; Banff, Alta. Drodrecht: Reidel, 1985, pp. 340.
- [24] Kelly PJ. A congruence theorem for trees. Pacific J Math 1957; 7: 961968.
- [25] Lopez G. Deux r´esultats concernant la d´etermination dune relation par les types disomorphie de ses restrictions. C R Acad Sci Paris, S´er A 1972; 274: 15251528. (in French)
- [26] Lopez G. Sur la d´etermination dune relation par les types disomorphie de ses restrictions. C R Acad Sci Paris, S´er A 1972; 275: 951953. (in French)
- [27] Lopez G, Rauzy C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n − 1). I. Z Math Logik Grundlag Math 1992; 38: 2737.
- [28] Lopez G, Rauzy C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n − 1). II. Z Math Logik Grundlag Math 1992; 38: 157168.
- [29] Lucas E. Sur les congruences des nombres eul´eriens et les coefficients diff´erentiels des fonctions trigonom´etriques suivant un module premier. Bull. Soc. Math. France 1878; 6: 4954. (in French)
- [30] Moon JW. Topics on tournaments. New York-Montreal: Holt, Rinehart and Winston, 1968.
- [31] Pouzet M. Application dune propri´et´e combinatoire des parties dun ensemble aux groupes et aux relations. Math Zeitschrift 1976; 150: 117134. (in French)
- [32] Pouzet M. Relations non reconstructibles par leurs restrictions. JCTB, Series B 1979; 26: 2234. (in French)
- [33] Ramsey FP. On a problem of formal logic. Proc London Math Soc 1976; S2-30: 264286.
- [34] Schmerl JH, Trotter WT. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discrete Math 1993; 113: 191205.
- [35] Spinard P. P4-trees and substitution decomposition. Discrete Appl Math 1992; 39: 263291.
- [36] Wilson RM. A diagonal form for the incidence matrices of t-subsets vs. k -subsets. Europ J Combinatorics 1990; 11: 609615.