Lozenge tilings of hexagons with arbitrary dents

Eisenkölbl gave a formula for the number of lozenge tilings of a hexagon on the triangular lattice with three unit triangles removed from along alternating sides. In earlier work, the first author extended this to the situation when an arbitrary set of unit triangles is removed from along alternating sides of the hexagon. In this paper we address the general case when an arbitrary set of unit triangles is removed from along the boundary of the hexagon.     

A short proof of two shuffling theorems for tilings and a weighted generalization

Recently, Lai and Rohatgi discovered a shuffling theorem for lozenge tilings of doubly-dented hexagons, which generalized the earlier work of Ciucu. Later, Lai proved an analogous theorem for centrally symmetric tilings, which generalized some other previous work of Ciucu. In this paper, we give a unified proof of these two shuffling theorems, which also covers the weighted case. Unlike the original proofs, our arguments do not use the graphical condensation method but instead rely on a well-known tiling enumeration formula due to Cohn, Larsen, and Propp. Fulmek independently found a similar proof of Lai and Rohatgi's original shuffling theorem. Our proof also gives a simple explanation for Ciucu's recent conjecture relating the total number and the number of centrally symmetric lozenge tilings.     

Around the q-binomial-Eulerian polynomials

We find a combinatorial interpretation of Shareshian and Wachs’ $q$-binomial-Eulerian polynomials, which leads to an alternative proof of their $q$-$\gamma$-positivity using group actions. Motivated by the sign-balance identity of Désarménien–Foata–Loday for the $(\mathrm{des},\mathrm{inv})$-Eulerian polynomials, we further investigate the sign-balance of the $q$-binomial-Eulerian polynomials. We show the unimodality of the resulting signed binomial-Eulerian polynomials by exploiting their continued fraction expansion and making use of a new quadratic recursion for the $q$-binomial-Eulerian polynomials. We finally use the method of continued fractions to derive a new $(p,q)$-extension of the $\gamma$-positivity of binomial-Eulerian polynomials which involves crossings and nestings of permutations.     

The (p,q) property in families of d-intervals and d-trees

Given integers $p\ge q>1$, a family of sets satisfies the $(p,q)$ property if among any $p$ members of it some $q$ intersect. We prove that for any fixed integer constants $p\ge q>1$, a family of $d$-intervals satisfying the $(p,q)$ property can be pierced by $O\left(d^{\frac{q}{q-1}}\right)$ points, with constants depending only on $p$ and $q$. This extends results of Tardos, Kaiser and Alon for the case $q=2$, and of Kaiser and Rabinovich for the case $p=q=\lceil lo{g}_2(d+2)\rceil$. We further show that similar bounds hold in families of subgraphs of a tree or a graph of bounded tree-width, each consisting of at most $d$ connected components, extending results of Alon for the case $q=2$. Finally, we prove an upper bound of $O\left(d^{\frac{1}{p-1}}\right)$ on the fractional piercing number in families of $d$-intervals satisfying the $(p,p)$ property, and show that this bound is asymptotically sharp.     

An analogue of Furstenberg–Sárközy’s theorem and an alternative solution to Waring’s problem over finite fields

In this paper, we use Cayley digraphs to obtain some new self-contained proofs for Waring’s problem over finite fields, proving that any element of a finite field ${\mathbb{F}}_q$ can be written as a sum of $m$ many $k\text{th}$ powers as long as $q>k^{\frac{2m}{m-1}}$; and we also compute the smallest positive integers $m$ such that every element of ${\mathbb{F}}_q$ can be written as a sum of $m$ many $k\text{th}$ powers for all $q$ too small to be covered by the above mentioned results when $2⩽k⩽37$.In the process of developing the proofs mentioned above, we arrive at another result (providing a finite field analogue of Furstenberg–Sárközy’s Theorem) showing that any subset $E$ of a finite field ${\mathbb{F}}_q$ for which $\left|E\right|>\frac{qk}{\sqrt{q-1}}$ must contain at least two distinct elements whose difference is a $k\text{th}$ power.     

Endomorphisms and cores of quadratic forms graphs in odd characteristic

A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. A graph G is a core if every endomorphism of G is an automorphism. Let ${\mathbb{F}}_q$ be the finite field with q elements where q is a power of an odd prime number. The quadratic forms graph, denoted by $\mathrm{Quad}(n,q)$ where $n\ge 2$, has all quadratic forms on ${\mathbb{F}}_q^n$ as vertices and two vertices f and g are adjacent whenever $\mathrm{rk}(f-g)=1$ or 2. We prove that every $\mathrm{Quad}(n,q)$ is a pseudo-core. Further, when n is even, $\mathrm{Quad}(n,q)$ is a core. When n is odd, $\mathrm{Quad}(n,q)$ is not a core. On the other hand, we completely determine the independence number of $\mathrm{Quad}(n,q)$.     

Highly nonlinear functions over finite fields

We consider a generalisation of a conjecture by Patterson and Wiedemann from 1983 on the Hamming distance of a function from ${\mathbb{F}}_q^n$ to ${\mathbb{F}}_q$ to the set of affine functions from ${\mathbb{F}}_q^n$ to ${\mathbb{F}}_q$. We prove the conjecture for each q such that the characteristic of ${\mathbb{F}}_q$ lies in a subset of the primes with density 1 and we prove the conjecture for all q by assuming the generalised Riemann hypothesis. Roughly speaking, we show the existence of functions for which the distance to the affine functions is maximised when n tends to infinity. This also determines the asymptotic behaviour of the covering radius of the $[q^n,n+1]$ Reed-Muller code over ${\mathbb{F}}_q$ and so answers a question raised by Leducq in 2013. Our results extend the case $q=2$, which was recently proved by the author and which corresponds to the original conjecture by Patterson and Wiedemann. Our proof combines evaluations of Gauss sums in the semiprimitive case, probabilistic arguments, and methods from discrepancy theory.     

Automorphism groups of designs with λ=1

If $G$ is a finite group and $k=q>2$ or $k=q+1$ for a prime power $q$ then, for infinitely many integers $v$, there is a 2-$(v,k,1)$-design $\mathbf{D}$ for which $\mathrm{Aut}\mathbf{D}?G$.     

Fq-linear codes over Fq-algebras

Huffman (2013) [12] studied ${\mathbb{F}}_q$-linear codes over ${\mathbb{F}}_{q^m}$ and he proved the MacWilliams identity for these codes with respect to ordinary and Hermitian trace inner products. Let S be a finite commutative ${\mathbb{F}}_q$-algebra. An ${\mathbb{F}}_q$-linear code over S of length n is an ${\mathbb{F}}_q$-submodule of $S^n$. In this paper, we study ${\mathbb{F}}_q$-linear codes over S. We obtain some bounds on minimum distance of these codes, and some large classes of MDR codes are introduced. We generalize the ordinary and Hermitian trace products over ${\mathbb{F}}_q$-algebras and we prove the MacWilliams identity with respect to the generalized form. In particular, we obtain Huffman's results on the MacWilliams identity. Among other results, we give a theory to construct a class of quantum codes and the structure of ${\mathbb{F}}_q$-linear codes over finite commutative graded ${\mathbb{F}}_q$-algebras.