Jianguo Qian, Konrad Engel and Wei Xu (Dass et al., 2015) gave a generalization of Sperner’s theorem (Sperner, 1928): n and m are given integers, they found the minimum number of pairs Yi⊆Yj(i≠j) in a multifamily {Y1,…,Ym} of not necessarily different subsets of an n-element set. Here a far reaching generalization and easier proof is given. Let G be a graph and m an integer, choose m vertices with possible repetitions in such a way that the number of adjacent pairs (including the repeated vertices) is minimum. It is proved that the following choice gives the minimum: take the vertices of a largest independent set in G with nearly equal multiplicities.

The Turán number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let Pk be the path with k vertices, the square Pk2 of Pk is obtained by joining the pairs of vertices with distance one or two in Pk. The powerful theorem of Erdős, Stone and Simonovits determines the asymptotic behavior of ex(n,Pk2). In the present paper, we determine the exact value of ex(n,P52) and ex(n,P62) and pose a conjecture for the exact value of ex(n,Pk2).

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(Kn)=n−b(n), where b(n) is the number of 1’s in the binary representation of n. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n−b(n)≤m(G)≤n−1. We show that for any tree T on an even number of vertices we have m(T)=n−1, and that for any tree T on an odd number of vertices, we have n−65≤m(T)≤n−2. Our proof uses results about the weighted version of the problem for Kn, which may be of independent interest. We also exhibit a sequence Gn of graphs with m(Gn)=n−b(n) such that Gn has O(nb(n)) edges and n vertices.

There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein (, 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage.

This is a paper about the beauty of the permutation method. New and shorter proofs are given for the theorem [P. L. Erdos and G. O. H. Katona, J. Combin. Theory. Ser. A, 43 (1986), pp. 58--69; S. Shahriari, Discrete Math., 162 (1996), pp. 229--238] determining all extremal two-part Sperner families and for the uniqueness of k-Sperner families of maximum size [P. Erdos, Bull. Amer. Math. Soc., 51 (1945), pp. 898--902].

Abstract Some connections between extremal set theory and the optimization of the reliability polynomial are shown. Then the concept of the reliability polynomial is generalized for the case when the elements can have three different states: good, mediocre and bad. The state of the device can be described by a 0,1,2 sequence. Such a state is called operative if the device operates when its elements are in the states described by the sequence. The maximum of the generalized reliability polynomial is studied under the condition that the set of operative states froms an antichain. © 1993 by John Wiley & Sons, Inc.

In this paper the connection between the self-information of a source letter from a finite alphabet and its code-word length in a Huffman code is investigated. Consider the set of all independent finite alphabet sources which contain a source letter a of probabilityp. The maximum over this set of the length of a Huffman codeword for a is determined. This maximum remains constant aspvaries between the reciprocal values of two consecutive Fibonacci numbers. For the smallpthis maximum is approximately equal to\left[ \log_{2} \frac{1+ \sqrt{5}}{2} \right]^{-1} \approx 1.44times the self-information.