Mathematics - Combinatorics Publications (50)

Search

Mathematics - Combinatorics Publications

New lower and upper bounds on the reliability function of typewriter channels are given. Our lower bounds improve upon the (multiletter) expurgated bound of Gallager, furnishing a new and simple counterexample to a conjecture made in 1967 by Shannon, Gallager and Berlekamp on its tightness. The only other known counterexample is due to Katsman, Tsfasman and Vl\u{a}du\c{t} who used algebraic-geometric codes on a $q$-ary symmetric channels, $q\geq 49$. Read More


The feedback arc (vertex) set problem, shortened FASP (FVSP), is to transform a given multi digraph $G=(V,E)$ into an acyclic graph by deleting as few arcs (vertices) as possible. Due to the results of Richard M. Karp in 1972 it is one of the classic NP-complete problems. Read More


This article proves a conjecture by Zuber about the enumeration of fully packed loops (FPLs). The conjecture states that the number of FPLs whose link pattern consists of two noncrossing matchings which are separated by $m$ nested arches is a polynomial function in $m$ of certain degree and with certain leading coefficient. Contrary to the approach of Caselli, Krattenthaler, Lass and Nadeau (who proved a partial result) we make use of the theory of wheel polynomials developed by Di Francesco, Fonseca and Zinn-Justin. Read More


Schnyder woods are particularly elegant combinatorial structures with numerous applications concerning planar triangulations and more generally 3-connected planar maps. We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of any genus with a special emphasis on the toroidal case. We provide a natural partition of the set of Schnyder woods of a given map into distributive lattices depending on the surface homology. Read More


In this paper, we introduce the concept of $k$-clean monomial ideals as an extension of clean monomial ideals and present some homological and combinatorial properties of them. Using the hierarchal structure of $k$-clean ideals, we show that a $(d-1)$-dimensional simplicial complex is $k$-decomposable if and only if its Stanley-Reisner ideal is $k$-clean, where $k\leq d-1$. We prove that the classes of monomial ideals like monomial complete intersection ideals, Cohen-Macaulay monomial ideals of codimension 2 and symbolic powers of Stanley-Reisner ideals of matroid complexes are $k$-clean for all $k\geq 0$. Read More


The only open case of Vizing's conjecture that every planar graph with $\Delta\geq 6$ is a class 1 graph is $\Delta = 6$. We give a short proof of the following statement: there is no 6-critical plane graph $G$, such that every vertex of $G$ is incident to at most three 3-faces. A stronger statement without restriction to critical graphs is stated in \cite{Wang_Xu_2013}. Read More


Strong difference families are an interesting class of discrete structures which can be used to derive relative difference families. Relative difference families are closely related to $2$-designs, and have applications in constructions for many significant codes, such as optical orthogonal codes and optical orthogonal signature pattern codes. In this paper, with a careful use of cyclotomic conditions attached to strong difference families, we improve the lower bound on the asymptotic existence results of $(\mathbb{F}_{q_1}\times \mathbb{F}_{q_2},\mathbb{F}_{q_1}\times \{0\},k,\lambda)$-DFs for $k\in\{q_1,q_1+1\}$. Read More


In 1975 Pippenger and Golumbic proved that any graph on $n$ vertices admits at most $2e(n/k)^k$ induced $k$-cycles. This bound is larger by a multiplicative factor of $2e$ than the simple lower bound obtained by a blow-up construction. Pippenger and Golumbic conjectured that the latter lower bound is essentially tight. Read More


Given the subjective preferences of three roommates, the rent of a 3-bedroom apartment can be divided among the rooms in such a way that the three roommates decide on pairwise distinct rooms and are not envious of each other. We give a simple combinatorial proof of the fact that the subjective preferences of only two of the roommates actually suffice to achieve this envy-free rent division using Sperner's lemma. Our proof, in particular, yields an algorithm to find the fair division of rent. Read More


We study the Koszul property of a standard graded $K$-algebra $R$ defined by the binomial edge ideal of a pair of graphs $(G_1,G_2)$. We show that the following statements are equivalent: (i) $R$ is Koszul; (ii) the defining ideal $J_{G_1,G_2}$ of $R$ has a quadratic Gr\"obner basis; (iii) the graded maximal ideal of $R$ has linear quotients with respect to a suitable order of its generators Read More


Maximal green sequences are important objects in representation theory, cluster algebras, and string theory. It is an open problem to determine what lengths are achieved by the maximal green sequences of a quiver. We combine the combinatorics of surface triangulations and the basics of scattering diagrams to address this problem. Read More


