On the number of combinations without a fixed distance

An explicit formula is derived for the number of k-element subsets A of {1,2,…n} such that no two elements whose difference is q are in A.     

On quantitative aspects of the unit sum number problem

We investigate the function u _K,S (n; q) which counts the number of representations of algebraic integers α with |N_{K/mathbb Q}(a)| ￡ q{|N_{K/{mathbb Q}}(alpha)| leq q} for some real positive q that can be written as sums of exactly n S-units of the number field K.     

Convexity without convex combinations

Separation theorems play a central role in the theory of Functional Inequalities. The importance of Convex Geometry has led to the study of convexity structures induced by Beckenbach families. The aim of the present note is to replace recent investigations into the context of an axiomatic setting, for which Beckenbach structures serve as models. Besides the alternative approach, some new results (whose classical correspondences are well-known in Convex Geometry) are also presented.     

On the number of roots of self-inversive polynomials on the complex unit circle

We present a sufficient condition for a self-inversive polynomial to have a fixed number of roots on the complex unit circle. We also prove that these roots are simple when that condition is satisfied. This generalizes the condition found by Lakatos and Losonczi for all the roots of a self-inversive polynomial to lie on the complex unit circle.     

Teaching about combinations without permutations

In an elementary statistics course, the topic of combinations may be desired for computing the binomial probabilities, but the topic of permutations may be unnecessary. It is possible to explain combinations thoroughly without discussing permutations. The formula for the binomial coefficient is proved for successively larger samples by augmenting the samples of a given size, using the induction principle. For small sample sizes, it is easy to avoid mentioning factorials.     

On the dual Helly number and irreducible decompositions of the unit in lattices

Translated from Matematicheskie Zametki, Vol. 54, No. 3, pp. 34–39, September, 1993.     

On total chromatic number of planar graphs without 4-cycles

Let G be a simple graph with maximum degree A(G) and total chromatic number Xve(G). Vizing conjectured thatΔ(G) 1≤Xve(G)≤Δ(G) 2 (Total Chromatic Conjecture). Even for planar graphs, this conjecture has not been settled yet. The unsettled difficult case for planar graphs isΔ(G) = 6. This paper shows that if G is a simple planar graph with maximum degree 6 and without 4-cycles, then Xve(G)≤8. Together with the previous results on this topic, this shows that every simple planar graph without 4-cycles satisfies the Total Chromatic Conjecture.     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

On the generation of permutations and combinations

In this paper a new method of generating permutations in lexicographical order is developed. Analysis shows that the method is superior to the known method of generation by addition. A simple method of generating combinations is also described.     

On the number of A-mappings

Suppose that $ \mathfrak{S} $ _n is the semigroup of mappings of the set of n elements into itself, A is a fixed subset of the set of natural numbers ?, and V _n (A) is the set of mappings from $ \mathfrak{S} $ _n whose contours are of sizes belonging to A. Mappings from V _n (A) are usually called A-mappings. Consider a random mapping σ _n , uniformly distributed on V n(A). Suppose that ν _n is the number of components and λ _n is the number of cyclic points of the random mapping σ _n . In this paper, for a particular class of sets A, we obtain the asymptotics of the number of elements of the set V _n (A) and prove limit theorems for the random variables ν _n and λ _n as n → ∞.     

On the number of hyperforests

We consider m-forests with n labeled vertices and T edges. Asymptotic expressions for the number of such hyperforests are obtained as m is fixed and n, T→∞ in such a manner that either 0 < α₀ ≤T/n ≤ α₁ < 1/(m(m-1)), where α₀ and α₁ are some constants, or T/n→1/(m(m−1)) sufficiently fast. Proceedings of the XVI Seminar on Stability Problems for Stochastic Models, Part I, Eger, Hungary, 1994.     

On the number of list-colorings

Given a list of boxes L for a graph G (each vertex is assigned a finite set of colors that we call a box), we denote by f(G, L) the number of L-colorings of G (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and of size k, f(G, L) = p(G, k), where P=G, k) is the chromatic polynominal of G. We denote by F(G, k) the minimum of f(G, L) over all the lists of boxes such that each box has size at least k. It is clear that F(G, k) ≤ P(G, k) for all G, k, and we will see in the introduction some examples of graphs such that F(G, k) < P(G, k) for some k. However, we will show, in answer to a problem proposed by A. Kostochka and A. Sidorenko (Fourth Czechoslovak Symposium on Combinatorics, Prachatice, Jin, 1990), that for all G, F(G, k) = P(G, k) for all k sufficiently large. It will follow in particular that F(G, k) is not given by a polynominal in k for all G. The proof is based on the analysis of an algorithm for computing f(G, L) analogous to the classical one for computing P(G, k).