# Mathematics - Combinatorics Publications (50) Home Article Categories

## Mathematics - Combinatorics Publications

2017Apr

Over the last decade, Sudoku, a combinatorial number-placement puzzle, has become a favorite pastimes of many all around the world. In this puzzle, the task is to complete a partially filled $9 \times 9$ square with numbers 1 through 9, subject to the constraint that each number must appear once in each row, each column, and each of the nine $3 \times 3$ blocks. Sudoku squares can be considered a subclass of the well-studied class of Latin squares. Read More

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vuskovic. Read More

In this paper, we answer two questions on local $h$-vectors, which were asked by Athanasiadis. First, we characterize all possible local $h$-vectors of quasi-geometric subdivisions of a simplex. Second, we prove that the local $\gamma$-vector of the barycentric subdivision of any CW-regular subdivision of a simplex is nonnegative. Read More

Fillmore Theorem says that if $A$ is a nonscalar matrix of order $n$ over a field $\mathbb{F}$ and $\gamma_1,\ldots,\gamma_n\in \mathbb{F}$ are such that $\gamma_1+\cdots+\gamma_n=\text{tr} \, A$, then there is a matrix $B$ similar to $A$ with diagonal $(\gamma_1,\ldots,\gamma_n)$. Fillmore proof works by induction on the size of $A$ and implicitly provides an algorithm to construct $B$. We develop an explicit and extremely simple algorithm that finish in two steps (two similarities), and with its help we extend Fillmore Theorem to integers (if $A$ is integer then we can require to $B$ to be integer). Read More

2017Apr

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a t-(n,k,{\lambda}) combinatorial design with tiny, yet positive, probability. Herein, we strengthen both the method and the result of Kuperberg, Lovett, and Peled as follows. Read More

2017Apr

Let $\chi_l(G)$ denote the list chromatic number of the $r$-uniform hypergraph~$G$. Extending a result of Alon for graphs, Saxton and the second author used the method of containers to prove that, if $G$ is simple and $d$-regular, then $\chi_l(G)\ge (1/(r-1)+o(1))\log_r d$. To see how close this inequality is to best possible, we examine $\chi_l(G)$ when $G$ is a random $r$-partite hypergraph with $n$ vertices in each class. Read More

Matchings are frequently used to model RNA secondary structures; however, not all matchings can be realized as RNA motifs. One class of matchings, called the L $\&$ P matchings, is the most restrictive model for RNA secondary structures in the Largest Hairpin Family (LHF). The L $\&$ P matchings were enumerated in $2015$ by Jefferson, and they are equinumerous with the set of nesting-similarity classes of matchings, enumerated by Klazar. Read More

Hegyv\'ari and Hennecart showed that if $B$ is a sufficiently large brick of a Heisenberg group, then the product set $B\cdot B$ contains many cosets of the center of the group. We give a new, robust proof of this theorem that extends to all extra special groups as well as to a large family of quasigroups. Read More

In the present work we are going to give a formal exposition of the ribbon graphs topic based on notes of Labourie \cite{Lab}, since is difficult to find as such in the literature. Read More

Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hard-core model and monomer-dimer model are the independence and matching polynomials respectively. We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions. Read More

2017Apr

Foldable paper constructions known as flexagons have been studied since 1939. In this paper we review the construction of hexagonal flexagons (hexaflexagons) and compute the number of distinct hexaflexagons with n faces. Read More

An alternating sign matrix, or ASM, is a $(0, \pm 1)$-matrix where the nonzero entries in each row and column alternate in sign. We generalize this notion to hypermatrices: an $n\times n\times n$ hypermatrix $A=[a_{ijk}]$ is an {\em alternating sign hypermatrix}, or ASHM, if each of its planes, obtained by fixing one of the three indices, is an ASM. Several results concerning ASHMs are shown, such as finding the maximum number of nonzeros of an $n\times n\times n$ ASHM, and properties related to Latin squares. Read More

We continue our investigation of integral spans of tight frames in Euclidean spaces. In a previous paper, we considered the case of an equiangular tight frame (ETF), proving that if its integral span is a lattice then the frame must be rational, but overlooking a simple argument in the reverse direction. Thus our first result here is that the integral span of an ETF is a lattice if and only if the frame is rational. Read More

Using diagrammatic techniques, we provide an explicit proof of the single ring theorem, including the recent extension for the correlation function built out of left and right eigenvectors of a non-Hermitian matrix. We present the operational formalism allowing to map mutually the two distinct areas of free random variables: Hermitian positive definite operators and non-normal R-diagonal operators, realized as the large size limit of biunitarily invariant random matrices. Read More

