The combinatorics of N.G. de Bruijn

In memoriam: N.G. de Bruijn.     

Eine Bemerkung zu einem Ergebnis von N. G. de Bruijn

Ohne Zusammenfassung     

Early work of N.G. (Dick) de Bruijn in analysis and some of my own

There are parallels between de Bruijn’s early work in analysis and that of the author. However, Dick’s work soon became much broader and deeper. While the present paper reviews several topics of common interest, its main content is a short version of Dick’s important article related to Riemann’s Hypothesis, entitled ‘The roots of trigonometric integrals’ [N.G. de Bruijn, The roots of trigonometric integrals, Duke Math. J. 17 (1950) 197–226]. The associated ‘de Bruijn–Newman constant’ is also discussed.     

The directed genus of the de Bruijn graph

Define the directed genus, Γ(G), of an Eulerian digraph G to be the minimum value of p for which G has a 2-cell embedding in the orientable surface of genus p so that every face of the embedding is bounded by a directed circuit in G. The directed genus of the de Bruijn graph D_n is shown to be

     

N.G. de Bruijn’s contribution to the formalization of mathematics

N.G. (Dick) de Bruijn was the first to develop a formal language suitable for the complete expression of a mathematical subject matter. His formalization does not only regard the usual mathematical expressions, but also all sorts of meta-notions such as definitions, substitutions, theorems and even complete proofs. He envisaged (and demonstrated) that a full formalization enables one to check proofs automatically by means of a computer program. He started developing his ideas about a suitable formal language for mathematics in the end of the 1960s, when computers were still in their infancy. De Bruijn was ahead of his time and much of his work only became known to a wider audience much later. In the present paper we highlight de Bruijn’s contributions to the formalization of mathematics, directed towards verification by a computer, by placing these in their time and by relating them to parallel and later developments. We aim to explain some of the more technical aspects of de Bruijn’s work to a wider audience of interested mathematicians and computer scientists.     

Independence number of de Bruijn graphs

In this paper, we give several exact values of the independence number of a de Bruijn graph UB(d,D) and in the other cases, we establish pertinent lower and upper bounds of this parameter. We show that asymptotically, if d is even, the ratio of the number of vertices of a greatest independent set of UB(d,D) is .     

Hamiltonicity of large generalized de Bruijn cycles

In this article, we determine when the large generalized de Bruijn cycles are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized cycles. They are Kronecker products of generalized de Bruijn digraphs and dicycles.     

n维有向de Bruijn图和无向de Bruijn图上的随机游动

本文对有向和无向de Bruijn图上的随机游动进行了研究，得出了有向de Bruijn图上简单随机游动任意两点之间平均击中时间的显式表达式，并证明了有向和无向de Bruijn图上随机游动的快速收敛性。     

二元de Bruijn网络的可靠性分析

证明了二元de Bruijn网络是极大限制边连通的,并且它们的最小限制边割只能分离一条孤立边或者一个三角形. 利用此结果分析了二元de Bruijn网络的可靠性,确定了它们的可靠多项式的前四项系数.     

Minimal polynomials of the modified de Bruijn sequences

It is well known that a de Bruijn sequence over has the minimal polynomial (x+1)^d, where 2^n-1+nd2ⁿ-1. We study the minimal polynomials of the modified de Bruijn sequences.     

The Steinhaus theorem and regular variation: de Bruijn and after

The contributions of N.G. de Bruijn to regular variation, and recent developments in this field, are discussed. A new version of the Uniform Convergence Theorem is given.     

Nicolaas Govert de Bruijn,the enchanter of friable integers

N.G. de Bruijn carried out fundamental work on integers having only small prime factors and the Dickman–de Bruijn function that arises on computing the density of those integers. In this he used his earlier work on linear functionals and differential–difference equations. We review his relevant work and also some later improvements by others.     

Hypergraphs and a functional equation of Bouwkamp and de Bruijn

Let . Bouwkamp and de Bruijn found that there exists a power series Ψ(u,v) satisfying the equation . We show that this result can be interpreted combinatorially using hypergraphs. We also explain some facts about Φ(u,0) and Ψ(u,0), shown by Bouwkamp and de Bruijn, by using hypertrees, and we use Lagrange inversion to count hypertrees by number of vertices and number of edges of a specified size.     

广义de Bruijn和Kautz有向图的距离控制数

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .     

Perfect matchings of a graph associated with a binary de Bruijn digraph

Let B_n be the binary de Bruijn digraph of order n and W the quotient set of the set of vertices of B_n with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that (v,u) is an arc of B_n. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.