Combinatorics (math.CO)

  • PDF
    A pair $(A,B)$ of square $(0,1)$-matrices is called a Lehman pair if $AB^T=J+kI$ for some integer $k\in\{-1,1,2,3,\ldots\}$, and the matrices $A$ and $B$ are called Lehman pair. This terminology arises because Lehman showed that the rows of minimum weight in any non-degenerate minimally nonideal (mni) matrix $M$ form a square Lehman submatrix of $M$. In this paper, we view a Lehman matrix as the bipartite adjacency matrix of a regular bipartite graph, focussing in particular on the case where the graph is cubic. From this perspective, we identify two constructions that generate cubic Lehman graphs from smaller Lehman graphs. The most prolific of these constructions involves repeatedly replacing suitable pairs of edges with a particular $6$-vertex subgraph that we call a $3$-rung ladder segment. Two decades ago, Lütolf and Margot initiated a computational study of mni matrices and constructed a catalogue containing (among other things) a listing of all cubic Lehman matrices with $k =1$ of order up to $17 \times 17$. We verify their catalogue (which has just one omission), and extend the computational results to $20 \times 20$ matrices. Of the $908$ cubic Lehman matrices (with $k=1$) of order up to $20 \times 20$, only two do not arise from our $3$-rung ladder construction. However these exceptions can be derived from our second construction, and so our two constructions cover all known cubic Lehman matrices with $k=1$.
  • PDF
    For a graph $G$ with vertex set $V(G)$, the Steiner distance $d(S)$ of $S\subseteq V(G)$ is the smallest number of edges in a connected subgraph of $G$ that contains $S$. Such a subgraph is necessarily a tree called a Steiner tree for $S$. The Steiner distance is a type of multi-way metric measuring the size of a Steiner tree between vertices of a graph and it generalizes the geodetic distance. The Steiner Wiener index is the sum of all Steiner distances in a graph and it generalizes the Wiener index. A simple method for calculating the Steiner Wiener index of block graphs is presented.
  • PDF
    We survey some recent works on standard Young tableaux of bounded height. We focus on consequences resulting from numerous bijections to lattice walks in Weyl chambers.
  • PDF
    Given a finitely generated group with generating set $S$, we study the cogrowth sequence, which is the number of words of length $n$ over the alphabet $S$ that are equal to one. This is related to the probability of return for walks in a Cayley graph with steps from $S$. We prove that the cogrowth sequence is not P-recursive when $G$ is an amenable group of superpolynomial growth, answering a question of Garrabant and Pak. In addition, we compute the cogrowth for certain infinite families of free products of finite groups and free groups, and prove that a gap theorem holds: if $S$ is a finite symmetric generating set for a group $G$ and if $a_n$ denotes the number of words of length $n$ over the alphabet $S$ that are equal to $1$ then either $\limsup_n a_n^{1/n} \le 2$ or $\limsup_n a_n^{1/n} \ge 2\sqrt{2}$.
  • PDF
    We develop algorithms, implemented in Maple, that study the number of vertices with a particular number of children in a random ordered tree where all vertices must have a number of children in some finite set. By calculating the mixed moments of two such numbers, the package produces strong evidence that the numbers are pairwise asymptotically normal.
  • PDF
    The inertia of a graph $G$ is defined to be the triplet $In(G) = (p(G), n(G), $ $\eta(G))$, where $p(G)$, $n(G)$ and $\eta(G)$ are the numbers of positive, negative and zero eigenvalues (including multiplicities) of the adjacency matrix $A(G)$, respectively. Traditionally $p(G)$ (resp. $n(G)$) is called the positive (resp. negative) inertia index of $G$. In this paper, we introduce three types of congruent transformations for graphs that keep the positive inertia index and negative inertia index. By using these congruent transformations, we determine all graphs with exactly two positive eigenvalues and one zero eigenvalue.
  • PDF
    The polytope of integer partitions of $n$ is the convex hull of the corresponding $n$-dimensional integer points. Its vertices are of importance because every partition is their convex combination. Computation shows intriguing features of $v(n),$ the number of the polytope vertices: its graph has a saw-toothed shape with the highest peaks at prime $n$'s. We explain the shape of $v(n)$ by the large number of partitions of even $n$'s that were counted by N. Metropolis and P. R. Stein. These partitions are convex combinations of two others. We reveal that divisibility of $n$ by 3 also reduces the value of $v(n),$ which is caused by partitions that are convex combinations of three but not two others, and characterize convex representations of such integer points in arbitrary integral polytope. To approach the prime $n$ phenomenon, we use a specific classification of integers and demonstrate that the graph of $v(n)$ is stratified to layers corresponding to resulting classes. Our main conjecture claims that $v(n)$ depends on collections of divisors of $n.$ We also offer an initial argument for that the number of vertices of the Gomory's master corner polyhedron on the cyclic group has features similar to those of $v(n).$
  • PDF
    In contrast to ordinary graphs, the number of the nowhere-zero group-flows in a signed graph may vary with different groups, even if the groups have the same order. In fact, for a signed graph $G$ and non-negative integer $d$, it was shown that there exists a polynomial $F_d(G,x)$ such that the number of the nowhere-zero $\Gamma$-flows in $G$ equals $F_d(G,x)$ evaluated at $k$ for every Abelian group $\Gamma$ of order $k$ with $\epsilon(\Gamma)=d$, where $\epsilon(\Gamma)$ is the largest integer $d$ such that $\Gamma$ has a subgroup isomorphic to $\mathbb{Z}^d_2$. We aim to give an expression of $F_d(G,x)$. We first define the fundamental directed circuits for a signed graph $G$ and show that all $\Gamma$-flows (not necessarily nowhere-zero) in $G$ can be generated by these circuits. Moreover, we show that all $\Gamma$-flows in $G$ can be evenly partitioned into $2^d$-classes specified by the elements of order 2 in $\Gamma$. This gives an explanation for why the number of the $\Gamma$-flows in a signed graph varies with different $\epsilon(\Gamma)$, and also gives an answer to a problem posed by Beck and Zaslavsky. Based on this result, we establish an explicit expression of $F_d(G,x)$ for any non-negative integer $d$. Further, using an extension of Whitney's broken circuit theory we give a combinatorial interpretation of the coefficients in $F_d(G,x)$ for $d=0$, in terms of the broken bonds. As an example, we give an analytic expression of $F_0(G,x)$ for a class of the signed graphs which contain no balanced circuit. Finally, we show that the broken bonds in a signed graph form a homogeneous simplicial complex.
  • PDF
    We prove an identity for the squares of generalized Tribonacci numbers. Various summation identities involving these numbers are obtained.
  • PDF
    Phylogenetic networks are rooted directed acyclic graphs that represent evolutionary relationships between species whose past includes reticulation events such as hybridisation and horizontal gene transfer. To search the space of phylogenetic networks, the popular tree rearrangement operation rooted subtree prune and regraft (rSPR) was recently generalised to phylogenetic networks. This new operation - called subnet prune and regraft (SNPR) - induces a metric on the space of all phylogenetic networks as well as on several widely-used network classes. In this paper, we investigate several problems that arise in the context of computing the SNPR-distance. For a phylogenetic tree $T$ and a phylogenetic network $N$, we show how this distance can be computed by considering the set of trees that are embedded in $N$ and then use this result to characterise the SNPR-distance between $T$ and $N$ in terms of agreement forests. Furthermore, we analyse properties of shortest SNPR-sequences between two phylogenetic networks $N$ and $N'$, and answer the question whether or not any of the classes of tree-child, reticulation-visible, or tree-based networks isometrically embeds into the class of all phylogenetic networks under SNPR.
  • PDF
    Let $S$ be a set of arbitrary objects, and let $S^d=\{v_1...v_d\colon v_i\in S\}$. A polybox code is a set $V\subset S^d$ with the property that for every two words $v,w\in V$ there is $i\in [d]$ with $v_i'=w_i$, where a permutation $s\mapsto s'$ of $S$ is such that $s''=(s')'=s$ and $s'\neq s$. If $|V|=2^d$, then $V$ is called a cube tiling code. Cube tiling codes determine $2$-periodic cube tilings of $\mathbb{R}^d$ or, equivalently, tilings of the flat torus $\mathbb{T}^d=\{(x_1,\ldots ,x_d)({\rm mod} 2):(x_1,\ldots ,x_d)\in \mathbb{R}^d\}$ by translates of the unit cube as well as $r$-perfect codes in $\mathbb{Z}^d_{4r+2}$ in the maximum metric. By a structural result, cube tiling codes for $d=4$ are enumerated. It is computed that there are 27,385 non-isomorphic cube tiling codes in dimension four, and the total number of such codes is equal to 17,794,836,080,455,680. Moreover, some procedure of passing from a cube tiling code to a cube tiling code in dimensions $d\leq 5$ is given.
  • PDF
    We study the mixing time of the $(n,k)$ Bernoulli--Laplace urn model, where $k\in\{0,1,\ldots,n\}$. Consider two urns, each containing $n$ balls, so that when combined they have precisely $n$ red balls and $n$ white balls. At each step of the process choose uniformly at random $k$ balls from the left urn and $k$ balls from the right urn and switch them simultaneously. We show that if $k=o(n)$, this Markov chain exhibits mixing time cutoff at $\frac{n}{4k}\log n$ and window of the order $\frac{n}{k}\log\log n$. This is an extension of a classical theorem of Diaconis and Shahshahani who treated the case $k=1$.
  • PDF
    The Erdős--Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph $H$, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of $r$-uniform hypergraphs. A theorem of Rödl asserts that if an $n$-vertex graph is non-universal then it contains an almost homogeneous set (i.e one with edge density either very close to $0$ or $1$) of size $\Omega(n)$. We prove that if a $3$-uniform hypergraph is non-universal then it contains an almost homogeneous set of size $\Omega(\log n)$. An example of Rödl from 1986 shows that this bound is tight. Let $R_r(t)$ denote the size of the largest non-universal $r$-graph $G$ so that neither $G$ nor its complement contain a complete $r$-partite subgraph with parts of size $t$. We prove an Erdős--Hajnal-type stepping-up lemma, showing how to transform a lower bound for $R_{r}(t)$ into a lower bound for $R_{r+1}(t)$. As an application of this lemma, we improve a bound of Conlon--Fox--Sudakov by showing that $R_3(t) \geq t^{\Omega(t)}$.
  • PDF
    Characterizations graphs of some classes to induce periodic Grover walks have been studied for recent years. In particular, for the strongly regular graphs, it has been known that there are only three kinds of such graphs. Here, we focus on the periodicity of the Grover walks on distance-regular graphs. The distance-regular graph can be regarded as a kind of generalization of the strongly regular graphs and the typical graph with an equitable partition. In this paper, we find some classes of such distance-regular graphs and obtain some useful necessary conditions to induce periodic Grover walks on the general distance-regular graphs. Also, we apply this necessary condition to give another proof for the strong regular graphs.
  • PDF
    This paper considers the difficulty in the set-system approach to generalizing graph theory. These difficulties arise categorically as the category of set-system hypergraphs is shown not to be cartesian closed and lacks enough projective objects, unlike the category of directed multigraphs (i.e. quivers). The category of incidence hypergraphs is introduced as a "graph-like" remedy for the set-system issues so that hypergraphs may be studied by their locally graphic behavior via homomorphisms that allow an edge of the domain to be mapped into a subset of an edge in the codomain. Moreover, it is shown that the category of quivers embeds into the category of incidence hypergraphs via a logical functor that is the inverse image of an essential geometric morphism between the topoi. Consequently, the quiver exponential is shown to be simply represented using incidence hypergraph homomorphisms.
  • PDF
    A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back more than two hundred years to the work of Euler on Latin squares and has been the focus of extensive research ever since. Euler posed a problem equivalent to finding properly $n$-edge-coloured complete bipartite graphs $K_{n,n}$ which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of $K_{n,n}$ without even a single rainbow perfect matching, the theme of this paper is to show that with some very weak additional constraints one can find many disjoint rainbow perfect matchings. In particular, we prove that if some fraction of the colour classes have at most $(1-o(1)) n$ edges then one can nearly-decompose the edges of $K_{n,n}$ into edge-disjoint perfect rainbow matchings. As an application of this, we establish in a very strong form a conjecture of Akbari and Alipour and asymptotically prove a conjecture of Barat and Nagy. Both these conjectures concern rainbow perfect matchings in edge-colourings of $K_{n,n}$ with quadratically many colours. Using our techniques, we also prove a number of results on near-decompositions of graphs into other rainbow structures like Hamiltonian cycles and spanning trees. Most notably, we prove that any properly coloured complete graph can be nearly-decomposed into spanning rainbow trees. This asymptotically proves the Brualdi-Hollingsworth and Kaneko-Kano-Suzuki conjectures which predict that a perfect decomposition should exist under the same assumptions.
  • PDF
    Fix graphs $F$ and $H$ and let $ex(n,H,F)$ denote the maximum possible number of copies of the graph $H$ in an $n$-vertex $F$-free graph. The systematic study of this function was initiated by Alon and Shikhelman [\it J. Comb. Theory, B. \bf 121 (2016)]. In this paper, we give new general bounds concerning this generalized Turán function. We also determine $ex(n,P_k,K_{2,t})$ and $ex(n,C_k,K_{2,t})$ asymptotically for every $k$ and $t$. For example, it is shown that for $t \geq 2$ and $k\geq 5$ we have $ex(n,C_k,K_{2,t})=\left(\frac{1}{2k}+o(1)\right)(t-1)^{k/2}n^{k/2}$. We also characterize the graphs $F$ that cause the function $ex(n,C_k,F)$ to be linear in $n$. In the final section we discuss a connection between the function $ex(n,H,F)$ and so-called Berge hypergraphs.
  • PDF
    A path in an(a) edge(vertex)-colored graph is called \empha conflict-free path if there exists a color used on only one of the edges(vertices) of the path. An(A) edge(vertex)-colored graph is called \emphconflict-free (vertex-)connected if between each pair of distinct vertices of the graph there is a conflict-free path. We call the graph \emphstrongly conflict-free connected if between each pair of distinct vertices of the graph there exists a conflict-free shortest path. The \emphstrong conflict-free connection number of a connected graph $G$, denoted by $scfc(G)$, is defined as the smallest number of colors that are required to make $G$ strongly conflict-free connected. In this paper, we study the problem: Given a connected graph $G$ and a coloring $c: E(or\ V)\rightarrow \{1,2,\cdots,k\} \ (k\geq 1)$ of $G$, determine whether or not $G$ is conflict-free (vertex-)connected under the coloring $c$. We provide a polynomial-time algorithm for this problem. We then show that it is NP-complete to decide whether there is a 2-edge-coloring of $G=(V,E)$ such that, for a given subset $P$ of $V\times V$, all pairs $(u,v)\in P$ are strongly conflict-free connected. At last, we show that it is NP-hard to decide whether $scfc(G)\leq k$ $(k\geq 3)$ for a given graph $G$.
  • PDF
    For a finite point set $E\subset \mathbb{R}^d$ and a connected graph $G$ on $k+1$ vertices, we define a $G$-framework to be a collection of $k + 1$ points in E such that the distance between a pair of points is specified if the corresponding vertices of $G$ are connected by an edge. We consider two frameworks the same if the specified edge-distances are the same. We find tight bounds on such distinct-distance drawings for rigid graphs in the plane, deploying the celebrated result of Guth and Katz. We introduce a congruence relation on the wider set of graphs, which behaves nicely in both the real-discrete and continuous settings. We provide a sharp bound on the number of such congruence classes. We then make a conjecture that the tight bound on rigid graphs should apply to all graphs. This appears to be a hard problem even in the case of the non-rigid 2-chain. However we provide evidence to support the conjecture by demonstrating that if the Erdős pinned-distance conjecture holds in dimension $d$ then the result for all graphs in dimension $d$ follows.
  • PDF
    Ramsey theory looks for regularities in large objects. Model theory studies algebraic structures as models of theories. The structural Ramsey theory combines these two fields and is concerned with Ramsey-type questions about certain model-theoretic structures. In 2005, Nešetřil initiated a systematic study of the so-called Ramsey classes of finite structures. This thesis is a contribution to the programme; we find Ramsey expansions of the primitive 3-constrained classes from Cherlin's catalogue of metrically homogeneous graphs. A key ingradient is an explicit combinatorial algorithm to fill-in the missing distances in edge-labelled graphs to obtain structures from Cherlin's classes. This algorithm also implies the extension property for partial automorphisms (EPPA), another combinatorial property of classes of finite structures.

Recent comments

Danial Dervovic Mar 01 2018 12:08 UTC

Hello again Māris, many thanks for your patience. Your comments and questions have given me much food for thought, and scope for an amended version of the paper -- please see my responses below.

Please if any of the authors of [AST17 [arXiv:1712.01609](https://arxiv.org/abs/1712.01609)] have any fu

...(continued)
Danial Dervovic Feb 05 2018 15:03 UTC

Thank you Māris for the extremely well thought-out and articulated points here.

I think this very clearly highlights the need to think explicitly about the precompute time if using the lifting to directly simulate the quantum walk, amongst other things.

I wish to give a well-considered respons

...(continued)
Māris Ozols Feb 01 2018 17:53 UTC

This paper considers the problem of using "lifted" Markov chains to simulate the mixing of coined quantum walks. The Markov chain has to approximately (in the total variational distance) sample from the distribution obtained by running the quantum walk for a randomly chosen time $t \in [0,T]$ follow

...(continued)
Danial Dervovic Dec 10 2017 15:25 UTC

Thank you for the insightful observations, Simon.

In response to the first point, there is a very short comment in the Discussion section to this effect. I felt an explicit dependence on $T$ as opposed to the diameter would make the implications of the result more clear. Namely, lifting can mix

...(continued)
Simon Apers Dec 09 2017 07:54 UTC

Thanks for the comment, Simone. A couple of observations:

- We noticed that Danial's result can in fact be proved more directly using the theorem that is used from ([arXiv:1705.08253][1]): by choosing the quantum walk Cesaro average as the goal distribution, it can be attained with a lifted Markov

...(continued)
Simone Severini Dec 07 2017 02:51 UTC

Closely related to

Simon Apers, Alain Sarlette, Francesco Ticozzi, Simulation of Quantum Walks and Fast Mixing with Classical Processes, https://scirate.com/arxiv/1712.01609

In my opinion, lifting is a good opportunity to put on a rigorous footing the relationship between classical and quantu

...(continued)
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)