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: 433–437.
  • [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. 3–110.
  • [3] Bouaziz M, Boudabbous Y, El Amri N. Hereditary hemimorphy of {−k}-hemimorphic tournaments for k ≥ 5. J Korean Math Soc 2011; 48: 599–626.
  • [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: 109–112. (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: 841–844. (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: 1037–1040. (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: 845–848. (article in French with an abstract in English)
  • [8] Boudabbous Y, Lopez G. The minimal non-(≤ k )-reconstructible relations. Discrete Math 2005; 291: 19–40.
  • [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: 125–128. (article in French with an abstract in English)
  • [10] Chung FRK, Graham RL. Cohomological aspects of hypergraphs. Trans Amer Math Soc 1992; 334: 365–388.
  • [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: 181–199. (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: 209–236. (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: 84–96.
  • [14] Ehrenfeucht A, Rozenberg G. Primitivity is hereditary for 2-structures. Theoret Comput Sc 1990; 70: 343–358.
  • [15] Fine NJ. Binomial coefficients modulo a prime. American Mathematical Monthly 1947; 54: 589–592.
  • [16] Fra¨ıss´e R. L’intervalle en th´eorie des relations; ses g´en´eralisations; filtre intervallaire et clˆoture d’une 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; L’Arbresle, France. Amsterdam: North-Holland, 1984, pp. 313–341. (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: 85–94.
  • [18] Gallai T. Transitiv orientierbare graphen. Acta Math Acad Sci Hungar 1967; 18: 25–66.
  • [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: 1233–1237.
  • [21] Ille P. Indecomposable graphs. Discrete Math. 1997; 173: 71–78.
  • [22] Kantor W. On incidence matrices of finite projection and affine spaces. Math Zeitschrift 1972; 124: 315–318.
  • [23] Kelly D. Comparability graphs. In: Rival I, editor. Graphs and Orders; 1984; Banff, Alta. Drodrecht: Reidel, 1985, pp. 3–40.
  • [24] Kelly PJ. A congruence theorem for trees. Pacific J Math 1957; 7: 961–968.
  • [25] Lopez G. Deux r´esultats concernant la d´etermination d’une relation par les types d’isomorphie de ses restrictions. C R Acad Sci Paris, S´er A 1972; 274: 1525–1528. (in French)
  • [26] Lopez G. Sur la d´etermination d’une relation par les types d’isomorphie de ses restrictions. C R Acad Sci Paris, S´er A 1972; 275: 951–953. (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: 27–37.
  • [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: 157–168.
  • [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: 49–54. (in French)
  • [30] Moon JW. Topics on tournaments. New York-Montreal: Holt, Rinehart and Winston, 1968.
  • [31] Pouzet M. Application d’une propri´et´e combinatoire des parties d’un ensemble aux groupes et aux relations. Math Zeitschrift 1976; 150: 117–134. (in French)
  • [32] Pouzet M. Relations non reconstructibles par leurs restrictions. JCTB, Series B 1979; 26: 22–34. (in French)
  • [33] Ramsey FP. On a problem of formal logic. Proc London Math Soc 1976; S2-30: 264–286.
  • [34] Schmerl JH, Trotter WT. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discrete Math 1993; 113: 191–205.
  • [35] Spinard P. P4-trees and substitution decomposition. Discrete Appl Math 1992; 39: 263–291.
  • [36] Wilson RM. A diagonal form for the incidence matrices of t-subsets vs. k -subsets. Europ J Combinatorics 1990; 11: 609–615.