Advanced Combinatorial Mathematics
364 papers on this topic
Turán graphs with bounded matching number
We determine the maximum possible number of edges of a graph with $n$ vertices, matching number at most $s$ and clique number at most $k$ for all admissible values of the parameters.
Strong blocking sets and minimal codes from expander graphs
A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining...
The hull of two classical propagation rules and their applications
In this work, we study and determine the dimensions of Euclidean and Hermitian hulls of two classical propagation rules, namely, the direct sum construction and the...
Quaternary linear codes and related binary subfield codes
In this paper, we mainly study quaternary linear codes and their binary subfield codes. First we obtain a general explicit relationship between quaternary linear codes and their binary subfield...
Contracted Product of Hypermatrices via STP of Matrices
An equivalent definition of hypermatrices is introduced. The matrix expression of hypermatrices is proposed. Using permutation matrices, the conversion of different matrix expressions is revealed....
Computing error bounds for asymptotic expansions of regular P-recursive sequences
Over the last several decades, improvements in the fields of analytic combinatorics and computer algebra have made determining the asymptotic behaviour of sequences satisfying linear recurrence...
ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In general, a...
Hypercubes and Isometric Words based on Swap and Mismatch Distance
The hypercube of dimension n is the graph whose vertices are the 2^n binary words of length n, and there is an edge between two of them if they have Hamming distance 1. We consider an edit...
Higher-Order MDS Codes
An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters [n,k,d] and the list size L. L-MDS codes are then defined as codes...
Erd\H{o}s Matching Conjecture for almost perfect matchings
In 1965 Erd\H{o}s asked, what is the largest size of a family of $k$-element subsets of an $n$-element set that does not have a matching of size $s+1$? In this note, we improve upon a recent...
On the Hat Guessing Number of Graphs
The hat guessing number $HG(G)$ of a graph $G$ on $n$ vertices is defined in terms of the following game: $n$ players are placed on the $n$ vertices of $G$, each wearing a hat whose color is...
t-design curves and mobile sampling on the sphere
In analogy to classical spherical t-design points, we introduce the concept of t-design curves on the sphere. This means that the line integral along a t-design curve integrates polynomials of...
Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings
We show that the threshold for the binomial random $3$-partite, $3$-uniform hypergraph $G^{3}((n,n,n),p)$ to contain a Latin square is $Θ(\log{n}/n)$. We also prove analogous results for Steiner...
Some punctured codes of several families of binary linear codes
Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by $\mathcal{C}(f)=\left\{ {\rm Tr}(af(x)+bx)_{x...
More on Change-Making and Related Problems
Given a set of $n$ integer-valued coin types and a target value $t$, the well-known change-making problem asks for the minimum number of coins that sum to $t$, assuming an unlimited number of...
Bent Functions in the Partial Spread Class Generated by Linear Recurring Sequences
We present a construction of partial spread bent functions using subspaces generated by linear recurring sequences (LRS). We first show that the kernels of the linear mappings defined by two LRS...
Linear Layouts of Bipartite Planar Graphs
A linear layout of a graph $ G $ consists of a linear order $\prec$ of the vertices and a partition of the edges. A part is called a queue (stack) if no two edges nest (cross), that is, two edges...
Excluding Single-Crossing Matching Minors in Bipartite Graphs
\noindent By a seminal result of Valiant, computing the permanent of $(0,1)$-matrices is, in general, $\#\mathsf{P}$-hard. In 1913 P\'olya asked for which $(0,1)$-matrices $A$ it is possible to...