Combinatorics (math.CO)

  • PDF
    We consider a problem introduced by Mossel and Ross [Shotgun assembly of labeled graphs, arXiv:1504.07682]. Suppose a random $n\times n$ jigsaw puzzle is constructed by independently and uniformly choosing the shape of each "jig" from $q$ possibilities. We are given the shuffled pieces. Then, depending on $q$, what is the probability that we can reassemble the puzzle uniquely? We say that two solutions of a puzzle are similar if they only differ by permutation of duplicate pieces, and rotation of rotationally symmetric pieces. In this paper, we show that, with high probability, such a puzzle has at least two non-similar solutions when $2\leq q \leq \frac{2}{\sqrt{e}}n$, all solutions are similar when $q\geq (2+\varepsilon)n$, and the solution is unique when $q=\omega(n)$.
  • PDF
    We formulate three current models of discrete-time quantum walks in a combinatorial way. These walks are shown to be closely related to rotation systems and 1-factorizations of graphs. For two of the models, we compute the traces and total entropies of the average mixing matrices for some cubic graphs. The trace captures how likely a quantum walk is to revisit the state it started with, and the total entropy measures how close the limiting distribution is to uniform. Our numerical results indicate three relations between quantum walks and graph structures: for the first model, rotation systems with higher genera give lower traces and higher entropies, and for the second model, the symmetric 1-factorizations always give the highest trace.
  • PDF
    In 2010, Joyce et. al defined the leverage centrality of vertices in a graph as a means to analyze functional connections within the human brain. In this metric a degree of a vertex is compared to the degrees of all it neighbors. We investigate this property from a mathematical perspective. We first outline some of the basic properties and then compute leverage centralities of vertices in different families of graphs. In particular, we show there is a surprising connection between the number of distinct leverage centralities in the Cartesian product of paths and the triangle numbers.
  • PDF
    We introduce new natural generalizations of the classical descent and inversion statistics for permutations, called width-$k$ descents and width-$k$ inversions. These variations induce generalizations of the excedance and major statistics, providing a framework in which the most well-known equidistributivity results for classical statistics are paralleled. We explore additional relationships among the statistics providing specific formulas in certain special cases. Moreover, we explore the behavior of these width-$k$ statistics in the context of pattern avoidance.
  • PDF
    Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. In this paper we use the container method to prove results that correspond to problems concerning tuples of disjoint independent sets in hypergraphs. In particular: (i) We generalise the random Ramsey theorem of Rödl and Ruciński by providing a resilience analogue. This result also implies the random version of Turán's theorem due to Conlon and Gowers and Schacht. (ii) We prove a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter. (iii) Both of the above results in fact hold for uniform hypergraphs. (iv) For a (hyper)graph $H$, we determine, up to an error term in the exponent, the number of $n$-vertex (hyper)graphs $G$ that have the Ramsey property with respect to $H$ (that is, whenever $G$ is $r$-coloured, there is a monochromatic copy of $H$ in $G$). (v) We strengthen the \emphrandom Rado theorem of Friedgut, Rödl and Schacht by proving a resilience version of the result. (vi) For partition regular matrices $A$ we determine, up to an error term in the exponent, the number of subsets of $\{1,\dots,n\}$ for which there exists an $r$-colouring which contains no monochromatic solutions to $Ax=0$. Along the way a number of open problems are posed.
  • PDF
    We use the rationality of the generalized $h^{th}$ convergent functions, $Conv_h(\alpha, R; z)$, to the infinite J-fraction expansions enumerating the generalized factorial product sequences, $p_n(\alpha, R) = R(R+\alpha)\cdots(R+(n-1)\alpha)$, defined in the references to construct new congruences and $h$-order finite difference equations for generalized factorial functions modulo $h \alpha^t$ for any primes or odd integers $h \geq 2$ and integers $0 \leq t \leq h$. Special cases of the results we consider within the article include applications to new congruences and exact formulas for the $\alpha$-factorial functions, $n!_{(\alpha)}$. Applications of the new results we consider within the article include new finite sums for the $\alpha$-factorial functions, restatements of classical necessary and sufficient conditions of the primality of special integer subsequences and tuples, and new finite sums for the single and double factorial functions modulo integers $h \geq 2$.
  • PDF
    With any (not necessarily proper) edge $k$-colouring $\gamma:E(G)\longrightarrow\{1,\dots,k\}$ of a graph $G$,one can associate a vertex colouring $\sigma\_{\gamma}$ given by $\sigma\_{\gamma}(v)=\sum\_{e\ni v}\gamma(e)$.A neighbour-sum-distinguishing edge $k$-colouring is an edge colouring whose associated vertex colouring is proper.The neighbour-sum-distinguishing index of a graph $G$ is then the smallest $k$ for which $G$ admitsa neighbour-sum-distinguishing edge $k$-colouring.These notions naturally extends to total colourings of graphs that assign colours to both vertices and edges.We study in this paper equitable neighbour-sum-distinguishing edge colourings andtotal colourings, that is colourings $\gamma$ for whichthe number of elements in any two colour classes of $\gamma$ differ by at most one.We determine the equitable neighbour-sum-distinguishing indexof complete graphs, complete bipartite graphs and forests,and the equitable neighbour-sum-distinguishing total chromatic numberof complete graphs and bipartite graphs.
  • PDF
    In 1972, Erdös - Faber - Lovász (EFL) conjectured that, if $\textbf{H}$ is a linear hypergraph consisting of $n$ edges of cardinality $n$, then it is possible to color the vertices with $n$ colors so that no two vertices with the same color are in the same edge. In 1978, Deza, Erdös and Frankl had given an equivalent version of the same for graphs: Let $G= \bigcup_{i=1}^{n} A_i$ denote a graph with $n$ complete graphs $A_1, A_2,$ $ \dots , A_n$, each having exactly $n$ vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of $G$ is $n$. The clique degree $d^K(v)$ of a vertex $v$ in $G$ is given by $d^K(v) = |\{A_i: v \in V(A_i), 1 \leq i \leq n\}|$. In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdös - Faber - Lovász conjecture using intersection matrix of the cliques $A_i$'s of $G$ and clique degrees of the vertices of $G$. Also, we give theoretical proof of the conjecture for some class of graphs. In particular we show that: 1. If $G$ is a graph satisfying the hypothesis of the Conjecture \refEFL and every $A_i$ ($1 \leq i \leq n$) has at most $\sqrt{n}$ vertices of clique degree greater than 1, then $G$ is $n$-colorable. 2. If $G$ is a graph satisfying the hypothesis of the Conjecture \refEFL and every $A_i$ ($1 \leq i \leq n$) has at most $\left \lceil {\frac{n+d-1}{d}} \right \rceil$ vertices of clique degree greater than or equal to $d$ ($2\leq d \leq n$), then $G$ is $n$-colorable.
  • PDF
    In the present paper we consider point distributions in compact connected two-point homogeneous spaces (Riemannian symmetric spaces of rank one). All such spaces are known, they are spheres in the Euclidean spaces, the real, complex and quaternionic projective spaces and the octonionic projective plane. Our concern is with discrepancies of distributions in metric balls and sums of pairwise distances between points of distributions for all such spaces. Using the geometric features of two-point spaces, we show that Stolarsky's invariance principle, well-known for the Euclidean spheres, can be extended to all projective spaces and the octonionic projective plane. Relying on the theory of spherical functions, we obtain the best possible bounds for quadratic discrepancies and sums of distances for point distributions in the two-point homogeneous spaces. Applications to $t$-designs and Lévy-Schoenberg kernels in such spaces are also considered in the paper.
  • PDF
    In this paper, we investigate the problem of separating a set $X$ of points in $\mathbb{R}^{2}$ with an arrangement of $K$ lines such that each cell contains an asymptotically equal number of points (up to a constant ratio). We consider a property of curves called the stabbing number, defined to be the maximum countable number of intersections possible between the curve and a line in the plane. We show that large subsets of $X$ lying on Jordan curves of low stabbing number are an obstacle to equal separation. We further discuss Jordan curves of minimal stabbing number containing $X$. Our results generalize recent bounds on the Erdős-Szekeres Conjecture, showing that for fixed $d$ and sufficiently large $n$, if $|X| \ge 2^{c_dn/d + o(n)}$ with $c_d = 1 + O(\frac{1}{\sqrt{d}})$, then there exists a subset of $n$ points lying on a Jordan curve with stabbing number at most $d$.
  • PDF
    Consider a surface $S$ and let $M\subset S$. If $S\setminus M$ is not connected, then we say $M$ \emphseparates $S$, and we refer to $M$ as a \emphseparating set of $S$. If $M$ separates $S$, and no proper subset of $M$ separates $S$, then we say $M$ is a \emphminimal separating set of $S$. In this paper we use methods of combinatorial topology to classify the minimal separating sets of the orientable surfaces of genus $g=2$ and $g=3$. The classification for genus 0 and 1 was done in earlier work, using methods of algebraic topology.
  • PDF
    It is well known that each nonnegative integral flow on a graph can be decomposed into a sum of nonnegative graphic circuit flows, which cannot be further decomposed into nonnegative integral sub-flows. This is equivalent to saying that the indecomposable flows on graphs are those graphic circuit flows. Turning from graphs to signed graphs, the indecomposable flows are much richer than those of unsigned graphs. This paper gives a complete description of indecomposable flows on signed graphs from the viewpoint of resolution of singularities by means of double covering graphs.
  • PDF
    Weingarten calculus is a completely general and explicit method to compute the moments of the Haar measure on compact subgroups of matrix algebras. Particular cases of this calculus were initiated by theoretical physicists -- including Weingarten, after whom this calculus was coined by the first author, after investigating it systematically. Substantial progress was achieved subsequently by the second author and coworkers, based on representation theoretic and combinatorial techniques. All formulas of `Weingarten calculus' are in the spirit of Weingarten's seminal paper [W78]. However, modern proofs are very different from Weingarten's initial ideas. In this paper, we revisit Weingarten's initial proof and we illustrate its power by uncovering two new important applications: (i) a uniform bound on the Weingarten function, that subsumes existing uniform bounds, and is optimal up to a polynomial factor, and (ii) an extension of Weingarten calculus to symmetric spaces and conceptual proofs of identities established by the second author.
  • PDF
    Let $\mathcal{S}\subset\mathbb{F}_{q}^{n}$ be the subset of self-orthogonal vectors in $\mathbb{F}_q^n$, which has size $|\mathcal{S}|=q^{n-1}+O\left(\sqrt{q^{n}}\right)$. In this paper we use the recently developed slice rank method to show that any set $E\subset\mathcal{S}$ of size \[ |E|>(n+1)^(q-1)(k-1) \]contains a $k$-tuple of distinct mutually orthogonal vectors, where $n\geq\binom{k}{2}$ and $q=p^{r}$ with $p\geq k$. The key innovation is a more general version of the slice rank of a tensor, which we call the multi-slice rank. We use a combinatorial argument to create an appropriate indicator tensor for the orthogonality of $k$-vectors, however for $k\geq4$ this tensor will have large slice rank, and so to obtain our results we need to use the less restrictive multi-slice rank. Additionally, we use this method to generalize a recent result of Ge and Shangguan, and prove that any set $A\subset\mathbb{F}_{q}^{n}$ of size \[ |A|>\binomn+(q-1)(k-1)(q-1)(k-1) \]contains a $k$-right-corner, that is distinct vectors $x_{1},\dots,x_{k},x_{k+1}$ where $x_{1}-x_{k+1},\dots,x_{k}-x_{k+1}$ are mutually orthogonal, as long as $n\geq\binom{k+1}{2}$ and $q=p^{r}$ with $p>k$.
  • PDF
    We introduce a class of fixed points of primitive morphisms among aperiodic binary generalized pseudostandard words. We conjecture that this class contains all fixed points of primitive morphisms among aperiodic binary generalized pseudostandard words that are not standard Sturmian words.
  • PDF
    The closed neighborhood $N_G[e]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having an end-vertex in common with $e$. Let $f$ be a function on $E(G)$, the edge set of $G$, into the set $\{-1,1\}$. If $\sum_{x\in{N[e]}}f(x)\geq 1$ for each edge $e \in E(G)$, then $f$ is called a signed edge dominating function of $G$. The signed edge domination number of $G$ is the minimum weight of a signed edge dominating function of $G$. In this paper, we find the signed edge domination number of the complete tripartite graph $K_{m,n,p}$, where $1\leq m\leq n$ and $p\geq m+n$. This completes the search for the signed edge domination numbers of the complete tripartite graphs.
  • PDF
    Based on numerical simulation and local stability analysis we describe the structure of the phase space of the edge/triangle model of random graphs. We support simulation evidence with mathematical proof of continuity and discontinuity for many of the phase transitions. All but one of themany phase transitions in this model break some form of symmetry, and we use this model to explore how changes in symmetry are related to discontinuities at these transitions.

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)