The classification of flag-transitive generalised quadrangles is a long-standing open problem at the interface of finite geometry and permutation group theory. Given that all known flag-transitive generalised quadrangles are also point-primitive (up to point-line duality), it is likewise natural to seek a classification of the point-primitive examples. Working towards this aim, we are led to investigate generalised quadrangles that admit a collineation group $G$ preserving a Cartesian product decomposition of the set of points. Read More


We introduce the notion of a $[z, r; g]$-mixed cage. A $[z, r; g]$-mixed cage is a mixed graph $G$, $z$-regular by arcs, $r$-regular by edges, with girth $g$ and minimum order. In this paper we prove the existence of $[z, r ;g]$-mixed cages and exhibit families of mixed cages for some specific values. Read More


Using jagged overpartitions, we give three generalizations of a weighted word version of Capparelli's identity due to Andrews, Alladi, and Gordon and present several corollaries. Read More


We prove a splitter theorem for tight multimatroids, generalizing the corresponding result for matroids, obtained independently by Brylawski and Seymour. Further corollaries give splitter theorems for delta-matroids and ribbon graphs. Read More


Alladi and Gordon introduced the method of weighted words in 1993 to prove a refinement and generalisation of Schur's partition identity. Together with Andrews, they later used it to refine Capparelli's and G\"ollnitz' identities too. In this paper, we present a new variant of this method, which can be used to study more complicated partition identities, and apply it to prove refinements and generalisations of three partition identities. Read More


We relate the counting of honeycomb dimer configurations on the cylinder to the counting of certain vertices in Kirillov-Reshetikhin crystal graphs. We show that these dimer configurations yield the quantum Kostka numbers of the small quantum cohomology ring of the Grassmannian, i.e. Read More


There are many hard conjectures in graph theory, like Tutte's 5-flow conjecture, and the 5-cycle double cover conjecture, which would be true in general if they would be true for cubic graphs. Since most of them are trivially true for 3-edge-colorable cubic graphs, cubic graphs which are not 3-edge-colorable, often called {\em snarks}, play a key role in this context. Here, we survey parameters measuring how far apart a non 3-edge-colorable graph is from being 3-edge-colorable. Read More


We introduce and analyse an extension of the disjunctive sum operation on some classical impartial games. Whereas the disjunctive sum describes positions formed from independent subpositions, our operation combines positions that are not completely independent but interact only in a very restricted way. We extend the games Nim and Silver Dollar, played by moving counters along one-dimensional strips of cells, by joining several strips at their initial cell. Read More


In this paper, we study divisorial ideals of a Hibi ring which is a toric ring arising from a partially ordered set. We especially characterize the special class of divisorial ideals called conic using the associated partially ordered set. Using our observation of conic divisorial ideals, we also construct a module giving a non-commutative crepant resolution (= NCCR) of the Segre product of polynomial rings. Read More


In recent work it was shown how recursive factorisation of certain QRT maps leads to Somos-4 and Somos-5 recurrences with periodic coefficients, and to a fifth-order recurrence with the Laurent property. Here we recursively factorise the 12-parameter symmetric QRT map, given by a second-order recurrence for a dependent variable $u_n$, to obtain a system of three coupled recurrences which possesses the Laurent property. As degenerate special cases, we derive systems of two coupled recurrences corresponding to the 5-parameter additive and multiplicative symmetric QRT maps. Read More


Let $G$ be a graph, let $k$ be a positive integer, and let $p:V(G)\rightarrow Z_k$ be a mapping with $|E(G)| \stackrel{k}{\equiv}\sum_{v\in V(G)}p(v) $. In this paper, we show that if $G$ is $(3k-3)$-edge-connected, then $G$ has an orientation such that for each vertex $v$, $d^+_G(v)\stackrel{k}{\equiv} p(v)$ and $$\lfloor \frac{d_{G}(v)}{2}\rfloor-(k-1)\le d^+_G(v)\le \lceil \frac{d_{G}(v)}{2}\rceil+(k-1).$$ This result implies that every $(3k-3)$-edge-connected bipartite graph $G$ with the bipartition $(A,B)$ has a factor $H$ such that for every each $v$, $d_H(v)\stackrel{k}{\equiv} f(v)$ and $$\lfloor \frac{d_{G}(v)}{2}\rfloor-(k-1)\le d_H(v)\le \lceil \frac{d_{G}(v)}{2}\rceil+(k-1),$$ where $f:V(G)\rightarrow Z_k$ is a mapping with $\sum_{v\in A}f(v) \stackrel{k}{\equiv}\sum_{v\in B}f(v)$. Read More


We study pretty good quantum state transfer (i.e., state transfer that becomes arbitrarily close to perfect) between vertices of graphs with an involution in the presence of an energy potential. Read More


