New constructions for perfect hash families and related structures using combinatorial designs and codes

In this paper, we consider explicit constructions of perfect hash families using combinatorial methods. We provide several direct constructions from combinatorial structures related to orthogonal arrays. We also simplify and generalize a recursive construction due to Atici, Magliversas, Stinson and Wei [3]. Using similar methods, we also obtain efficient constructions for separating hash families which result in improved existence results for structures such as separating systems, key distribution patterns, group testing algorithms, cover‐free families and secure frameproof codes. © 2000 John Wiley & Sons, Inc. J Combin Designs 8:189–200, 2000     

Cyclic polytopes, hyperplanes, and Gray codes

We consider cyclic d-polytopes P that are realizable with vertices on the moment curve $M_d:t\longrightarrow (t,t^2,\ldots,t^d)$ of order $d\geq 3$. A hyperplane H bisects a j-face of P if H meets its relative interior. For $\ell\geq 1$, we investigate the maximum number of vertices that P can have so that for some $\ell$ hyperplanes, each j-face of P is bisected by one of the hyperplanes. For $\ell > 1$, the problem translates to the existence of certain codes, or equivalently, certain paths on the cube $\{0,1\}^\ell$.     

On the power of white pebbles

We construct a family (G _p |p) of directed acyclic graphs such that any black pebble strategy forG _p requiresp ² pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.Supported by the National Science Foundation under contract no. DCR-8407256 and by the office of Naval Research under contract no. N0014-80-0517.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

Recursive constructions for difference matrices and relative difference families

We present a new recursive construction for difference matrices whose application allows us to improve some results by D. Jungnickel. For instance, we prove that for any Abelian p-group G of type (n₁, n₂, …, n_t) there exists a (G, p^e, 1) difference matrix with e = Also, we prove that for any group G there exists a (G, p, 1) difference matrix where p is the smallest prime dividing |G|. Difference matrices are then used for constructing, recursively, relative difference families. We revisit some constructions by M. J. Colbourn, C. J. Colbourn, D. Jungnickel, K. T. Phelps, and R. M. Wilson. Combining them we get, in particular, the existence of a multiplier (G, k, λ)-DF for any Abelian group G of nonsquare-free order, whenever there exists a (p, k, λ)-DF for each prime p dividing |G|. Then we focus our attention on a recent construction by M. Jimbo. We improve this construction and prove, as a corollary, the existence of a (G, k, λ)-DF for any group G under the same conditions as above. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 165–182, 1998     

On the recognition complexity of some graph properties

By applying a topological approach due to Kahn, Saks and Sturtevant, we prove that all decreasing graph properties consisting of bipartite graphs only are elusive. This is an analogue to a well-known result of Yao.     

Spectral properties of threshold functions

We examine the spectra of boolean functions obtained as the sign of a real polynomial of degreed. A tight lower bound on various norms of the lowerd levels of the function's Fourier transform is established. The result is applied to derive best possible lower bounds on the influences of variables on linear threshold functions. Some conjectures are posed concerning upper and lower bounds on influences of variables in higher order threshold functions.Supported by an Eshkol fellowship, administered by the National Council for Research and Development—Israel Ministry of Science and Development.     

The asymmetric leader election algorithm: Number of survivors near the end of the game

The following classical asymmetric leader election algorithm has obtained quite a bit of attention lately. Starting with n players, each one throws a coin, and the k of them which have each thrown a head (with probability q) go on, and the leader will be found amongst them, using the same strategy. Should nobody advance, the party will repeat the procedure. One of the most interesting parameter here is the number J (n) of rounds until a leader has been identified. In this paper we investigate, in the classical leader election algorithm, what happens near the end of the game, namely we fix an integer κ and we study the behaviour of the number of survivors L at level J (n) ? κ. In our asymptotic analysis (for n → ∞) we are focusing on the limiting distribution functions. We also investigate what happens, if the parameter p = 1 ? q gets small (p → 0) or large (p → 1). We use three e?cient tools: an urn model, a Mellin-Laplace technique for harmonic sums and some asymptotic distributions related to one of the extreme-value distributions: the Gumbel law. This study was motivated by a recent paper by Kalpathy, Mahmoud and Rosenkrantz, where they consider the number of survivors S_n,t, after t election rounds, in a broad class of fair leader election algorithms starting with n candidates.     

( d, m )-dominating numbers of hypercube

This paper shows that the (d, m)-dominating number of the m-dimensional hypercube Q _m (m≥4) is 2 for any integer d. . The project supported by NSFC and NSFJS.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

The complexity of detecting crossingfree configurations in the plane

