Combinatorics (math.CO)

  • PDF
    In this paper we derive a result that establishes the validity of a model for a basic parameter of a random graph, its degree sequence. Simultaneously, the result gives an asymptotic formula for the number of graphs with given degree sequence, which is also of fundamental importance. The results verify two conjectures of McKay and Wormald made in 1990 and 1997.
  • PDF
    Web crawlers are used by internet search engines to gather information about the web graph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once initial random vertex weights have been assigned, the robot crawler traverses the graph deterministically following a greedy algorithm, always visiting the neighbour of least weight and then updating this weight to be the highest overall. We consider the maximum, minimum and average number of steps taken by the crawler to visit every vertex of firstly, complete k-partite graphs and secondly, sparse Erdős-Rényi random graphs. Our work follows on from a paper of Bonato et. al. who introduced the model.
  • PDF
    The divisible sandpile model is a growth model on graphs that was introduced by Levine and Peres as a tool to study internal diffusion limited aggregation. In this work we investigate the shape of the divisible sandpile model on the graphical Sierpinski gasket SG. We show that the shape is a ball in the graph metric of SG. Moreover we give an exact representation of the odometer function of the divisible sandpile.
  • PDF
    A sorting network is a shortest path from $12 \dots n$ to $n \dots 21$ in the Cayley graph of $S_n$ generated by adjacent transpositions. We establish existence of a local limit of sorting networks in a neighbourhood of $an$ for $a\in[0,1]$ as $n\to\infty$, with time scaled by a factor of $n$. The limit is a swap process $U$ on $\mathbb{Z}$. We show that $U$ is stationary and mixing with respect to the spatial shift and has time-stationary increments. Moreover, the only dependence on $a$ is through time scaling by a factor of $\sqrt{a(1-a)}$.
  • PDF
    In a series of papers the present authors and their coworkers have developed a family of algebraic techniques to solve a number of problems in the theory of discrete or continuous dynamical systems and to analyze numerical integrators. Given a specific problem, those techniques construct an abstract, \em universal version of it which is solved algebraically; then, the results are tranferred to the original problem with the help of a suitable morphism. In earlier contributions, the abstract problem is formulated either in the dual of the shuffle Hopf algebra or in the dual of the Connes-Kreimer Hopf algebra. In the present contribution we extend these techniques to more general Hopf algebras, which in some cases lead to more efficient computations.
  • PDF
    A regular $t$-balanced Cayley map (RBCM$_t$ for short) on a group $\Gamma$ is an embedding of a Cayley graph on $\Gamma$ into a surface with some special symmetric properties. We propose a reduction method to study RBCM$_t$'s, and as a first practice, we completely classify RBCM$_t$'s for a class of split metacyclic 2-groups.
  • PDF
    In this paper we introduce a graph structure, called subspace sum graph $\mathcal{G}(\mathbb{V})$ on a finite dimensional vector space $\mathbb{V}$ where the vertex set is the collection of non-trivial proper subspaces of a vector space and two vertices $W_1,W_2$ are adjacent if $W_1 + W_2=\mathbb{V}$. The diameter, girth, connectivity, maximal independent sets, different variants of domination number, clique number and chromatic number of $\mathcal{G}(\mathbb{V})$ are studied. It is shown that two subspace sum graphs are isomorphic if and only if the base vector spaces are isomorphic. Finally some properties of subspace sum graph are studied when the base field is finite.
  • PDF
    The paper designs five graph operations, and proves that every signed graph with chromatic number $q$ can be obtained from all-positive complete graphs $(K_q,+)$ by repeatedly applying these operations. This result gives a signed version of the Hajós theorem, emphasizing the role of all-positive complete graphs played in the class of signed graphs, as played in the class of unsigned graphs.
  • PDF
    We describe the second (generalized) Feng-Rao distance for elements in an Arf numerical semigroup that are greater than or equal to the conductor of the semigroup. This provides a lower bound for the second Hamming weight for one point AG codes. In particular, we can obtain the second Feng-Rao distance for the codes defined by asymptotically good towers of function fields whose Weierstrass semigroups are inductive. In addition, we compute the second Feng-Rao number, and provide some examples and comparisons with previous results on this topic. These calculations rely on Apéry sets, and thus several results concerning Apéry sets of Arf semigroups are presented.
  • PDF
    Let $G=(V,E)$ be a connected graph and let $d(u,v)$ denote the distance between vertices $u,v \in V$. A metric basis for $G$ is a set $B\subseteq V$ of minimum cardinality such that no two vertices of $G$ have the same distances to all points of $B$. The cardinality of a metric basis of $G$ is called the metric dimension of $G$, denoted by $\dim(G)$. In this paper we determine the metric dimension of the circulant graphs $C(n,\pm\{1,2,3,4\})$ for all values of $n$.
  • PDF
    In this paper we show a variant of colorful Tverberg's theorem which is valid in any matroid: Let $S$ be a sequence of non-loops in a matroid $M$ of finite rank $m$ with closure operator cl. Suppose that $S$ is colored in such a way that the first color does not appear more than $r$-times and each other color appears at most $(r-1)$-times. Then $S$ can be partitioned into $r$ rainbow subsequences $S_1,\ldots, S_r$ such that $cl\,\emptyset\subsetneq cl\,S_1\subseteq cl\, S_2\subseteq \ldots \subseteq cl\,S_r$. In particular, $\emptyset\neq \bigcap_{i=1}^r cl\,S_i$. A subsequence is called rainbow if it contains each color at most once. The conclusion of our theorem is weaker than the conclusion of the original Tverberg's theorem in $\mathbb R^d$, which states that $\bigcap conv\,S_i\neq \emptyset$, whereas we only claim that $\bigcap aff\,S_i\neq \emptyset$. On the other hand, our theorem strengthens the Tverberg's theorem in several other ways: 1) it is applicable to any matroid (whereas Tverberg's theorem can only be used in $\mathbb R^d$), 2) instead of $\bigcap cl\,S_i\neq \emptyset$ we have the stronger condition $cl\,\emptyset\subsetneq cl\,S_1\subseteq cl\,S_2\subseteq \ldots \subseteq cl\,S_r$, and 3) we add a color constraints that are even stronger than the color constraints in the colorful version of Tverberg's theorem. Recently, the author together with Goaoc, Mabillard, Patáková, Tancer and Wagner used the first property and applied the non-colorful version of this theorem to homology groups with $GF(p)$ coefficients to obtain several non-embeddability results, for details we refer to arXiv:1610.09063.
  • PDF
    For any $(m,n)$-periodic higher spin six-vertex configuration $\mathscr{L}$, we construct a one-parameter family $\Delta_\xi$ of pseudo-unitarizable representations of the corresponding noncommutative fiber product $\mathcal{A}(\mathscr{L})$ by difference operators acting on the space of sections of a complex line bundle $L_\xi$ over the face lattice $F$. The indefinite inner product is given explicitly in terms of a combinatorial sign function defined on $F$. We prove that each simple integral weight $\mathcal{A}(\mathscr{L})$-module (previously classified by the author, see arXiv:1612.08125) occurs as a submodule in one of these representation spaces. Lastly we give a combinatorial description of the signature of the unique (up to nonzero real multiples) indefinite inner product on any simple integral weight module, in terms of certain eight-vertex configurations canonically attached to $\mathscr{L}$. In particular we obtain necessary and sufficient conditions for such a module to be unitarizable.
  • PDF
    The Kolakoski sequence is the unique infinite sequence with values in $\{1, 2\}$ and first term twems $1, 2, \ldots$ which equals the sequence of run-lengths of itself, we call this $K(1, 2).$ We define $K(m, n)$ similarly for $m+n$ odd. A well-known open problem is that its limiting density is one-half. Indeed, not much is known about the Kolakoski sequence. The focus of this paper in on conjectures related to the Kolakoski sequence which are more discrete in nature. We conjecture that a certain doubly infinite family of finite sequences $E_{1, n}\left(1^{2^j}, 1^{2j}\right)$ has odd length for all $j>0$ and even $n>0.$ We define $cf(m, n, d)$ to be the "correlation frequency" or limiting probability that terms in $K(m, n)$ which are $d$ apart are equal. We conjecture that the sign of $cf(m, n, d) - 1/2$ is periodic mod $m+n.$ We also discuss extensive empirical evidence for these conjectures.
  • PDF
    Problem of finding an optimal upper bound for the chromatic no. of a (3 Times K1)-free graph is still open and pretty hard. Here we prove that for a (3 Times K1)-free graph G with maximum degree greater than or equal to 8, \chi is less than or equal to max (maximum degree-1, \omega). We also prove that if G is (3 Times K1)-free, \omega is equal to 4 and maximum degree is greater than or equal to 7, then \chi is less than or equal to maximum degree-1. This implies that Borodin & Kostochka Conjecture is true for (3 Times K1)-free graphs as a corollary.
  • PDF
    Let $S_n$ denote the group all permutations of $n$. For every permutation $\sigma$, we let $\mathrm{des}(\sigma)$ denote the number of descents in $\sigma$ and $\mathrm{LRMin}(\sigma)$ denote the number of left-to-right minima of $\sigma$. Given a sequence $\tau = \tau_1 \cdots \tau_n$ of distinct positive integers, we define the reduction of $\tau$, $\mathrm{red}(\tau)$, to be the permutation of $S_n$ that results by replacing the $i$-th smallest element of $\tau$ by $i$. If $\Gamma$ is a set of permutations, we say that a permutation $\sigma = \sigma_1 \ldots \sigma_n \in S_n$ has a $\Gamma$-match starting at position $i$ if there is a $i < j$ such that $\mathrm{red}(\sigma_i \sigma_{i+1} \ldots \sigma_j) \in \Gamma$. We let $\Gamma$-$\mathrm{mch}(\sigma)$ denote the number of $\Gamma$-matches in $\sigma$. We let $\mathcal{NM}_n(\Gamma)$ be the set of $\sigma \in S_n$ such that $\Gamma$-$\mathrm{mch}(\sigma) = 0$. In this paper, we modify Jones and Remmel's reciprocity method to study the generating function of the form \beginequation \mboxNM_\Gamma(t,x,y)=\sum_n ≥0 \fract^nn! \mboxNM_\Gamma,n(x,y) \endequation where $\displaystyle \mbox{NM}_{\Gamma,n}(x,y) =\sum_{\sigma \in \mathcal{NM}_n(\Gamma)}x^{\mathrm{LRmin}(\sigma)}y^{1+\mathrm{des}(\sigma)}$ in the case where we no longer insist that all the permutations $\tau \in \Gamma$ have at most one descent.
  • PDF
    Rotation symmetric Boolean functions are invariant under circular translation of indices. These functions have very rich cryptographic properties and have been used in different cryptosystems. Recently, Thomas Cusick proved that exponential sums of rotation symmetric Boolean functions satisfy homogeneous linear recurrences with integer coefficients. In this work, a generalization of this result is proved over any Galois field. That is, exponential sums over Galois fields of rotation symmetric polynomials satisfy linear recurrences with integer coefficients. In the particular case of $\mathbb{F}_2$, an elementary method is used to obtain explicit recurrences for exponential sums of some of these functions. The concept of trapezoid Boolean function is also introduced and it is showed that the linear recurrences that exponential sums of trapezoid Boolean functions satisfy are the same as the ones satisfied by exponential sums of the corresponding rotations symmetric Boolean functions. Finally, it is proved that exponential sums of trapezoid and symmetric polynomials also satisfy linear recurrences with integer coefficients over any Galois field $\mathbb{F}_q$. Moreover, the Discrete Fourier Transform matrix and some Complex Hadamard matrices appear as examples in some of our explicit formulas of these recurrences.
  • PDF
    Recently Lubetzky and Peres showed that simple random walks on a sequence of $d$-regular Ramanujan graphs $G_n=(V_n,E_n)$ of increasing sizes exhibit cutoff in total variation around the diameter lower bound $\frac{d}{d-2}\log_{d-1}|V_n| $. We provide a different argument under the assumption that for some $r(n) \gg 1$ the maximal number of simple cycles in a ball of radius $r(n)$ in $G_n$ is uniformly bounded in $n$.
  • PDF
    We introduce the Hopf algebra of quasi-symmetric functions with semigroup exponents generalizing the Hopf algebra QSym of quasi-symmetric functions. As a special case we obtain the Hopf algebra WCQSym of weak composition quasi-symmetric functions, which provides a framework for the study of a question proposed by G.-C.~Rota relating symmetric type functions and Rota-Baxter algebras. We provide the transformation formulas between the weak composition monomial and fundamental quasi-symmetric functions, which extends the corresponding results for quasi-symmetric functions. Moreover, we show that QSym is a Hopf subalgebra and a Hopf quotient algebra of WCQSym. Rota's question is addressed by identifying WCQsym with the free commutative unitary Rota-Baxter algebra of weight 1 on one generator, which also allows us to equip this algebra with a Hopf algebra structure.
  • PDF
    In 2011, Li et al. \citeLLL obtained an upper bound of the strong rainbow connection number of an $r$-dimensional undirected toroidal mesh. In this paper, this bound is improved. As a result, we give a negative answer to their problem.
  • PDF
    In a projective plane $\Pi_{q}$ (not necessarily Desarguesian) of order $q$, a point subset $\mathcal{S}$ is saturating (or dense) if any point of $\Pi_{q}\setminus \mathcal{S}$ is collinear with two points in $\mathcal{S}$. Modifying an approach of [31], we proved the following upper bound on the smallest size $s(2,q)$ of a saturating set in $\Pi_{q}$: \beginequation* s(2,q)≤\sqrt(q+1)\left(3\ln q+\ln\ln q +\ln\frac34\right)+\sqrt\fracq3\ln q+3. \endequation* The bound holds for all q, not necessarily large. By using inductive constructions, upper bounds on the smallest size of a saturating set in the projective space $\mathrm{PG}(N,q)$ with even dimension $N$ are obtained. All the results are also stated in terms of linear covering codes.
  • PDF
    This paper derives the bulk local limit of the swap process of uniformly random sorting networks. The limit object is defined through a deterministic procedure, a local version of the Edelman-Greene algorithm, applied to a two dimensional determinantal point process with explicit kernel. The latter describes the asymptotic joint law near $0$ of the eigenvalues of the corners in the antisymmetric Gaussian Unitary Ensemble. In particular, the limiting distribution of the first swap time at a given position is identified with the limiting distribution for the closest to $0$ eigenvalue in the antisymmetric GUE. The proofs rely on the determinantal structure and a double contour integral representation for the kernel of random Poissonized Young tableaux.
  • PDF
    We will say that an Abelian group $\Gamma$ of order $n$ has the $m$-\emphzero-sum-partition property ($m$-\textitZSP-property) if $m$ divides $n$, $m\geq 2$ and there is a partition of $\Gamma$ into pairwise disjoint subsets $A_1, A_2,\ldots , A_t$, such that $|A_i| = m$ and $\sum_{a\in A_i}a = g_0$ for $1 \leq i \leq t$, where $g_0$ is the identity element of $\Gamma$. In this paper we study the $m$-ZSP property of $\Gamma$. We show that $\Gamma$ has $m$-ZSP if and only if $|\Gamma|$ is odd or $m\geq 3$ and $\Gamma$ has more than one involution. We will apply the results to the study of group distance magic graphs as well as to generalized Kotzig arrays.
  • PDF
    A class of graphs is $\chi$-bounded if there exists a function $f:\mathbb N\rightarrow \mathbb N$ such that for every graph $G$ in the class and an induced subgraph $H$ of $G$, if $H$ has no clique of size $q+1$, then the chromatic number of $H$ is less than or equal to $f(q)$. We denote by $W_n$ the wheel graph on $n+1$ vertices. We show that the class of graphs having no vertex-minor isomorphic to $W_n$ is $\chi$-bounded. This generalizes several previous results; $\chi$-boundedness for circle graphs, for graphs having no $W_5$ vertex-minors, and for graphs having no fan vertex-minors.
  • PDF
    Graph construction, a fundamental operation in a data processing pipeline, is typically done by multiplying the incidence array representations of a graph, $\mathbf{E}_\mathrm{in}$ and $\mathbf{E}_\mathrm{out}$, to produce an adjacency array of the graph, $\mathbf{A}$, that can be processed with a variety of algorithms. This paper provides the mathematical criteria to determine if the product $\mathbf{A} = \mathbf{E}^{\sf T}_\mathrm{out}\mathbf{E}_\mathrm{in}$ will have the required structure of the adjacency array of the graph. The values in the resulting adjacency array are determined by the corresponding addition $\oplus$ and multiplication $\otimes$ operations used to perform the array multiplication. Illustrations of the various results possible from different $\oplus$ and $\otimes$ operations are provided using a small collection of popular music metadata.
  • PDF
    We prove the total positivity of the Narayana triangles of type $A$ and type $B$, and thus affirmatively confirm a conjecture of Chen, Liang and Wang and a conjecture of Pan and Zeng. We also prove the strict total positivity of the Narayana squares of type $A$ and type $B$.
  • PDF
    Let $S = k[x_1, \dotsc, x_n]$ be a polynomial ring over a field $k$ and let $M$ be a graded $S$-module with minimal free resolution $\mathbb{F}_\bullet$. Its linear part $lin(\mathbb{F}_\bullet)$ is obtained by deleting all non-linear entries from the differential of $\mathbb{F}_\bullet$. Our first result is an elementary description of $lin(\mathbb{F}_\bullet)$ in the case that $M$ is the Stanley-Reisner ring of a simplicial complex $\Delta$. Indeed, the differential of $lin(\mathbb{F}_\bullet)$ is simply a compilation of restriction maps in the simplicial cohomology of induced subcomplexes of $\Delta$. Our second result concerns the linearity defect of $M$, which is the largest $i$ such that $H_i(lin(\mathbb{F}_\bullet)) \neq 0$. We show that the linearity defect of $M$ is also the largest $i$, such that there exists a $g \in \mathbb{F}_{i}$ with $g\notin\mathfrak{m}\mathbb{F}_{i}$ and $\mathrm{d} g\in\mathfrak{m}^2\mathbb{F}_{i-1}$. Combining these two results, we obtain a description of the linearity defect of (the Stanley-Reisner ideal of) a simplicial complex, as well as a characterization of its componentwise linearity. Along the way, we also show that if a monomial ideal has at least one generator of degree $2$, then the linear strand of its resolution can be written using only $\pm 1$ coefficients.
  • PDF
    In this paper we devise a method of finding the limiting mean length of a minimal spanning tree for a random graph via the Smoluchowski coagulation equations for the corresponding coalescent process. In particular, we use this approach for finding the limiting mean length of a minimal spanning tree for the Erdos-Renyi random graph on an asymmetric bipartite graph, producing a completely new formula yet consistent with the previously known formula for the symmetric bipartite graph $K_{n,n}$.