We compute an explicit $e$-positive formula for the chromatic symmetric function of a lollipop graph, $L_{m,n}$. From here we deduce that there exist countably infinite nonisomorphic $e$-positive, and hence Schur-positive, bases of the algebra of symmetric functions. Finally, we resolve 6 conjectures on the chromatic symmetric function of a lariat graph, $L_{n+3}$. Read More


We study the branching tree of the perimeters of the nested loops in critical $O(n)$ model for $n\in(0,2)$ on random quadrangulations. We prove that after renormalization it converges towards an explicit continuous multiplicative cascade whose offspring distribution $(x_i)_{i \ge 1}$ is related to the jumps of a spectrally positive $\alpha$-stable L\'evy process with $\alpha= \frac{3}{2} \pm \frac{1}{\pi} \arccos(n/2)$ and for which we can compute explicitly the transform $$\mathbb{E}\left[ \sum_{i \ge 1}(x_i)^\theta \right] = \frac{ \sin(\pi(2-\alpha)) }{ \sin(\pi(\theta-\alpha)) } \quad \text{for }\theta \in (\alpha, \alpha+1).$$ An important ingredient in the proof is a new formula on first moments of additive functionals of the jumps of a left-continuous random walk stopped at a hitting time. Read More


The resolutions and maximal sets of compatible resolutions of all 2-(120,8,1) designs arising frommaximal (120,8)-arcs in the known projective planes of order 16 are computed. It is shown that each of these designs is embeddable in a unique way in a projective plane of order 16. Read More