The computational complexity of the following type of problem is studied. Given a geometric graphG=(P, S) whereP is a set of points in the Euclidean plane andS a set of straight (closed) line segments between pairs of points inP, we want to know whetherG possesses a crossingfree subgraph of a special type. We analyze the problem of detecting crossingfree spanning trees, one factors and two factors in the plane. We also consider special restrictions on the slopes and on the lengths of the edges in the subgraphs.Klaus Jansen acknowledges support by the Deutsche Forschungsgemeinschaft. Gerhard J. Woeginger acknowledges support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Explicit constructions of separating hash families from algebraic curves over finite fields

Let X be a set of order n and Y be a set of order m. An (n,m,{w ₁, w ₂})-separating hash family is a set of N functions from X to Y such that for any with , |X ₁| = w ₁ and |X ₂| = w ₂, there exists an element such that . In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w ₁,w ₂})–separating hash families with for fixed m, w ₁, and w ₂. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound , which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].     

Dense sets and embedding binary trees into hypercubes

The purpose of this paper is to describe a method for embedding binary trees into hypercubes based on an iterative embedding into their subgraphs induced by dense sets. As a particular application, we present a class of binary trees, defined in terms of size of their subtrees, whose members allow a dilation two embedding into their optimal hypercubes. This provides a partial evidence in favor of a long-standing conjecture of Bhatt and Ipsen which claims that such an embedding exists for an arbitrary binary tree.     

Some constructions of linearly optimal group codes

We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]_q-codes over F_q for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring F_qG where G is an elementary abelian group of order q.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

Cyclotomic graphs and perfect codes

We study two families of cyclotomic graphs and perfect codes in them. They are Cayley graphs on the additive group of $\mathbb{Z}[{\zeta }_m]/A$, with connection sets $\{\pm ({\zeta }_m^i+A):0\le i\le m?1\}$ and $\{\pm ({\zeta }_m^i+A):0\le i\le ?(m)?1\}$, respectively, where ${\zeta }_m$ ($m\ge 2$) is an mth primitive root of unity, A a nonzero ideal of $\mathbb{Z}[{\zeta }_m]$, and ? Euler's totient function. We call them the mth cyclotomic graph and the second kind mth cyclotomic graph, and denote them by $G_m(A)$ and $G_m^{?}(A)$, respectively. We give a necessary and sufficient condition for $D/A$ to be a perfect t-code in $G_m^{?}(A)$ and a necessary condition for $D/A$ to be such a code in $G_m(A)$, where $t\ge 1$ is an integer and D an ideal of $\mathbb{Z}[{\zeta }_m]$ containing A. In the case when $m=3,4$, $G_m((\alpha ))$ is known as an Eisenstein–Jacobi and Gaussian networks, respectively, and we obtain necessary conditions for $(\beta )/(\alpha )$ to be a perfect t-code in $G_m((\alpha ))$, where $0\ne \alpha ,\beta \in \mathbb{Z}[{\zeta }_m]$ with β dividing α. In the literature such conditions are known to be sufficient when $m=4$ and $m=3$ under an additional condition. We give a classification of all first kind Frobenius circulants of valency 2p and prove that they are all pth cyclotomic graphs, where p is an odd prime. Such graphs belong to a large family of Cayley graphs that are efficient for routing and gossiping.     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

A simulation tool for the performance evaluation of parallel branch and bound algorithms

Parallel computation offers a challenging opportunity to speed up the time consuming enumerative procedures that are necessary to solve hard combinatorial problems. Theoretical analysis of such a parallel branch and bound algorithm is very hard and empirical analysis is not straightforward because the performance of a parallel algorithm cannot be evaluated simply by executing the algorithm on a few parallel systems. Among the difficulties encountered are the noise produced by other users on the system, the limited variation in parallelism (the number of processors in the system is strictly bounded) and the waste of resources involved: most of the time, the outcomes of all computations are already known and the only issue of interest is when these outcomes are produced.We will describe a way to simulate the execution of parallel branch and bound algorithms on arbitrary parallel systems in such a way that the memory and cpu requirements are very reasonable. The use of simulation has only minor consequences for the formulation of the algorithm.     

On the spanning trees of weighted graphs

Given a weighted graph, letW ₁,W ₂,W ₃,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weightW ₁ is at mostk–1 edge swaps away from some spanning tree of weightW _k . Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weightW _k .This work was supported in part by a grant from the AT&T foundation and NSF grant DCR-8351757.Primarily supported by a 1967 Science and Engineering Scholarship from the Natural Sciences and Engineering Research Council of Canada.     

On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.