Binary codes and partial permutation decoding sets from the odd graphs

For k ≥ 1, the odd graph denoted by O(k), is the graph with the vertex-set Ω^{k}, the set of all k-subsets of Ω = {1, 2, …, 2k +1}, and any two of its vertices u and v constitute an edge [u, v] if and only if u ∩ v = /0. In this paper the binary code generated by the adjacency matrix of O(k) is studied. The automorphism group of the code is determined, and by identifying a suitable information set, a 2-PD-set of the order of k ⁴ is determined. Lastly, the relationship between the dual code from O(k) and the code from its graph-theoretical complement $\overline {O(k)} $ , is investigated.     

A random construction for permutation codes and the covering radius

We analyse a probabilistic argument that gives a semi-random construction for a permutation code on n symbols with distance n − s and size Θ(s!(log n)^1/2), and a bound on the covering radius for sets of permutations in terms of a certain frequency parameter.      

Information sets and partial permutation decoding for codes from finite geometries

We determine information sets for the generalized Reed–Muller codes and use these to apply partial permutation decoding to codes from finite geometries over prime fields. We also obtain new bases of minimum-weight vectors for the codes of the designs of points and hyperplanes over prime fields.     

Invariant Gaussian processes and independent sets on regular graphs of large girth

We prove that every 3‐regular, n‐vertex simple graph with sufficiently large girth contains an independent set of size at least 0.4361n. (The best known bound is 0.4352n.) In fact, computer simulation suggests that the bound our method provides is about 0.438n. Our method uses invariant Gaussian processes on the d‐regular tree that satisfy the eigenvector equation at each vertex for a certain eigenvalue . We show that such processes can be approximated by i.i.d. factors provided that . We then use these approximations for to produce factor of i.i.d. independent sets on regular trees. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 284–303, 2015     

Hall sets,Lazard sets and comma-free codes

We investigate the relationship between two constructions of maximal comma-free codes described, respectively, by Eastman and by Scholtz and the notions of Hall sets and Lazard sets introduced in connection with factorizations of free monoids and bases of free Lie algebras.     

Galois theory for sets of operations closed under permutation,cylindrification, and composition

A set of operations on A is shown to be the set of linear term operations of some algebra on A if and only if it is closed under permutation of variables, addition of inessential variables, and composition, and if it contains all projections. A Galois framework is introduced to describe the sets of operations that are closed under the operations mentioned above, not necessarily containing all projections. The dual objects of this Galois connection are systems of pointed multisets, and the Galois closed sets of dual objects are described accordingly. Moreover, the closure systems associated with this Galois connection are shown to be uncountable (even if the closed sets of operations are assumed to contain all projections).     

On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.     

Maximal and extremal singular graphs

A graph G is singular if the nullspace of its adjacency matrix is nontrivial. Such a graph contains induced subgraphs called singular configurations of nullity 1. We present two algorithms. One is for the construction of a maximal singular nontrivial graph G containing an induced subgraph, which is a singular configuration with the support of a vector in its nullspace as in that of G. The second is for the construction of a nut graph, a graph of nullity one whose null vector has no zero entries. An extremal singular graph of a given order, with the maximal nullity and support, has a nut graph as a maximal singular configuration.     

Reed-Muller codes and permutation decoding

We show that the first- and second-order Reed-Muller codes, R(1,m) and R(2,m), can be used for permutation decoding by finding, within the translation group, (m−1)- and (m+1)-PD-sets for R(1,m) for m≥5,6, respectively, and (m−3)-PD-sets for R(2,m) for m≥8. We extend the results of Seneviratne [P. Seneviratne, Partial permutation decoding for the first-order Reed-Muller codes, Discrete Math., 309 (2009), 1967-1970].     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

Loops,regular permutation sets and graph colourings

We establish a correspondence among loops, regular permutation sets and directed graphs with a suitable edge colouring and relate some algebraic properties of the loop to configurations of the associated graph.     

Binary permutation sequences as subsets of Levenshtein codes,spectral null codes,run-length limited codes and constant weight codes

We investigate binary sequences which can be obtained by concatenating the columns of (0,1)-matrices derived from permutation sequences. We then prove that these binary sequences are subsets of a surprisingly diverse ensemble of codes, namely the Levenshtein codes, capable of correcting insertion/deletion errors; spectral null codes, with spectral nulls at certain frequencies; as well as being subsets of run-length limited codes, Nyquist null codes and constant weight codes. This paper was presented in part at the IEEE Information Theory Workshop, Chengdu, China, October, 2006.     

Binary extremal self-dual codes of length 60 and related codes

We give a classification of four-circulant singly even self-dual [60, 30, d] codes for \(d=10\) and 12. These codes are used to construct extremal singly even self-dual [60, 30, 12] codes with weight enumerator for which no extremal singly even self-dual code was previously known to exist. From extremal singly even self-dual [60, 30, 12] codes, we also construct optimal singly even self-dual [58, 29, 10] codes with weight enumerator for which no optimal singly even self-dual code was previously known to exist. Finally, we give some restriction on the possible weight enumerators of certain singly even self-dual codes with shadow of minimum weight 1.