Recent comments

Mario Jun 08 2016 06:58 UTC

Too bad, the paper has been withdrawn due to a mistake :-/

Joshua Lockhart May 12 2016 12:14 UTC

Some of the figures in your bound entanglement paper look spookily like some of our graphs! Thanks for highlighting these connections Māris, I appreciate it.

Māris Ozols May 12 2016 07:07 UTC

You introduce some very interesting concepts in this paper! I just wanted to point out some connections that might be interesting to explore.

**Hamiltonian complexity**

The density matrix in your eq. (2) looks exactly like 2-local Hamiltonian that encodes classical computation in its ground state

...(continued)
Tom Wong Nov 09 2015 11:12 UTC

This resolves an open problem of whether the procedure of Emms et al (2006), which is based on quantum walks, can distinguish all non-isomorphic strongly regular graphs. Their conclusion: no, because they came up with an example where the procedure fails.

Zoltán Zimborás Sep 18 2015 04:26 UTC

I can only quote Derrick Stolee: 'Terry Tao just dropped a bomb'. :)

Omar Shehab Jul 01 2014 20:55 UTC

In the last paragraph of the first column of page 3 says,

> This space contains $2^{NU}$ strings, and we have just send that $N!$
> of these strings $p_\pi$ encode permutations $\pi$.

