Counting cliques in a random graph
We show that the expected number of cliques in the Erdős-Rényi random graph is .
Source author record
Norihide Tokushige
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
5works
2topics
4close collaborators
Published work
5 publications
preprint2016arXiv
Multiply union families in Nn
Let A⊂Nn be an r-wise s-union family, that is, a family of sequences with n components of non-negative integers such that for any r sequences in A the total sum of the maximum of each component in those sequences is at most s. We determine the maximum size of A and its unique extremal configuration provided (i) n is sufficiently large for fixed r and s, or (ii) n=r+1.
Open access
preprint2015arXiv
Towards extending the Ahlswede-Khachatrian theorem to cross t-intersecting families
Ahlswede and Khachatrian's diametric theorem is a weighted version of their complete intersection theorem, itself an extension of the t-intersecting Erdős-Ko-Rado theorem. Their intersection theorem says that the maximum size of a family of subsets of [n]={1,…,n}, every pair of which intersects in at least t elements, is the size of certain trivially intersecting families proposed by Frankl. We address a cross intersecting version of their diametric theorem. Two families A and B of subsets of [n] are {\em cross t-intersecting} if for every A∈A and B∈B, A and B intersect in at least t elements. The p-weight of a k element subset A of [n] is pk(1−p)n−k, and the weight of a family A is the sum of the weights of its sets. The weight of a pair of families is the product of the weights of the families. The maximum p-weight of a t-intersecting family depends on the value of p. Ahlswede and Khachatrian showed that for p in the range [t+2r−1r,t+2r+1r+1], the maximum p-weight of a t-intersecting family is that of the family Frt consisting of all subsets of [n] containing at least t+r elements of the set [t+2r]. In a previous paper we showed a cross t-intersecting version of this for large t in the case that r=0. In this paper, we do the same in the case that r=1. We show that for p in the range [t+11,t+32] the maximum p-weight of a cross t-intersecting pair of families, for t≥200, is achieved when both families are F1t. Further, we show that except at the endpoints of this range, this is, up to isomorphism, the only pair of t-intersecting families achieving this weight.
Open access
preprint2014arXiv
An Erd\H os--Ko--Rado theorem for cross t-intersecting families
Two families A and B, of k-subsets of an n-set, are {\em cross t-intersecting} if for every choice of subsets A∈A and B∈B we have ∣A∩B∣≥t. We address the following conjectured cross t-intersecting version of the Erd\H os--Ko--Rado Theorem: For all n≥(t+1)(k−t+1) the maximum value of ∣A∣∣B∣ for two cross t-intersecting families A,B⊂(k[n]) is (k−tn−t)2. We verify this for all t≥14 except finitely many n and k for each fixed t. Further, we prove uniqueness and stability results in these cases, showing, for instance, that the families reaching this bound are unique up to isomorphism. We also consider a {\em p-weight} version of the problem, which comes from the product measure on the power set of an n-set.
Open access
preprint2011arXiv
Application of arrangement theory to unfolding models
Arrangement theory plays an essential role in the study of the unfolding model used in many fields. This paper describes how arrangement theory can be usefully employed in solving the problems of counting (i) the number of admissible rankings in an unfolding model and (ii) the number of ranking patterns generated by unfolding models. The paper is mostly expository but also contains some new results such as simple upper and lower bounds for the number of ranking patterns in the unidimensional case.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.