Combinatorics (math.CO)

  • PDF
    For well-generated complex reflection groups, Chapuy and Stump gave a simple product for a generating function counting reflection factorizations of a Coxeter element by their length. This is refined here to record the number of reflections used from each orbit of hyperplanes. The proof is case-by-case via the classification of well-generated groups. It implies a new expression for the Coxeter number, expressed via data coming from a hyperplane orbit; a case-free proof of this due to J. Michel is included.
  • PDF
    We show that there is a binary subspace code of constant dimension~3 in ambient dimension 7, having minimum distance 4 and cardinality 333, i.e., $333 \le A_2(7,4;3)$, which improves the previous best known lower bound of 329. Moreover, if a code with these parameters has at least 333 elements, its automorphism group is in $31$ conjugacy classes. This is achieved by a more general technique for an exhaustive search in a finite group that does not depend on the enumeration of all subgroups.
  • PDF
    We study planar walks that start from a given point (i\_0, j\_0), take their steps in a finite set S, and are confined in the first quadrant of the plane. Their enumeration can be attacked in a systematic way: the generating function Q(x, y, t) that counts them by their length (variable t) and the coordinates of their endpoint (variables x, y) satisfies a linear functional equation encoding the step-by-step description of walks. For instance, for the square lattice walks starting from the origin, this equation reads (xy-t(x + y + x^2 y + x y^2)) Q(x, y, t) = xy-xtQ(x, 0, t)-ytQ(O, y, t). The central question addressed in this paper is the nature of the series Q(x, y , t). When is it algebraic? When is it D-finite (or holonomic)? Can these properties be derived from the functional equation itself? Our first result is a new proof of an old theorem due to Kreweras, according to which one of these walk models has, for mysterious reasons, an algebraic generating function. Then, we provide a new proof of a holonomy criterion recently proved by M. Petkovsek and the author. In both cases, we work directly from the functional equation.
  • PDF
    Let $G$ be a graph with the usual shortest-path metric. A graph is $\delta$-hyperbolic if for every geodesic triangle $T$, any side of $T$ is contained in a $\delta$-neighborhood of the union of the other two sides. A graph is chordal if every induced cycle has at most three edges. A vertex separator set in a graph is a set of vertices that disconnects two vertices. In this paper we study the relation between vertex separator sets, some chordality properties which are natural generalizations of being chordal and the hyperbolicity of the graph. We also give a characterization of being quasi-isometric to a tree in terms of chordality and prove that this condition also characterizes being hyperbolic, when restricted to triangles, and having stable geodesics, when restricted to bigons.
  • PDF
    We introduce some natural families of distributions on rooted binary ranked plane trees with a view toward unifying ideas from various fields, including macroevolution, epidemiology, computational group theory, search algorithms and other fields. In the process we introduce the notions of split-exchangeability and plane-invariance of a general Markov splitting model in order to readily obtain probabilities over various equivalence classes of trees that arise in statistics, phylogenetics, epidemiology and group theory.
  • PDF
    Let a word be a sequence of $n$ i.i.d. integer random variables. The perimeter $P$ of the word is the number of edges of the word, seen as a polyomino. In this paper, we present a probabilistic approach to the computation of the moments of $P$. This is applied to uniform and geometric random variables. We also show that, asymptotically, the distribution of $P$ is Gaussian and, seen as a stochastic process, the perimeter converges in distribution to a Brownian motion
  • PDF
    The full $n$-Latin square is the $n\times n$ array with symbols $1,2,\dots ,n$ in each cell. In this paper we show, as part of a more general result, that any defining set for the full $n$-Latin square has size $n^3(1-o(1))$. The full design $N(v,k)$ is the unique simple design with parameters $(v,k,{v-2 \choose k-2})$; that is, the design consisting of all subsets of size $k$ from a set of size $v$. We show that any defining set for the full design $N(v,k)$ has size ${v\choose k}(1-o(1))$ (as $v-k$ becomes large). These results improve existing results and are asymptotically optimal. In particular, the latter result solves an open problem given in (Donovan, Lefevre, et al, 2009), in which it is conjectured that the proportion of blocks in the complement of a full design will asymptotically approach zero.
  • PDF
    Given a module $M$ for the algebra $\mathcal{D}_{\mathtt{q}}(G)$ of quantum differential operators on $G$, and a positive integer $n$, we may equip the space $F_n^G(M)$ of invariant tensors in $V^{\otimes n}\otimes M$, with an action of the double affine Hecke algebra of type $A_{n-1}$. Here $G= SL_N$ or $GL_N$, and $V$ is the $N$-dimensional defining representation of $G$. In this paper we take $M$ to be the basic $\mathcal{D}_{\mathtt{q}}(G)$-module, i.e. the quantized coordinate algebra $M= \mathcal{O}_{\mathtt{q}}(G)$. We describe a weight basis for $F_n^G(\mathcal{O}_{\mathtt{q}}(G))$ combinatorially in terms of walks in the type $A$ weight lattice, and standard periodic tableaux, and subsequently identify $F_n^G(\mathcal{O}_{\mathtt{q}}(G))$ with the irreducible "rectangular representation" of height $N$ of the double affine Hecke algebra.
  • PDF
    This paper continues the study of combinatorial properties of binary functions --- that is, functions $f:2^E\rightarrow\mathbb{C}$ such that $f(\emptyset)=1$, where $E$ is a finite set. Binary functions have previously been shown to admit families of transforms that generalise duality, including a trinity transform, and families of associated minor operations that generalise deletion and contraction, with both these families parameterised by the complex numbers. Binary function representations exist for graphs (via the indicator functions of their cutset spaces) and indeed arbitrary matroids (as shown by the author previously). In this paper, we characterise degenerate elements --- analogues of loops and coloops --- in binary functions, with respect to any pair of minor operations from our complex-parameterised family. We then apply this to study the relationship between binary functions and Tutte's alternating dimaps, which also support a trinity transform and three associated minor operations. It is shown that only the simplest alternating dimaps have binary representations of the form we consider, which seems to be the most direct type of representation. The question of whether there exist other, more sophisticated types of binary function representations for alternating dimaps is left open.
  • PDF
    We exhibit infinitely many examples of edge-regular graphs that have regular cliques and that are not strongly regular. This answers a question of Neumaier from 1981.
  • PDF
    In this note we construct a series of small subsets containing a non-d-th power element in a finite field by applying certain bounds on incomplete character sums. Precisely, let $h=\lfloor q^{\delta}\rfloor>1$ and $d\mid q^h-1$. If $q^h-1$ has a prime divisor $r$ with $r=O((h\log q)^c)$, then there is a constant $0<\epsilon<1$ such that for a ratio at least $\frac 1 {q^{\epsilon h}}$ of $\alpha\in \mathbb{F}_{q^{h}} \backslash\mathbb{F}_{q}$, the set $S=\{ \alpha-x^t, x\in\mathbb{F}_{q}\}$ of cardinality $O(q^{\frac 12 +\delta_c})$ contains a non-d-th power in $\mathbb{F}_{q^{\lfloor q^\delta\rfloor}}$, where $t$ is the largest power of $r$ such that $t<\sqrt{q}/h$. For odd $q$, the choice of $\delta=\frac 12-d, d=o(1)>0$ shows that there exists an explicit subset of cardinality $q^{1-d}=O(\log^{2+\epsilon'}(q^h))$ containing a non-quadratic element in $\mathbb{F}_{q^h}$. On the other hand, the choice of $h=2$ shows that for any odd prime power $q$, there is an explicit subset of cardinality $O(\sqrt{q})$ containing a non-quadratic element in $\mathbb{F}_{q^2}$, essentially improving a $O(q)$ construction by Coulter and Kosick \citeCK. In addition, we obtain a similar construction for small sets containing a primitive element. The construction works well provided $\phi(q^h-1)$ is very small, where $\phi$ is the Euler's totient function.
  • PDF
    For lengths $64$ and $66$, we construct extremal singly even self-dual codes with weight enumerators for which no extremal singly even self-dual codes were previously known to exist. We also construct new $40$ inequivalent extremal doubly even self-dual $[64,32,12]$ codes with covering radius $12$ meeting the Delsarte bound.
  • PDF
    We associate invariants such as permutation cycles and local cycles at infinity with $2-$standard consecutive structures (refer Definition $23$) to a line arrangement (refer Definition $2$) which has global cyclicity (refer Definition $19$) over fields with $1-ad$ structure (refer Definition $1$) to describe the gonality structures (refer Definition $8$) in Theorem $11$ when there exists a local permutation chart where the intersections points corresponding to simple transpositions satisfy One Sided Property $11$. While generalizing the features of a finite set of linear inequalities in two variables we compute modified simplicial homology groups of line arrangements over arbitrary fields in Theorem $2$ and ask Question $1$ about associating spaces which describe these invariant homology groups. In this article we could associate regions (refer Definition $5$) describing these invariants over fields with $1-ad$ structure. We construct a graph of isomorphism of classes of line arrangements over fields with $1-ad$ structure using the associated invariants and Elementary Collineation Transformations (ECT) in Theorem $13$ and in Note $11$. Here we prove a representation Theorem $13$ where we represent each isomorphism class with a given set of distinct slopes. We also prove a formulation of Polygonal Jordan Curve Theorem $3$ over fields with $1-ad$ structure and an isomorphism Theorem $14$ for those line arrangement collineation maps which preserve nook points and central pairs for quadrilateral substructures (refer Definition $30$). At the end of the article we ask some open questions on line-folds (refer Definition $31$).
  • PDF
    For a given graph $G$, the least integer $k\geq 2$ such that for every Abelian group $\mathcal{G}$ of order $k$ there exists a proper edge labeling $f:E(G)\rightarrow \mathcal{G}$ so that $\sum_{x\in N(u)}f(xu)\neq \sum_{x\in N(v)}f(xv)$ for each edge $uv\in E(G)$ is called the \textitgroup twin chromatic index of $G$ and denoted by $\chi'_g(G)$. This graph invariant is related to a few well known problems in the field neighbour distinguishing graph colorings. We conjecture that $\chi'_g(G)\leq \Delta(G)+3$ for all graphs without isolated edges and provide an infinite family of connected graph (trees) for which the equality holds. We prove this conjecture is valid for all trees, and then apply this result as the base case for proving a general upper bound for all graphs G without isolated edges: $\chi'_g(G)\leq 2(\Delta(G)+{\rm col}(G))-5$. This improves the best known upper bound known previously only for the case of cyclic groups $\mathbb{Z}_k$.
  • PDF
    The Plurality problem - introduced by Aigner \citeA2004 - has many variants. In this article we deal with the following version: suppose we are given $n$ balls, each of them colored by one of three colors. A \textitplurality ball is one such that its color class is strictly larger than any other color class. Questioner wants to find a plurality ball as soon as possible or state there is no, by asking triplets (or $k$-sets, in general), while Adversary partition the triplets into color classes as an answer for the queries and wants to postpone the possibility of determining a plurality ball (or stating there is no). We denote by $A_p(n,3)$ the largest number of queries needed to ask if both play optimally (and Questioner asks triplets). We provide an almost precise result in case of even $n$ by proving that for $n \ge 4$ even we have $$\frac34n-2 \le A_p(n,3) \le \frac34n-\frac12,$$ and for $n \ge 3$ odd we have $$\frac34n-O(\log n) \le A_p(n,3) \le \frac34n-\frac12.$$ We also prove some bounds on the number of queries needed to ask for larger $k$.
  • PDF
    A multigraph is a nonsimple graph which is permitted to have multiple edges, that is, edges that have the same end nodes. We introduce the concept of spanning simplicial complexes $\Delta_s(\mathcal{G})$ of multigraphs $\mathcal{G}$, which provides a generalization of spanning simplicial complexes of associated simple graphs. We give first the characterization of all spanning trees of a uni-cyclic multigraph $\mathcal{U}_{n,m}^r$ with $n$ edges including $r$ multiple edges within and outside the cycle of length $m$. Then, we determine the facet ideal $I_\mathcal{F}(\Delta_s(\mathcal{U}_{n,m}^r))$ of spanning simplicial complex $\Delta_s(\mathcal{U}_{n,m}^r)$ and its primary decomposition. The Euler characteristic is a well-known topological and homotopic invariant to classify surfaces. Finally, we device a formula for Euler characteristic of spanning simplicial complex $\Delta_s(\mathcal{U}_{n,m}^r)$.
  • PDF
    The distinguishing number (index) $D(G)$ ($D'(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a trivial automorphism. A graphoidal cover of $G$ is a collection $\psi$ of (not necessarily open) paths in $G$ such that every path in $\psi$ has at least two vertices, every vertex of $G$ is an internal vertex of at most one path in $\psi$ and every edge of $G$ is in exactly one path in $\psi$. Let $\Omega(G,\psi)$ denote the intersection graph of $\psi$. A graph $H$ is called a graphoidal graph, if there exists a graph $G$ and a graphoidal cover $\psi$ of $G$ such that $H\cong \Omega (G, \psi)$. In this paper, we study the distinguishing number and the distinguishing index of the line graph and the graphoidal graph of a simple connected graph $G$.
  • PDF
    We give a proof of Willcocks's Conjecture, stating that if $p - q$ and $p + q$ are relatively prime, then there exists a Hamiltonian tour of a $(p, q)$-leaper on a square chessboard of side $2(p + q)$. The conjecture was formulated by T. H. Willcocks in 1976 and has been an open problem since.
  • PDF
    For any graph, one can construct a ring, called the edge ring, which is a quadratic-monomial generated subring of the Laurent polynomial ring $k[x_1^{\pm 1},\dots,x_n^{\pm 1}]$. In fact, every quadratic-monomial generated subring of this Laurent polynomial ring can be generated as an edge ring for some graph. The combinatorial structure of the graph has been successfully applied to identify and classify many important commutative algebraic properties of the corresponding edge ring. In this paper, we classify Serre's $R_1$ condition for all quadratic-monomial generated subrings of $k[x_1^{\pm 1},\dots,x_n^{\pm 1}]$. Moreover, we provide a minimal example of a graph whose corresponding edge ring is not Cohen-Macaulay. This paper extends the work of Hibi and Ohsugi from the setting subrings of polynomial rings to subrings of Laurent polynomial rings.
  • PDF
    Let $\Gamma$ be a graph and let $G$ be a group of automorphisms of $\Gamma$. The graph $\Gamma$ is called $G$-normal if $G$ is normal in the automorphism group of $\Gamma$. Let $T$ be a finite non-abelian simple group and let $G = T^l$ with $l\geq 1$. In this paper we prove that if every connected pentavalent symmetric $T$-vertex-transitive graph is $T$-normal, then every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal. This result, among others, implies that every connected pentavalent symmetric $G$-vertex-transitive graph is $G$-normal except $T$ is one of $57$ simple groups. Furthermore, every connected pentavalent symmetric $G$-regular graph is $G$-normal except $T$ is one of $20$ simple groups, and every connected pentavalent $G$-symmetric graph is $G$-normal except $T$ is one of $17$ simple groups.
  • PDF
    For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$, the \emphSteiner distance $d_G(S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$. In this paper, we summarize the known results on the Steiner distance parameters, including Steiner distance, Steiner diameter, Steiner center, Steiner median, Steiner interval, Steiner distance hereditary graph, Steiner distance stable graph, average Steiner distance, and Steiner Wiener index. It also contains some conjectures and open problems for further studies.

Recent comments

Māris Ozols Jul 26 2017 11:07 UTC

Conway's list still has four other $1000 problems left:

https://oeis.org/A248380/a248380.pdf

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)