I have following confusions.

- First of all, $\pi$ is a single definite permutation. So the sentence says

...(continued)
Omar Shehab Jul 01 2014 19:16 UTC

I think I know what is going on there. $\pi_{i,j}$ is just 0 or 1 and will be the corresponding digit of the binary representation of $\pi_i$.

Omar Shehab Jul 01 2014 19:03 UTC

I am little confused about equation 3 on page 3. It is,

$\pi_i=\sum^{U-1}_{j = 0} \pi_{i,j}(2)^j$

I have no clue what $\pi_{i, j}$ is. Any idea from anyone? Let $\pi_i = 3$ and $U = 2$. What should be the values of $\pi_{i,0}$ and $\pi_{i,1}$?

TQC 2014 Program Committee Jun 03 2014 10:43 UTC

### Reviewer 1 ###

The paper investigates a generalization of the notion of quantum colorings, and their associated nonlocal games, to graph homomorphisms.

A homomorphism from a graph $X$ to a graph $Y$ is a mapping $f$ from the vertices of $X$ to the vertices of $Y$ that preserves edge relat

...(continued)
TQC 2014 Program Committee Jun 03 2014 10:31 UTC

### Reviewer 1 ###

The main topic of study is the zero-error capacity of a classical communication system with a noisy classical channel, complemented with side information passing via a perfect noiseless quantum channel, in the form of shared entanglement between sender and receiver.

The math

...(continued)