Let $\mathcal{B}$ denote a set of bicolorings of $[n]$, where each bicoloring is a mapping of the points in $[n]$ to $\{-1,+1\}$. For each $B \in \mathcal{B}$, let $Y_B=(B(1),\ldots,B(n))$. For each $A \subseteq [n]$, let $X_A \in \{0,1\}^n$ denote the incidence vector of $A$. Read More

2017Apr

One of the most intriguing problems, in $q$-analogs of designs, is the existence question of an infinite family of $q$-analog of Steiner systems, known also as $q$-Steiner systems, (spreads not included) in general, and the existence question for the $q$-analog of the Fano plane, known also as the $q$-Fano plane, in particular. These questions are in the front line of open problems in block design. There was a common belief and a conjecture that such structures do not exist. Read More

A pseudocircle is a simple closed curve on some surface. Arrangements of pseudocircles were introduced by Gr\"unbaum, who defined them as collections of pseudocircles that pairwise intersect in exactly two points, at which they cross. There are several variations on this notion in the literature, one of which requires that no three pseudocircles have a point in common. Read More

We give a unified approach to constructing quaternary sequences with even period and low autocorrelation from pairs of binary sequences with even period and optimal autocorrelation. We obtain several families of balanced and almost balanced quaternary sequences with low autocorrelation using this approach, as well as investigate their linear complexity. Read More

2017Apr

Given a metric space $(X,d)$, we say that a mapping $\chi: [X]^{2}\longrightarrow\{0.1\}$ is an isometric coloring if $d(x,y)=d(z,t)$ implies $\chi(\{x,y\})=\chi(\{z,t\})$. A free ultrafilter $\mathcal{U}$ on an infinite metric space $(X,d)$ is called metrically Ramsey if, for every isometric coloring $\chi$ of $[X]^{2}$, there is a member $U\in\mathcal{U}$ such that the set $[U]^{2}$ is $\chi$-monochrome. Read More

In this paper, we describe a general setting for dimer models on cylinders over Dynkin diagrams which in type A reduces to the well studied case of dimer models on a disc. We prove that all Berenstein--Fomin--Zelevinsky quivers for Schubert cells in a symmetric Kac--Moody algebra give rise to dimer models on the cylinder over the corresponding Dynkin diagram. We also give an independent proof of a result of Buan, Iyama, Reiten and Smith that the corresponding superpotentials are rigid using the dimer model structure of the quivers. Read More

