CyberSec Research

Global permutation patterns have recently been shown to characterize important properties of a Coxeter group. Here we study global patterns in the context of signed permutations, with both characterizing and enumerative results. Surprisingly, many properties of signed permutations may be characterized by avoidance of the same set of patterns as the corresponding properties in the symmetric group. We also extend previous enumerative work of Egge, and our work has connections to the Garfinkle--Barbasch--Vogan correspondence, the Erd\H{o}s--Szekeres theorem, and well-known integer sequences.

We reduce the problem of counting self-avoiding walks in the square lattice to a problem of counting the number of integral points in multidimensional domains. We obtain an asymptotic estimate of the number of self-avoiding walks of length $n$ in the square lattice. This new formalism gives a natural and unified setting in order to study the properties the number of self-avoidings walks in the lattice $\mathbb{Z}^{d}$ of any dimension $d\geq 2$.

Let $G$ be a graph consisting of $s$ odd cycles that all share a common vertex. Bhaskara, Higashitani, and Shibu Deepthi recently computed the $h$-polynomial for the quotient ring $R/I_G$, where $I_G$ is the toric ideal of $G$, in terms of the number and sizes of odd cycles in the graph. The purpose of this note is to prove the stronger result that these toric ideals are geometrically vertex decomposable, which allows us to deduce the result of Bhaskara, Higashitani, and Shibu Deepthi about the $h$-polyhomial as a corollary.

For a simple graph $\Gamma$, a (bipartite)tree-line graph and a tree-graph of $\Gamma$ can be defined. With a (bipartite)tree-line graph constructed by the function $(b)\ell$, we study the continuous quantum walk on $(b)\ell ^n \Gamma$. An equitable partition of a bipartite tree-line graph is obtained by its corresponding derived tree graph. This paper also examines quantum walks on derived graphs, whose vertices represent their basis state.

