A framework for constructing partial geometric difference sets

Partial geometric difference sets (PGDSs) were defined in Olmez (J Combin Des 22(6):252–269, 2014). They are used to construct partial geometric designs. We use the framework of extended building sets to find infinite families of PGDSs in abelian groups. Included in our new families of PGDSs are generalizations of the Hadamard, McFarland, Spence, Davis-Jedwab, and Chen difference sets.     

New partial geometric difference sets and partial geometric difference families

Using Galois rings and Galois fields, we construct several infinite classes of partial geometric difference sets, and partial geometric difference families, with new parameters. Furthermore, these partial geometric difference sets (and partial geometric difference families) correspond to new infinite families of directed strongly regular graphs. We also discuss some of the links between partially balanced designs, 2-adesigns (which were recently coined by Cunsheng Ding in “Codes from Difference Sets” (2015)), and partial geometric designs, and make an investigation into when a 2-adesign is a partial geometric design.     

On topological and geometric (194) configurations

An $\left(n_k\right)$ configuration is a set of  $n$ points and  $n$ lines such that each point lies on  $k$ lines while each line contains  $k$ points. The configuration is geometric, topological, or combinatorial depending on whether lines are considered to be straight lines, pseudolines, or just combinatorial lines. The existence and enumeration of $\left(n_k\right)$ configurations for a given  $k$ has been subject to active research. A current front of research concerns geometric $\left(n_4\right)$ configurations: it is now known that geometric $\left(n_4\right)$ configurations exist for all  $n\ge 18$, apart from sporadic exceptional cases. In this paper, we settle by computational techniques the first open case of $\left(19_4\right)$ configurations: we obtain all topological $\left(19_4\right)$ configurations among which none are geometrically realizable.     

Existence and non-existence results for strong external difference families

We consider strong external difference families (SEDFs); these are external difference families satisfying additional conditions on the patterns of external differences that occur, and were first defined in the context of classifying optimal strong algebraic manipulation detection codes. We establish new necessary conditions for the existence of $(n,m,k,\lambda )$-SEDFs; in particular giving a near-complete treatment of the $\lambda =2$ case. For the case $m=2$, we obtain a structural characterization for partition type SEDFs (of maximum possible $k$ and $\lambda$), showing that these correspond to Paley partial difference sets. We also prove a version of our main result for generalized SEDFs, establishing non-trivial necessary conditions for their existence.     

Determinacy of refinements to the difference hierarchy of co-analytic sets

In this paper we develop a technique for proving determinacy of classes of the form ${\omega }^2\text{-}{\mathrm{\Pi }}_1^1+\mathrm{\Gamma }$ (a refinement of the difference hierarchy on ${\mathrm{\Pi }}_1^1$ lying between ${\omega }^2\text{-}{\mathrm{\Pi }}_1^1$ and $({\omega }^2+1)\text{-}{\mathrm{\Pi }}_1^1$) from weak principles, establishing upper bounds for the determinacy-strength of the classes ${\omega }^2\text{-}{\mathrm{\Pi }}_1^1+{\mathrm{\Sigma }}_{\alpha }^0$ for all computable α and of ${\omega }^2\text{-}{\mathrm{\Pi }}_1^1+{{\mathrm{\Delta }}^1}_1$. This bridges the gap between previously known hypotheses implying determinacy in this region.     

Constructions for optimal cyclic ternary constant-weight codes of weight four and distance six

A cyclic ${(n,d,w)}_q$ code is a $q$-ary cyclic code of length $n$, minimum Hamming distance $d$ and weight $w$. In this paper, we investigate cyclic ${(n,6,4)}_3$ codes. A new upper bound on $C{A}_3(n,6,4)$, the largest possible number of codewords in a cyclic ${(n,6,4)}_3$ code, is given. Two new constructions for optimal cyclic ${(n,6,4)}_3$ codes based on cyclic $(n,4,1)$ difference packings are presented. As a consequence, the exact value of $C{A}_3(n,6,4)$ is determined for any positive integer $n\equiv 0,6,18(mod24)$. We also obtain some other infinite classes of optimal cyclic ${(n,6,4)}_3$ codes.     

Small Kakeya sets in non-prime order planes