Neural codes are collections of binary strings motivated by patterns of neural activity. In this paper, we study algorithmic and enumerative aspects of convex neural codes in dimension 1 (i.e. Read More


A T-net of order $m$ is a graph with $m$ nodes and $2m$ directed edges, where every node has indegree and outdegree equal to $2$. (A well known example of T-nets are de Bruijn graphs.) Given a T-net $N$ of order $m$, there is the so called "doubling" process that creates a T-net $N^*$ from $N$ with $2m$ nodes and $4m$ edges. Read More


The protection number of a plane tree is the minimal distance of the root to a leaf; this definition carries over to an arbitrary node in a plane tree by considering the maximal subtree having this node as a root. We study the the protection number of a uniformly chosen random tree of size $n$ and also the protection number of a uniformly chosen node in a uniformly chosen random tree of size $n$. The method is to apply singularity analysis to appropriate generating functions. Read More


In this paper, we prove lower and upper bounds on the achromatic and the pseudoachromatic indices of the $n$-dimensional finite projective space of order $q$. Read More


The zero forcing number $Z(G)$ of a graph $G$ is the minimum cardinality of a set $S$ with colored (black) vertices which forces the set $V(G)$ to be colored (black) after some times. "color change rule": a white vertex is changed to a black vertex when it is the only white neighbor of a black vertex. In this case, we say that the black vertex forces the white vertex. Read More


We study the subgraph of the Young-Fibonacci graph induced by elements with odd $f$-statistic (the $f$-statistic of an element $w$ of a differential graded poset is the number of saturated chains from the minimal element of the poset to $w$). We show that this subgraph is a binary tree. Moreover, the odd residues of the $f$-statistics in a row of this tree equidistibute modulo any power two. Read More


An identity of Chung, Graham and Knuth involving binomial coefficients and Eulerian numbers motivates our study of a class of polynomials that we call binomial-Eulerian polynomials. These polynomials share several properties with the Eulerian polynomials. For one thing, they are $h$-polynomials of simplicial polytopes, which gives a geometric interpretation of the fact that they are palindromic and unimodal. Read More


A Cayley graph on a group $G$ has a natural edge-colouring. We say that such a graph is CCA if every automorphism of the graph that preserves this edge-colouring is an element of the normaliser of the regular representation of $G$. A group $G$ is then said to be CCA if every Cayley graph on $G$ is CCA. Read More


We provide an algorithm for sampling the space of abstract simplicial complexes on a fixed number of vertices that aims to provide a balanced sampling over non-isomorphic complexes. Although sampling uniformly from geometrically distinct complexes is a difficult task with no known analytic algorithm, our generative and descriptive algorithm is designed with heuristics to help balance the combinatorial multiplicities of the states and more widely sample across the space of inequivalent configurations. We provide a formula for the exact probabilities with which this algorithm will produce a requested labeled state, and compare the algorithm to Kahle's multi-parameter model of exponential random simplicial complexes, demonstrating analytically that our algorithm performs better with respect to worst-case probability bounds on a given complex and providing numerical results illustrating the increased sampling efficiency over distinct classes. Read More


A $(t, s, v)$-all-or-nothing transform is a bijective mapping defined on $s$-tuples over an alphabet of size $v$, which satisfies the condition that the values of any $t$ input co-ordinates are completely undetermined, given only the values of any $s-t$ output co-ordinates. The main question we address in this paper is: for which choices of parameters does a $(t, s, v)$-all-or-nothing transform (AONT) exist? More specifically, if we fix $t$ and $v$, we want to determine the maximum integer $s$ such that a $(t, s, v)$-AONT exists. We mainly concentrate on the case $t=2$ for arbitrary values of $v$, where we obtain various necessary as well as sufficient conditions for existence of these objects. Read More


In 2013 J. B\"ottcher and J. Foniok proved that the class of all finite permutations has the Ramsey property. Read More


In the present article we introduce two new combinatorial interpretations of the $r$-Whitney numbers of the second kind obtained from the combinatorics of the differential operators associated to the grammar $G:=\{ y\rightarrow yx^{m}, x\rightarrow x\}$. By specializing $m=1$ we obtain also a new combinatorial interpretation of the $r$-Stirling numbers of the second kind. Again, by specializing to the case $r=0$ we introduce a new generalization of the Stirling number of the second kind and through them a binomial type family of polynomials that generalizes Touchard's. Read More


A dynamic coloring of the vertices of a graph $G$ starts with an initial subset $S$ of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set $S$ is called a forcing set of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes colored. Read More


In 1995, Stanley introduced the well-known chromatic symmetric function $X_{G}(x_{1},x_{2},\ldots)$ of a graph $G$. It is a sum of monomial symmetric functions such that for each vertex coloring of $G$ there is exactly one of these summands. The question, whether $X_{G}(x_1,x_{2},\ldots)$ distinguishes nonisomorphic graphs with the same number of vertices, is still open in general. Read More


In this paper we state a problem on rigidity of powers and give a solution of this problem for m=2. Our statement of this problem is elementary enough and does not require any knowledge of algebraic topology. Actually, this problem is related to unitary circle actions, rigid Hirzebruch genera and Kosniowski's conjecture. Read More


An alternative proof is given of the existence of greatest lower bounds in the imbalance order of binary maximal instantaneous codes of a given size. These codes are viewed as maximal antichains of a given size in the infinite binary tree of 0-1 words. The proof proposed makes use of a single balancing operation instead of expansion and contraction as in the original proof of the existence of glb. Read More


In this article, we use the Combinatorial Nullstellensatz to give new proofs of the Cauchy-Davenport, the Dias da Silva-Hamidoune and to generalize a previous addition theorem of the author. Precisely, this last result proves that for a set A $\subset$ Fp such that A $\cap$ (--A) = $\emptyset$ the cardinality of the set of subsums of at least $\alpha$ pairwise distinct elements of A is: |$\Sigma$$\alpha$(A)| $\ge$ min (p, |A|(|A| + 1)/2 -- $\alpha$($\alpha$ + 1)/2 + 1) , the only cases previously known were $\alpha$ $\in$ {0, 1}. The Combinatorial Nullstellensatz is used, for the first time, in a direct and in a reverse way. Read More


We study a recent model for edge exchangeable random graphs introduced by Crane and Dempsey; in particular we study asymptotic properties of the random simple graph obtained by merging multiple edges. We study a number of examples, and show that the model can produce dense, sparse and extremely sparse random graphs. One example yields a power-law degree distribution. Read More


We study four different notions of convergence for graphexes, recently introduced by Borgs, Chayes, Cohn and Holden, and by Veitch and Roy. We give some properties of them and some relations between them. We also extend results by Veitch and Roy on convergence of empirical graphons. Read More


We use the language of precategories to formulate a general mathematical framework for phylogenetics. Read More


Quantum discord refers to an important aspect of quantum correlations for bipartite quantum systems. In our earlier works we have shown that corresponding to every graph (combinatorial) there are quantum states whose properties are reflected in the structure of the corresponding graph. Here, we attempt to develop a graph theoretic study of quantum discord that corresponds to a necessary and sufficient condition of zero quantum discord states which says that the blocks of density matrix corresponding to a zero quantum discord state are normal and commute with each other. Read More


In this paper, we present several upper bounds for the adjacency and signless Laplacian spectral radii of uniform hypergraphs in terms of degree sequences. Read More


A basic combinatorial invariant of a convex polytope $P$ is its $f$-vector $f(P)=(f_0,f_1,\dots,f_{\dim P-1})$, where $f_i$ is the number of $i$-dimensional faces of $P$. Steinitz characterized all possible $f$-vectors of $3$-polytopes and Gr\"unbaum characterized the first two entries of the $f$-vectors of $4$-polytopes. In this paper, we characterize the first two entries of the $f$-vectors of $5$-polytopes. Read More