Combinatorics (math.CO)

Abstract: A $k$-uniform hypergraph is a hypergraph where each $k$-hyperedge has exactly $k$ vertices. A $k$-homogeneous access structure is represented by a $k$-uniform hypergraph $\mathcal{H}$, in which the participants correspond to the vertices of hypergraph $\mathcal{H}$. A set of vertices can reconstruct the secret value from their shares if they are connected by a $k$-hyperedge, while a set of non-adjacent vertices does not obtain any information about the secret. One parameter for measuring the efficiency of a secret sharing scheme is the information rate, defined as the ratio between the length of the secret and the maximum length of the shares given to the participants. Secret sharing schemes with an information rate equal to one are called ideal secret sharing schemes. An access structure is considered ideal if an ideal secret sharing scheme can realize it. Characterizing ideal access structures is one of the important problems in secret sharing schemes. The characterization of ideal access structures has been studied by many authors~\cite{BD, CT,JZB, FP1,FP2,DS1,TD}. In this paper, we characterize ideal $k$-homogeneous access structures using the independent sequence method. In particular, we prove that the reduced access structure of $\Gamma$ is an $(k, n)$-threshold access structure when the optimal information rate of $\Gamma$ is larger than $\frac{k-1}{k}$, where $\Gamma$ is a $k$-homogeneous access structure satisfying specific criteria.

Abstract: Some combinatorial designs, such as Hadamard matrices, have been extensively researched and are familiar to readers across the spectrum of Science and Engineering. They arise in diverse fields such as cryptography, communication theory, and quantum computing. Objects like this also lend themselves to compelling mathematics problems, such as the Hadamard conjecture. However, complex generalized weighing matrices, which generalize Hadamard matrices, have not received anything like the same level of scrutiny. Motivated by an application to the construction of quantum error-correcting codes, which we outline in the latter sections of this paper, we survey the existing literature on complex generalized weighing matrices. We discuss and extend upon the known existence conditions and constructions, and compile known existence results for small parameters. Some interesting quantum codes are constructed to demonstrate their value.

Abstract: We give a construction of a convex set $A \subset \mathbb R$ with cardinality $n$ such that $A-A$ contains a convex subset with cardinality $\Omega (n^2)$. We also consider the following variant of this problem: given a convex set $A$, what is the size of the largest matching $M \subset A \times A$ such that the set \[ \{ a-b : (a,b) \in M \} \] is convex? We prove that there always exists such an $M$ with $|M| \geq \sqrt n$, and that this lower bound is best possible, up a multiplicative constant.

Abstract: We study a number of topics in the theory of Boolean Representable Simplicial Complexes (BRSC). These include various operators on BRSC. We look at shellability in higher dimensions and propose a number of new conjectures.

Abstract: We show that if a Laurent series $f\in\mathbb{C}((t))$ satisfies a particular kind of linear iterative equation, then $f$ is either an algebraic function or it is differentially transcendental over $\mathbb{C}(t)$. This condition is more precisely stated as follows: We consider $R,a,b\in \mathbb{C}(t)$ with $R(0)=0$, such that $f(R(t))=a(t)f(t)+b(t)$. If either $R'(0)=0$ or $R'(0)$ is a root of unity, then either $f$ satisfies a polynomial equation, or $f$ does not satisfy a polynomial differential equation. We illustrate how to apply this result to deduce the differential transcendence of combinatorial generating functions by considering three examples: the ordinary generating function for a family of complete trees; the Green function for excursions on the Sierpinski graph; and a series related to the enumeration of permutations avoiding the consecutive pattern 1423. The proof strategy is inspired by the Galois theory of functional equations, and relies on the property of the dynamics of $R$, Liouville-Rosenlicht's theorem and Ax' theorem.

Abstract: We consider the problem of determining which matrices are permutable to be supmodular. We show that for small dimensions any matrix is permutable by a universal permutation or by a pair of permutations, while for higher dimensions no universal permutation exists. We raise several questions including to determine the dimensions in which every matrix is permutable.

Abstract: Let $\alpha(\mathbb{F}_q^d,p)$ denote the maximum size of a general position set in a $p$-random subset of $\mathbb{F}_q^d$. We determine the order of magnitude of $\alpha(\mathbb{F}_q^2,p)$ up to polylogarithmic factors for all possible values of $p$, improving the previous best upper bounds obtained by Roche-Newton--Warren and Bhowmick--Roche-Newton. For $d \ge 3$ we prove upper bounds for $\alpha(\mathbb{F}_q^d,p)$ that are essentially tight within certain intervals of $p$. We establish the upper bound $2^{(1+o(1))q}$ for the number of general position sets in $\mathbb{F}_q^d$, which matches the trivial lower bound $2^{q}$ asymptotically in exponent. We also refine this counting result by proving an asymptotically tight (in exponent) upper bound for the number of general position sets with fixed size. The latter result for $d=2$ improves a result of Roche-Newton--Warren. Our proofs are grounded in the hypergraph container method, and additionally, for $d=2$ we also leverage the pseudorandomness of the point-line incidence bipartite graph of $\mathbb{F}_{q}^2$.

Abstract: In this paper, we explore combinatorial properties of the posets associated with Kohnert polynomials. In particular, we determine a sufficient condition guaranteeing when such ``Kohnert posets'' are bounded and two necessary conditions for when they are ranked. Moreover, we apply the aforementioned conditions to find complete characterizations of when Kohnert posets are bounded and when they are ranked in special cases, including those associated with Demazure characters.

Abstract: The BG-rank BG($\pi$) of an integer partition $\pi$ is defined as $$\text{BG}(\pi) := i-j$$ where $i$ is the number of odd-indexed odd parts and $j$ is the number of even-indexed odd parts of $\pi$. In a recent work, Fu and Tang ask for a direct combinatorial proof of the following identity of Berkovich and Uncu $$B_{2N+\nu}(k,q)=q^{2k^2-k}\left[\begin{matrix}2N+\nu\\N+k\end{matrix}\right]_{q^2}$$ for any integer $k$ and non-negative integer $N$ where $\nu\in \{0,1\}$, $B_N(k,q)$ is the generating function for partitions into distinct parts less than or equal to $N$ with BG-rank equal to $k$ and $\left[\begin{matrix}a+b\\b\end{matrix}\right]_q$ is a Gaussian binomial coefficient. In this paper, we provide a combinatorial proof of Berkovich and Uncu's identity along the lines of Fu and Tang's idea.

Abstract: A numerical semigroup is a cofinite subset of the non-negative integers that is closed under addition and contains 0. Each numerical semigroup $S$ with fixed smallest positive element $m$ corresponds to an integer point in a rational polyhedral cone $\mathcal C_m$, called the Kunz cone. Moreover, numerical semigroups corresponding to points in the same face $F \subseteq \mathcal C_m$ are known to share many properties, such as the number of minimal generators. In this work, we classify which faces of $\mathcal C_m$ contain points corresponding to numerical semigroups. Additionally, we obtain sharp bounds on the number of minimal generators of $S$ in terms of the dimension of the face of $\mathcal C_m$ containing the point corresponding to $S$.

Abstract: We prove Menger-type results in which the obtained paths are pairwise non-adjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. We further show better bounds in the subcubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.