The finite field analog of the classical Kakeya problem asks the smallest possible size for a set of points in the Desarguesian affine plane which contains a line in every direction. This problem has been definitively solved by Blokhuis and Mazzocca (2008), who show that in $AG(2,s)$, $s$ a prime power, the smallest possible size of such a set is $\frac{1}{2}s(s+1)$. In this paper we examine a new construction of an infinite family of sets in $AG(2,s)$ containing a line in every direction, where $s=q^e$ with $q$ a prime power and $e$ an integer with $e>1$. These sets have size $\frac{1}{2}{q}^{2e}+O\left(q^{2e-1}\right)$, which is small in the sense that the lower bound is also $\frac{1}{2}{q}^{2e}$ plus smaller order terms. In addition, we discuss the minimality of our sets, showing that they contain no proper subset containing a line in every direction.     

Subspace partitions of Fqn containing direct sums

Let $q$ be a prime power and $n$ be a positive integer. A subspace partition of $V={\mathbb{F}}_q^n$, the vector space of dimension $n$ over ${\mathbb{F}}_q$, is a collection $\Pi$ of subspaces of $V$ such that each nonzero vector of $V$ is contained in exactly one subspace in $\Pi$; the multiset of dimensions of subspaces in $\Pi$ is then called a Gaussian partition of $V$. We say that $\Pi$contains a direct sum if there exist subspaces $W_1,\dots ,W_k\in \Pi$ such that $W_1\oplus ?\oplus W_k=V$. In this paper, we study the problem of classifying the subspace partitions that contain a direct sum. In particular, given integers $a_1$ and $a_2$ with $n>a_1>a_2\ge 1$, our main theorem shows that if $\Pi$ is a subspace partition of ${\mathbb{F}}_q^n$ with $m_i$ subspaces of dimension $a_i$ for $i=1,2$, then $\Pi$ contains a direct sum when $a_1{x}_1+a_2{x}_2=n$ has a solution $(x_1,x_2)$ for some integers $x_1,x_2\ge 0$ and $m_2$ belongs to the union $I$ of two natural intervals. The lower bound of $I$ captures all subspace partitions with dimensions in $\{a_1,a_2\}$ that are currently known to exist. Moreover, we show the existence of infinite classes of subspace partitions without a direct sum when $m_2?I$ or when the condition on the existence of a nonnegative integral solution $(x_1,x_2)$ is not satisfied. We further conjecture that this theorem can be extended to any number of distinct dimensions, where the number of subspaces in each dimension has appropriate bounds. These results offer further evidence of the natural combinatorial relationship between Gaussian and integer partitions (when $q\to 1$) as well as subspace and set partitions.     

Further results on (v,4,1)-perfect difference families

In this paper, it is shown that an ASP$(2r+1,3)$ exists for $2\le r\le 100$ and $r\ne 4,5$. The existence of a $(v,4,1)$-PDF is investigated by taking advantage of the relationship between ASPs and perfect difference families (PDFs). It is proved that a $(12t+1,4,1)$-PDF exists for $t\le 100$ and $t\ne 2,3$. Several recursive constructions for ASPs and PDFs are also presented. As a consequence, the existence results of an optimal $(v,4,1)$-OOC is updated.     

An infinite family of cubic nonnormal Cayley graphs on nonabelian simple groups

We construct a connected cubic nonnormal Cayley graph on ${\mathrm{A}}_{2^m?1}$ for each integer $m?4$ and determine its full automorphism group. This is the first infinite family of connected cubic nonnormal Cayley graphs on nonabelian simple groups.     

Lower bounds on the maximum number of non-crossing acyclic graphs

This paper is a contribution to the problem of counting geometric graphs on point sets. More concretely, we look at the maximum numbers of non-crossing spanning trees and forests. We show that the so-called double chain point configuration of $N$ points has $\Omega \left(12.52^N\right)$ non-crossing spanning trees and $\Omega \left(13.61^N\right)$ non-crossing forests. This improves the previous lower bounds on the maximum number of non-crossing spanning trees and of non-crossing forests among all sets of $N$ points in general position given by Dumitrescu, Schulz, Sheffer and Tóth (2013). Our analysis relies on the tools of analytic combinatorics, which enable us to count certain families of forests on points in convex position, and to estimate their average number of components. A new upper bound of $O\left(22.12^N\right)$ for the number of non-crossing spanning trees of the double chain is also obtained.