《组合数学》实践性教学研究

《组合数学》是理论和应用结合很强的一门学科。多年的教学经历发现,很多学生并不明白《组合数学》和其他应用学科的关系。文中介绍了教学过程中通过一些典型的实践性问题的解决,使学生能够理解并掌握怎样用组合数学去解决其他学科的问题,同时一些组合数学的问题怎样用其他学科的方法去解决。教学效果表明,文中的实践性教学尝试是成功的。     

The expected profile of digital search trees

A digital search tree (DST) is a fundamental data structure on words that finds various applications from the popular Lempel-Ziv?78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it depends on the number of stored strings and the distance from the root. Most parameters of DST (e.g., depth, height, fillup) can be expressed in terms of the profile. We study here asymptotics of the average profile in a DST built from sequences generated independently by a memoryless source. After representing the average profile by a recurrence, we solve it using a wide range of analytic tools. This analysis is surprisingly demanding but once it is carried out it reveals an unusually intriguing and interesting behavior. The average profile undergoes phase transitions when moving from the root to the longest path: at first it resembles a full tree until it abruptly starts growing polynomially and oscillating in this range. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, poissonization and depoissonization, the saddle point method, singularity analysis and uniform asymptotic analysis.     

The external constraint 4 nonempty part sandwich problem

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K₂-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K₂-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K₂-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.     

The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers

A set A of non‐negative integers is called a Sidon set if all the sums , with and a₁, , are distinct. A well‐known problem on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of . Results of Chowla, Erd?s, Singer and Turán from the 1940s give that . We study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ by a sparse, random subset R of , and ask how large a subset can be, if we require that S should be a Sidon set. Let be a random subset of of cardinality , with all the subsets of equiprobable. We investigate the random variable , where the maximum is taken over all Sidon subsets , and obtain quite precise information on for the whole range of m, as illustrated by the following abridged version of our results. Let be a fixed constant and suppose . We show that there is a constant such that, almost surely, we have . As it turns out, the function is a continuous, piecewise linear function of a that is non‐differentiable at two ‘critical’ points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function is constant. Our approach is based on estimating the number of Sidon sets of a given cardinality contained in [n]. Our estimates also directly address a problem raised by Cameron and Erd?s (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61–79). © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 1–25, 2015     

How many T‐tessellations on k lines? Existence of associated Gibbs measures on bounded convex domains

The paper bounds the number of tessellations with T‐shaped vertices on a fixed set of k lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a completely random T‐tessellation, as defined by Kiêu et al. (Spat Stat 6 (2013) 118–138), and of its Gibbsian modifications. The combinatorial bound is sharp, but likely pessimistic in typical cases. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 561–587, 2015     

Failure probability estimation with differently sized reference products for semiconductor burn‐in studies

A burn‐in study is applied to demonstrate compliance with a targeted early life failure probability of semiconductor products. This is achieved by investigating a sample of the produced chips for reliability‐relevant failures. Usually, a burn‐in study is carried out for a specific reference product with the aim to scale the reference product's failure probability to follower products with different chip sizes. It also appears, however, that there are multiple, differently sized reference products for which burn‐in studies are performed. In this paper, we present a novel model for estimating the failure probability of a chip, which is capable of handling burn‐in studies on multiple reference products. We discuss the model from a combinatorial and a Bayesian perspective; both approaches are shown to provide more accurate estimation results in comparison with a simple area‐based approach. Moreover, we discuss the required modifications of the model if the observed failures are tackled by countermeasures implemented in the chip production process. Finally, the model is applied to the problem of determining the failure probabilities of follower products on the basis of multiple reference products.