Combinatorics (math.CO)

  • PDF
    Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has "defect" $d$ if each monochromatic component has maximum degree at most $d$. A colouring has "clustering" $c$ if each monochromatic component has at most $c$ vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding $K_t$ as a minor, graphs excluding $K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open problems are discussed.
  • PDF
    The PWP map was introduced by the second author as a tool for ranking nodes in networks. In this work we extend this technique so that it can be used to rank links as well. Applying the Girvan-Newman algorithm a ranking method on links induces a deconstruction method for networks, therefore we obtain new methods for finding clustering and core-periphery structures on networks.
  • PDF
    We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any $\varepsilon \in (0,1)$ and positive integer $k,$ if a $(d+1)-$regular graph has an eigenvector which supports $\varepsilon$ fraction of the $\ell_2^2$ mass on a subset of $k$ vertices, then the graph must have a cycle of size $\tilde{O}(\log_{d}(k)/\varepsilon^2)$, suppressing logarithmic terms in $1/\varepsilon$. In this paper, we improve the upper bound to $\tilde{O}(\log_{d}(k)/\varepsilon)$ and present a construction showing a lower bound of $\Omega(\log_d(k)/\varepsilon)$. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.
  • PDF
    A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$-coloring is a Gallai coloring that uses $k$ colors. Given an integer $k\ge1$ and graphs $H_1, H_2, \ldots, H_k$, the Gallai-Ramsey number $GR(H_1, H_2, \ldots, H_k)$ is the least integer $n$ such that every Gallai $k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H_i$ in color $i$ for some $i \in \{1,2, \ldots, k\}$. When $H = H_1 = \cdots = H_k$, we simply write $GR_k(H)$. We study Gallai-Ramsey numbers of even cycles and paths. For all $n\ge3$ and $k\ge1$, let $G_i=P_{2i+3}$ be a path on $2i+3$ vertices for all $i\in\{0,1, \ldots, n-2\}$ and $G_{n-1}\in\{C_{2n}, P_{2n+1}\}$. Let $ i_j\in\{0,1,\ldots, n-1 \}$ for all $j\in\{1,2, \ldots, k\}$ with $ i_1\ge i_2\ge\cdots\ge i_k $. The first author recently conjectured that $ GR(G_{i_1}, G_{i_2}, \ldots, G_{i_k}) = 3+\min\{i_1,n^*-2\}+\sum_{j=1}^k i_j$, where $n^* =n$ when $G_{i_1}\ne P_{2n+1}$ and $n^* =n+1$ when $G_{i_1}= P_{2n+1}$. The truth of this conjecture implies that $GR_k(C_{2n})=GR_k(P_{2n})=(n-1)k+n+1$ for all $n\ge3$ and $k\ge1$, and $GR_k(P_{2n+1})=(n-1)k+n+2$ for all $n\ge1$ and $k\ge1$. In this paper, we prove that the aforementioned conjecture holds for $n\in\{3,4\}$ and all $k\ge1$. Our proof relies only on Gallai's result and the classical Ramsey numbers $R(H_1, H_2)$, where $H_1, H_2\in\{C_8, C_6, P_7, P_5, P_3\}$. We believe the recoloring method we developed here will be very useful for solving subsequent cases, and perhaps the conjecture.
  • PDF
    We continue to investigate the properties of the earlier defined functions fm and gm, which depend on an initial arithmetic function f0. In this papers values of f0 are the Fine numbers. We investigate functions fi; gi; (i = 1; 2; 3; 4). For each function, we derive an explicit formula and give a combinatorial interpretation. It appears that g2 and g3 are well-known combinatoric object called the Catalan triangles. We finish with an identity consisting of ten items.
  • PDF
    We introduce a family of sequence transformations, defined via partial Bell polynomials, that may be used for a systematic study of a wide variety of problems in enumerative combinatorics. This family includes some of the transformations listed in the paper by Bernstein & Sloane, now seen as transformations under the umbrella of partial Bell polynomials. Our goal is to describe these transformations from the algebraic and combinatorial points of view. We provide functional equations satisfied by the generating functions, derive inverse relations, and give a convolution formula. While the full range of applications remains unexplored, in this paper we show a glimpse of the versatility of Bell transformations by discussing the enumeration of several combinatorial configurations, including rational Dyck paths, rooted planar maps, and certain classes of permutations.
  • PDF
    Graph anticoloring problem is partial coloring problem where the main feature is the opposite rule of the graph coloring problem, i.e., if two vertices are adjacent, their assigned colors must be the same or at least one of them is uncolored. In the same way, Berge in 1972 proposed the problem of placing b black queens and w white queens on a $n \times n$ chessboard such that no two queens of different color can attack to each other, the complexity of this problem remains open. In this work we deal with the knight piece under the balance property, since this special case is the most difficult for brute force algorithms.
  • PDF
    The bunkbed conjecture was first posed by Kasteleyn. If $G=(V,E)$ is a finite graph and $H$ some subset of $V$, then the bunkbed of the pair $(G,H)$ is the graph $G\times\{1,2\}$ plus $|H|$ extra edges to connect for every $v\in H$ the vertices $(v,1)$ and $(v,2)$. The conjecture asserts that $(v,1)$ is more likely to connect with $(w,1)$ than with $(w,2)$ in the independent bond percolation model for any $v,w\in V$. This is intuitive because $(v,1)$ is in some sense closer to $(w,1)$ than it is to $(w,2)$. The conjecture has however resisted several attempts of proof. This paper settles the conjecture in the case of a constant percolation parameter and $G$ the complete graph.
  • PDF
    A family of sets is called $r$-\emphcover free if it does not contain $2\leq\ell+1\leq r+1$ distinct sets $A_0,A_1,\ldots,A_{\ell}$ such that $A_0\subseteq A_1\cup\cdots\cup A_{\ell}$. In particular, a $1$-cover free family of sets is simply an antichain, with respect to set inclusion. Thus, by Sperner's classical result, the maximal cardinality of a $1$-cover free family of subsets of a set of $n$ elements is $\binom{n}{\lfloor n/2\rfloor}$. For $r>1$, the maximal cardinality of an $r$-cover free family of subsets of a set of $n$ elements was studied by Erdős, Frankl and F\"uredi. In this paper we are interested in the following probabilistic variant of this problem. For positive integers $r$ and $n$, how small can the probability that $S_0\subseteq S_1\cup\cdots\cup S_r$ be, where $S_0,S_1,\ldots,S_r$ are i.i.d random subsets of a set of $n$ elements? For $r=1$, we show that for every $n\geq 2$, this probability is minimal when the distributions of $S_0$ and of $S_1$ are uniform on a $1$-cover free family of maximal cardinality. In a complete contrast, we also show that this is not the case for every $r>1$ (and $n$ large enough). Interestingly, finding a probability distribution on subsets of the set $\{1,2,\ldots,n\}$, for which the probability that $S_0\subseteq S_1\cup S_2$ is small (where $S_0,S_1,S_2$ are drawn independently according to this distribution), is useful for analyzing the misuse resistance of one-time signatures.
  • PDF
    In this article we study supermodular functions on finite distributive lattices. Relaxing the assumption that the domain is a powerset of a finite set, we focus on geometrical properties of the polyhedral cone of such functions. Specifically, we generalize the criterion for extremal rays and study the face lattice of the supermodular cone. An explicit description of facets by the corresponding tight linear inequalities is provided.
  • PDF
    In \citedehind1, the concept of image partition regularity near zero was first instigated. In contrast to the finite case , infinite image partition regular matrices near zero are very fascinating to analyze. In this regard the abstraction of Centrally image partition regular matrices near zero was introduced in \citebiswaspaul. In this paper we propose the notion of matrices that are C-image partition regular near zero for dense subsemigropus of $((0,\infty),+)$.

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](] have any fu

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

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

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

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

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,

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

Māris Ozols Jul 26 2017 11:07 UTC

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

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