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. | Turkish Journal of Mathematics Research Article Turk J Math (2014) 38: 949 – 964 ¨ ITAK ˙ c TUB ⃝ doi: On a generalization of Kelly’s combinatorial lemma Aymen BEN AMIRA1 , Jamel DAMMAK1 , Hamza SI KADDOUR2,∗ 1 Department of Mathematics, Faculty of Sciences of Sfax, Sfax, Tunisia 2 ICJ, Department of Mathematics, University of Lyon, Claude Bernard University Lyon 1, Villeurbanne, France Received: • Accepted: • Published Online: • Printed: Abstract: 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. Key words: Set, matrix, graph, tournament, isomorphism 1. Introduction Kelly’s combinatorial lemma [24] is the assertion that the number s(F, G) of induced subgraphs of a given graph G , isomorphic to F , is determined by the deck of G , provided that |V (F )| ki . t ti ti i=0 For an elementary proof of Theorem , see Fine [15]. As a consequence of Theorem , we have the following result, which is very useful in this paper. Corollary Let p be a prime number, t, k be positive integers, t ≤ k , t = [t0 , t1 , . . . , tt(p) ]p and k = [k0 , k1 , . . . , kk(p) ]p . Then p| (k) t Proof of Theorem . if and only if there is i ∈ {0, 1, . . . , t(p)} such that ti > ki . 1) We prove that under the stated conditions (k−i) t−i ̸≡ 0 (mod p) for every i ∈ {0, . . . , t} . From Theorem it follows that Kerp (t Wt k ) = {0} . Let i ∈ {0, . . . , t} then i = [i0 , i1 , . . . , it(p) ] with it(p) ≤ tt(p) . Since kj = tj for all j ts . We have (t − (ts + 1)ps )s = p − 1, (k − (ts + 1)ps )s = ks − ts − 1 and p − 1 > ks − ts − 1 . From Corollary , ( s) s +1)p p | k−(t , which is impossible. t−(ts +1)ps ( .