The competition between local Brownian roughness and global parabolic curvature experienced in many random interface models reflects an important aspect of the KPZ universality class. It may be summarised by an exponent triple $(1/2,1/3,2/3)$ representing local interface fluctuation, local roughness (or inward deviation) and convex hull facet length. The three effects arise, for example, in droplets in planar Ising models (Alexander, '01, Hammond, '11,'12). Read More

The tree-depth of $G$ is the smallest value of $k$ for which a labeling of the vertices of $G$ with elements from $\{1,\dots,k\}$ exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is $k$-critical if it has tree-depth $k$ and every proper minor of $G$ has smaller tree-depth. Motivated by a conjecture on the maximum degree of $k$-critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Read More

2017Apr

We consider the GF$(4)$-representable matroids with a circuit-hyperplane such that the matroid obtained by relaxing the circuit-hyperplane is also GF$(4)$-representable. We characterize the structure of these matroids as an application of structure theorems for the classes of $U_{2,4}$-fragile and $\{U_{2,5},U_{3,5}\}$-fragile matroids. In addition, we characterize the forbidden submatrices in GF$(4)$-representations of these matroids. Read More

A lattice $d$-simplex is the convex hull of $d + 1$ affinely independent integer points in $\mathbb{R}^d$. It is called empty if it contains no lattice point apart of its $d + 1$ vertices. The classification of empty $3$-simplices is known since $1964$ (White), based on the fact that they all have width one. Read More

For a fixed collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of ${\cal F}$-M-DELETION when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that ${\cal F}$-M-DELETION can be solved in time $f_{{\cal F}}(tw) \cdot n^{O(1)}$ on $n$-vertex graphs. Read More

We define a tournament to be alternation acyclic if it does not contain a cycle in which descents and ascents alternate. Using a result by Athanasiadis on hyperplane arrangements, we show that these tournaments are counted by the median Genocchi numbers. By establishing a bijection with objects defined by Dumont, we show that alternation acyclic tournaments in which at least one ascent begins at each vertex, except for the largest one, are counted by the Genocchi numbers of the first kind. Read More

2017Apr

The \emph{chromatic number} of a digraph $D$ is the minimum number of acyclic subgraphs covering the vertex set of $D$. A tournament $H$ is a \emph{hero} if every $H$-free tournament $T$ has chromatic number bounded by a function of $H$. Inspired by the celebrated Erd\H{o}s--Hajnal conjecture, Berger et al. Read More

In this paper we study the homology of a random Cech complex generated by a homogeneous Poisson process in a compact Riemannian manifold M. In particular, we focus on the phase transition for "homological connectivity" where the homology of the complex becomes isomorphic to that of M. The results presented in this paper are an important generalization of [7], from the flat torus to general compact Riemannian manifolds. Read More

In this short note, we study pairwise edge-disjoint rainbow spanning trees in properly edge-coloured complete graphs, where a graph is rainbow if its edges have distinct colours. Brualdi and Hollingsworth conjectured that every $K_n$ properly edge-coloured by $n-1$ colours has $n/2$ edge-disjoint rainbow spanning trees. Kaneko, Kano and Suzuki later suggested this should hold for every properly edge-coloured $K_n$. Read More

2017Apr

The Ehrhart polynomial and the reciprocity theorems by Ehrhart \& Macdonald are extended to tensor valuations on lattice polytopes. A complete classification is established of tensor valuations of rank up to eight that are equivariant with respect to the special linear group over the integers and translation covariant. Every such valuation is a linear combination of the Ehrhart tensors which is shown to no longer hold true for rank nine. Read More

2017Apr

In the generalized truncation construction, one replaces each vertex of a $k$-regular graph $\Gamma$ with a copy of a graph $\Upsilon$ of order $k$. We investigate the symmetry properties of the graphs constructed in this way, especially in connection to the symmetry properties of the graphs $\Gamma$ and $\Upsilon$ used in the construction. We demonstrate the usefulness of our results by using them to obtain a classification of cubic vertex-transitive graphs of girths $3$, $4$, and $5$. Read More

In this paper, we study the relationship between the radius $r$ and the attachment number $a$ of a tetravalent graph admitting a half-arc-transitive group of automorphisms. These two parameters were first introduced in~[{\em J.~Combin. Read More

We investigate bootstrap percolation with infection threshold $r> 1$ on the binomial $k$-uniform random hypergraph $H_k(n,p)$ in the regime $n^{-1}\ll n^{k-2}p \ll n^{-1/r}$, when the initial set of infected vertices is chosen uniformly at random from all sets of given size. We establish a threshold such that if there are less vertices in the initial set of infected vertices, then whp only a few additional vertices become infected, while if the initial set of infected vertices exceeds the threshold then whp almost every vertex becomes infected. In addition, for $k=2$, we show that the probability of failure decreases exponentially. Read More

2017Apr

We consider special cases of the two tree degree sequences problem. We show that if two tree degree sequences do not have common leaves then they always have edge-disjoint caterpillar realizations. By using a probabilistic method, we prove that two tree degree sequences always have edge-disjoint realizations if each vertex is a leaf in at least one of the trees. Read More

We characterize the class of infinite connected graphs $G$ for which there exists a $T$-join for any choice of an infinite $T \subseteq V(G)$. We also show that the following well-known fact remains true in the infinite case. If $G$ is connected and does not contain a $T$-join, then it will if we either remove an arbitrary vertex from $T$ or add any new vertex to $T$. Read More

We classify the Cohen-Macaulay binomial edge ideals of cactus graphs. Read More

Two mesh patterns are coincident if they are avoided by the same set of permutations, and are Wilf-equivalent if they have the same number of avoiders of each length. We provide sufficient conditions for coincidence of mesh patterns, when only permutations also avoiding a longer classical pattern are considered. Using these conditions we completely classify coincidences between families containing a mesh pattern of length 2 and a classical pattern of length 3. Read More

A general Kneser hypergraph ${\rm KG}^r(\mathcal{H})$ is an $r$-uniform hypergraph that somehow encodes the intersections of a ground hypergraph $\mathcal{H}$. The colorability defect of $\mathcal{H}$ is a combinatorial parameter providing a lower bound for the chromatic number of ${\rm KG}^r(\mathcal{H})$ which is involved in a series of works by Dol'nikov [Sibirskii Matematicheskii Zhurnal, 1988}], K\v{r}\'{\i}\v{z} [Transaction of the American Mathematical Society, 1992], and Ziegler~[Inventiones Mathematicae, 2002]. In this paper, we define a new combinatorial parameter, the equitable colorability defect of hypergraphs, which provides some common improvements of these works. Read More

Dual equivalence graphs are a powerful tool in symmetric function theory that provide a general framework for proving that a given quasisymmetric function is symmetric and Schur positive. In this paper, we study a larger family of graphs that includes dual equivalence graphs and define maps that, in certain cases, transform graphs in this larger family into dual equivalence graphs. This allows us to broaden the applications of dual equivalence graphs and points the way toward a broader theory that could solve many important, long-standing Schur positivity problems. Read More

2017Apr

The union-closed sets conjecture states that if a family of sets $\mathcal{A} \neq \{\emptyset\}$ is union-closed, then there is an element which belongs to at least half the sets in $\mathcal{A}$. In 2001, D. Reimer showed that the average set size of a union-closed family, $\mathcal{A}$, is at least $\frac{1}{2} \log_2 |\mathcal{A}|$. Read More

For a (molecular) graph, the first multiplicative Zagreb index $\prod_1(G)$ is the product of the square of every vertex degree, and the second multiplicative Zagreb index $\prod_2(G)$ is the product of the products of degrees of pairs of adjacent vertices. In this paper, we explore graphs in terms of (edge) connectivity. The maximum and minimum values of $\prod_1(G)$ and $\prod_2(G)$ of graphs with connectivity at most $k$ are provided. Read More

2017Apr

Gomory and Hu proved that if $G$ is a finite graph with non-negative weights on its edges, then there exists a tree $T$ (called now Gomory-Hu tree) on $V(G)$ such that for all $u\neq v\in V(G)$ there is an $e\in E(T)$ such that the two components of $T-e$ determines an optimal (minimal valued) cut between $u$ an $v$ in $G$. In this paper we extend their result to infinite weighted graphs with finite total weight. Furthermore, we show by an example that one can not omit the condition of finiteness of the total weight. Read More

An oriented graph $G^\sigma$ is a digraph without loops or multiple arcs whose underlying graph is $G$. Let $S\left(G^\sigma\right)$ be the skew-adjacency matrix of $G^\sigma$ and $\alpha(G)$ be the independence number of $G$. The rank of $S(G^\sigma)$ is called the skew-rank of $G^\sigma$, denoted by $sr(G^\sigma)$. Read More

A new class of positive definite functions related to colour-length function on arbitrary Coxeter group is introduced. Extensions of positive definite functions, called the Riesz-Coxeter product, from the Riesz product on the Rademacher (Abelian Coxeter) group to arbitrary Coxeter group is obtained. Applications to harmonic analysis, operator spaces and noncommutative probability is presented. Read More

2017Apr

This paper establishes relationships between elliptic functions and Riordan arrays leading to new classes of Riordan arrays which here are called elliptic Riordan arrays. In particular, the case of Riordan arrays derived from Jacobi elliptic functions which are parameterized by the elliptic modulus $k$ will be treated here. Some concrete examples of such Riordan arrays are presented via a recursive formula. Read More

Given a connected graph $R$ on $r$ vertices and a rooted graph $H,$ let $R\{H\}$ be the graph obtained from $r$ copies of $H$ and the graph $R$ by identifying the root of the $i-th$ copy of $H$ with the $i-th$ vertex of $R$. Let $0\leq\alpha\leq1,$ and let $A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G)$ where $D(G)$ and $A(G)$ are the diagonal matrix of the vertex degrees of $G$ and the adjacency matrix of $G$, respectively. A basic result on the $A_{\alpha}-$ spectrum of $R\{H\}$ is obtained. Read More

2017Apr

We introduce a refinement of the Billera, Jia and Reiner quasisymmetric function that carries information of face numbers of generalized permutohedra. This includes a refinement of Stanley's chromatic symmetric function. We consider more systematically the case of matroid base polytopes and obtain the formula for their $f$-polynomials in terms of principal specializations of quasisymmetric enumerators. Read More

We show that by restricting the degrees of the vertices of a graph to an arbitrary set $\Delta$, the threshold point $\alpha(\Delta)$ of the phase transition for a random graph with $n$ vertices and $m = \alpha(\Delta) n$ edges can be either accelerated (e.g., $\alpha(\Delta) \approx 0. Read More 2017Apr A graph$G$is said to be$2$-divisible if for all (nonempty) induced subgraphs$H$of$G$,$V(H)$can be partitioned into two sets$A,B$such that$\omega(A) < \omega(H)$and$\omega(B) < \omega(H)$. A graph$G$is said to be perfectly divisible if for all induced subgraphs$H$of$G$,$V(H)$can be partitioned into two sets$A,B$such that$H[A]$is perfect and$\omega(B) < \omega(H)$. We prove that if a graph is$(P_5,C_5)$-free, then it is$2$-divisible. Read More If$\gcd(r,t)=1$, then a theorem of Alladi offers the M\"obius sum identity $$-\sum_{\substack{ n \geq 2 \\ p_{\rm{min}}(n) \equiv r \pmod{t}}} \mu(n)n^{-1}= \frac{1}{\varphi(t)}.$$ Here$p_{\rm{min}}(n)$is the smallest prime divisor of$n$. The right-hand side represents the proportion of primes in a fixed arithmetic progression modulo$t\$. Read More