Suppose $G$ is a controllable graph of order $n$ with adjacency matrix $A$. Let $W=[e,Ae,\ldots,A^{n-1}e]$ ($e$ is the all-one vector) and $\Delta=\prod_{i>j}(\alpha_i-\alpha_j)^2$ ($\alpha_i$'s are eigenvalues of $A$) be the walk matrix and the discriminant of $G$, respectively. Wang and Yu \cite{wangyu2016} showed that if $$\theta(G):=\gcd\{2^{-\lfloor\frac{n}{2}\rfloor}\det W,\Delta\} $$ is odd and squarefree, then $G$ is determined by its generalized spectrum (DGS). Using the primary decomposition theorem, we obtain a new criterion for a graph $G$ to be DGS without the squarefreeness assumption on $\theta(G)$. Examples are further given to illustrate the effectiveness of the proposed criterion, compared with the two existing methods to deal with the difficulty of non-squarefreeness.

Distance-hereditary graphs are known to be the graphs that are totally decomposable for the split decomposition. We characterise distance-hereditary graphs whose complement is also distance-hereditary by their split decomposition and by their modular decomposition.

Substituting each edge of a simple connected graph $G$ by a path of length 1 and $k$ paths of length 5 generates the $k$-hexagonal graph $H^k(G)$. Iterative graph $H^k_n(G)$ is produced when the preceding constructions are repeated $n$ times. According to the graph structure, we obtain a set of linear equations, and derive the entirely normalized Laplacian spectrum of $H^k_n(G)$ when $k = 1$ and $k \geqslant 2$ respectively by analyzing the structure of the solutions of these linear equations. We find significant formulas to calculate the Kemeny's constant, multiplicative degree-Kirchhoff index and number of spanning trees of $H^k_n(G)$ as applications.

We study the enumeration of graph orientations under local degree constraints. Given a finite graph $G = (V, E)$ and a family of admissible sets $\{\mathsf P_v \subseteq \mathbb{Z} : v \in V\}$, let $\mathcal N (G; \prod_{v \in V} \mathsf P_v)$ denote the number of orientations in which the out-degree of each vertex $v$ lies in $P_v$. We prove a general duality formula expressing $\mathcal N(G; \prod_{v \in V} \mathsf P_v)$ as a signed sum over edge subsets, involving products of coefficient sums associated with $\{\mathsf P_v\}_{v \in V}$, from a family of polynomials. Our approach employs gauge transformations, a technique rooted in statistical physics and holographic algorithms. We also present a probabilistic derivation of the same identity, interpreting the orientation-generating polynomial as the expectation of a random polynomial product. As applications, we obtain explicit formulas for the number of even orientations and for mixed Eulerian-even orientations on general graphs. Our formula generalizes a result of Borb\'enyi and Csikv\'ari on Eulerian orientations of graphs.

An equitable coloring of a graph is a proper coloring where the sizes of any two different color classes do not differ by more than one. A graph is IC-planar if it can be drawn in the plane so that no two crossed edges have a common endpoint, and is NIC-planar graphs if it can be embedded in the plane in such a way that no two pairs of crossed edges share two endpoints. Zhang proved that every IC-planar graph with maximum degree $\Delta\geq 12$ and every NIC-planar graph with maximum degree $\Delta\geq 13$ have equitable $\Delta$-colorings. In this paper, we reduce the threshold from 12 to 10 for IC-planar graphs and from 13 to 11 for NIC-planar graphs.

A signed graph is a pair $(G,\sigma)$, where $G$ is a graph and $\sigma: E(G)\rightarrow \{-, +\}$, called signature, is an assignment of signs to the edges. Given a signed graph $(G,\sigma)$ with no negative loops, a balanced $(p,q)$-coloring of $(G,\sigma)$ is an assignment $f$ of $q$ colors to each vertex from a pool of $p$ colors such that each color class induces a balanced subgraph, i.e., no negative cycles. Let $(K_4,-)$ be the signed graph on $K_4$ with all edges being negative. In this work, we show that every signed (simple) subcubic graph admits a balanced $(5,3)$-coloring except for $(K_4,-)$ and signed graphs switching equivalent to it. For this particular signed graph the best balanced colorings are $(2p,p)$-colorings.

The combinatorial discrepancy of arithmetic progressions inside $[N] := \{1, \ldots, N\}$ is the smallest integer $D$ for which $[N]$ can be colored with two colors so that any arithmetic progression in $[N]$ contains at most $D$ more elements from one color class than the other. Bounding the discrepancy of such set systems is a classical problem in discrepancy theory. More recently, this problem was generalized to arithmetic progressions in grids like $[N]^d$ (Valk{\'o}) and $[N_1]\times \ldots \times [N_d]$ (Fox, Xu, and Zhou). In the latter setting, Fox, Xu, and Zhou gave upper and lower bounds on the discrepancy that match within a $\frac{\log |\Omega|}{\log \log |\Omega|}$ factor, where $\Omega := [N_1]\times \ldots \times [N_d]$ is the ground set. In this work, we use the connection between factorization norms and discrepancy to improve their upper bound to be within a $\sqrt{\log|\Omega|}$ factor from the lower bound. We also generalize Fox, Xu, and Zhou's lower bound, and our upper bounds to arithmetic progressions in arbitrary convex bodies.

In 1992, Wagner proved that the Hadamard product of two totally positive lower triangular Toeplitz matrices is totally positive. In this work, we strengthen this result by establishing total monomial positivity for the Hadamard product of Jacobi--Trudi matrices. In particular, we resolve a conjecture of Sokal concerning the Hadamard square of Jacobi--Trudi matrices. Moreover, we provide a manifestly positive Schur expansion for the Hadamard square of Jacobi--Trudi matrices indexed by ribbons. In addition, we construct a corresponding representation, offering a representation-theoretic proof of the Schur positivity.

Endowed with the binary operation of set addition carried over from the integers, the family $\mathcal P_{\mathrm{fin}}(\mathbb Z) $ of all non-empty finite subsets of $\mathbb Z$ forms a monoid whose neutral element is the singleton $\{0\}$. Building upon recent work by Tringali and Yan, we determine the automorphisms of $\mathcal P_{\mathrm{fin}}(\mathbb Z)$. In particular, we find that the automorphism group of $\mathcal P_{\mathrm{fin}}(\mathbb Z)$ is isomorphic to the direct product of a cyclic group of order two by the infinite dihedral group.

We investigate proper $(a:b)$-fractional colorings of $n$-uniform hypergraphs, which generalize traditional integer colorings of graphs. Each vertex is assigned $b$ distinct colors from a set of $a$ colors, and an edge is properly colored if no single color is shared by all vertices of the edge. A hypergraph is $(a:b)$-colorable if every edge is properly colored. We prove that for any $2\leq b\leq a-2\leq n/\ln n$, every $n$-uniform hypergraph $H$ with $ |E(H)| \leq (ab^3)^{-1/2}\left(\frac{n}{\log n}\right)^{1/2} \left(\frac{a}{b}\right)^{n-1} $ is proper $(a:b)$-colorable. We also address specific cases, including $(a:a-1)$-colorability.

We relate the combinatorics of Hall-Littlewood polynomials to that of abelian $p$-groups with alternating or Hermitian perfect pairings. Our main result is an analogue of the classical relationship between the Hall algebra of abelian $p$-groups (without pairings) and Hall-Littlewood polynomials. Specifically, we define a module over the classical Hall algebra with basis indexed by groups with pairings, and explicitly relate its structure constants to Hall-Littlewood polynomials at different values of the parameter $t$. We also show certain expectation formulas with respect to Cohen-Lenstra type measures on groups with pairings. In the alternating case this gives a new and simpler proof of previous results of Delaunay-Jouhet.

Denote by $f_D(n)$ the maximum size of a set family $\mathcal{F}$ on $[n] = \{1, \dots, n\}$ with distance set $D$. That is, $|A \bigtriangleup B| \in D$ holds for every pair of distinct sets $A, B \in \mathcal{F}$. Kleitman's celebrated discrete isodiametric inequality states that $f_D(n)$ is maximized at Hamming balls of radius $d/2$ when $D = \{1, \dots, d\}$. We study the generalization where $D$ is a set of arithmetic progression and determine $f_D(n)$ asymptotically for all homogeneous $D$. In the special case when $D$ is an interval, our result confirms a conjecture of Huang, Klurman, and Pohoata. Moreover, we demonstrate a dichotomy in the growth of $f_D(n)$, showing linear growth in $n$ when $D$ is a non-homogeneous arithmetic progression. Different from previous combinatorial and spectral approaches, we deduce our results by converting the restricted distance problems to restricted intersection problems. Our proof ideas can be adapted to prove upper bounds on $t$-distance sets in Hamming cubes (also known as binary $t$-codes), which has been extensively studied by algebraic combinatorialists community, improving previous bounds from polynomial methods and optimization approaches.

Let $\mathcal{A}$ be an affine hyperplane arrangement, $L(\mathcal{A})$ its intersection poset, and $\chi_{\mathcal{A}}(t)$ its characteristic polynomial. This paper aims to find combinatorial conditions for the factorization of $\chi_{\mathcal{A}}(t)$ and investigate corresponding algebraic interpretations. To this end, we introduce the concept of ideal decomposition in a finite ranked meet-semilattice. Notably, it extends two celebrated concepts: modular element proposed by Stanley in 1971 and nice partition proposed by Terao in 1992. The main results are as follows. An ideal decomposition of $L(\mathcal{A})$ leads to a factorization of its characteristic polynomial $\chi_{\mathcal{A}}(t)$, which is an extension of Terao's factorization under a nice partition. A special type of two-part ideal decomposition, modular ideal, is studied, which extends Stanley's factorization to affine hyperplane arrangements. We also show that any modular ideal of $L(\mathcal{A})$ has a geometric realization. Moreover, we extend Terao's factorization of the Orlik-Solomon algebra for central arrangements, originally induced by modular elements, to arbitrary affine hyperplane arrangements via the modular ideals.

We consider the length of {\em ordered loose paths} in the random $r$-uniform hypergraph $H=H^{(r)}(n, p)$. A ordered loose path is a sequence of edges $E_1,E_2,\ldots,E_\ell$ where $\max\{j\in E_i\}=\min\{j\in E_{i+1}\}$ for $1\leq i<\ell$. We establish fairly tight bounds on the length of the longest ordered loose path in $H$ that hold with high probability.