Search

We present progress on two old conjectures about longest cycles in graphs. The first conjecture, due to Thomassen from 1978, states that apart from a finite number of exceptions, all connected vertex-transitive graphs contain a Hamiltonian cycle. The second conjecture, due to Smith from 1984, states that for $r\ge 2$ in every $r$-connected graph any two longest cycles intersect in at least $r$ vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph which can be used to improve the best known bounds towards both of the aforementioned conjectures: First, we show that every connected vertex-transitive graph on $n\geq 3$ vertices contains a cycle of length at least $\Omega(n^{13/21})$, improving on $\Omega(n^{3/5})$ from [De Vos, arXiv:2302:04255, 2023]. Second, we show that in every $r$-connected graph with $r\geq 2$, any two longest cycles meet in at least $\Omega(r^{5/8})$ vertices, improving on $\Omega(r^{3/5})$ from [Chen, Faudree and Gould, J. Combin. Theory, Ser.~ B, 1998]. Our proof combines combinatorial arguments, computer-search and linear programming., Comment: 13 pages, 3 figures. Code available at https://github.com/tjeremie/Long-cycles

Let $G$ be a simple graph with adjacency matrix $A(G)$, signless Laplacian matrix $Q(G)$, degree diagonal matrix $D(G)$ and let $l(G)$ be the line graph of $G$. In 2017, Nikiforov defined the $A_\alpha$-matrix of $G$, $A_\alpha(G)$, as a linear convex combination of $A(G)$ and $D(G)$, the following way, $A_\alpha(G):=\alpha A(G)+(1-\alpha)D(G),$ where $\alpha\in[0,1]$. In this paper, we present some bounds for the eigenvalues of $A_\alpha(G)$ and for the largest and smallest eigenvalues of $A_\alpha(l(G))$. Extremal graphs attaining some of these bounds are characterized., Comment: 18 pages, 5 figures, 3 tables

Given a finite poset $\mathcal P$, we say that a family $\mathcal F$ of subsets of $[n]$ is $\mathcal P$-saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$, but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$. The induced saturation number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$, is the size of the smallest $\mathcal P$-saturated family with ground set $[n]$. In this paper we prove that the saturation number for any given poset grows at worst polynomially. More precisely, we show that $\text{sat}^*(n, \mathcal P)=O(n^c)$, where $c\leq|\mathcal{P}|^2/4+1$ is a constant depending on $\mathcal P$ only. We obtain this result by bounding the VC-dimension of our family., Comment: 7 pages, 2 figures

We introduce the Graph TT (GTT) and Graph OSPA (GOSPA) metrics based on optimal assignment, which allow us to compare not only the edge structures but also general vertex and edge attributes of graphs of possibly different sizes. We argue that this provides an intuitive and universal way to measure the distance between finite simple attributed graphs. Our paper discusses useful equivalences and inequalities as well as the relation of the new metrics to various existing quantifications of distance between graphs. By deriving a representation of a graph as a pair of point processes, we are able to formulate and study a new type of (finite) random graph convergence and demonstrate its applicability using general point processes of vertices with independent random edges. Computational aspects of the new metrics are studied in the form of an exact and two heuristic algorithms that are derived from previous algorithms for similar tasks. As an application, we perform a statistical test based on the GOSPA metric for functional differences in olfactory neurons of Drosophila flies., Comment: 53 pages, 7 figures, 5 tables

The proper conflict-free chromatic number, $\chi_{pcf}(G)$, of a graph $G$ is the least $k$ such that $G$ has a proper $k$-coloring in which for each non-isolated vertex there is a color appearing exactly once among its neighbors. The proper odd chromatic number, $\chi_{o}(G)$, of $G$ is the least $k$ such that $G$ has a proper coloring in which for every non-isolated vertex there is a color appearing an odd number of times among its neighbors. We say that a graph class $\mathcal{G}$ is $\chi_{pcf}$-bounded ($\chi_{o}$-bounded) if there is a function $f$ such that $\chi_{pcf}(G) \leq f(\chi(G))$ ($\chi_{o}(G) \leq f(\chi(G))$) for every $G \in \mathcal{G}$. Caro et al. (2022) asked for classes that are linearly $\chi_{pcf}$-bounded ($\chi_{pcf}$-bounded), and as a starting point, they showed that every claw-free graph $G$ satisfies $\chi_{pcf}(G) \le 2\Delta(G)+1$, which implies $\chi_{pcf}(G) \le 4\chi(G)+1$. In this paper, we improve the bound for claw-free graphs to a nearly tight bound by showing that such a graph $G$ satisfies $\chi_{pcf}(G) \le \Delta(G)+6$, and even $\chi_{pcf}(G) \le \Delta(G)+4$ if it is a quasi-line graph. These results also give evidence for a conjecture by Caro et al. Moreover, we show that convex-round graphs and permutation graphs are linearly $\chi_{pcf}$-bounded. For these last two results, we prove a lemma that reduces the problem of deciding if a hereditary class is linearly $\chi_{pcf}$-bounded to deciding if the bipartite graphs in the class are $\chi_{pcf}$-bounded by an absolute constant. This lemma complements a theorem of Liu (2022) and motivates us to study boundedness in bipartite graphs. In particular, we show that biconvex bipartite graphs are $\chi_{pcf}$-bounded while convex bipartite graphs are not even $\chi_o$-bounded, and exhibit a class of bipartite circle graphs that is linearly $\chi_o$-bounded but not $\chi_{pcf}$-bounded., Comment: 24 pages, 1 figure. Slight changes in introduction. References added

Let $G=(V,E)$ be an $n$-vertex connected graph of maximum degree $\Delta$. Given access to $V$ and an oracle that given two vertices $u,v\in V$, returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$? We give a simple deterministic algorithm to reconstruct trees using $\Delta n\log_\Delta n+(\Delta+2)n$ distance queries and show that even randomised algorithms need to use at least $\frac1{200} \Delta n\log_\Delta n$ queries in expectation. The best previous lower bound was an information-theoretic lower bound of $\Omega(n\log n/\log \log n)$. Our lower bound also extends to related query models including distance queries for phylogenetic trees, membership queries for learning partitions and path queries in directed trees. We extend our deterministic algorithm to reconstruct graphs without induced cycles of length at least $k$ using $O_{\Delta,k}(n\log n)$ queries, which includes various graph classes of interest such as chordal graphs, permutation graphs and AT-free graphs. Since the previously best known randomised algorithm for chordal graphs uses $O_{\Delta}(n\log^2 n)$ queries in expectation, we both get rid off the randomness and get the optimal dependency in $n$ for chordal graphs and various other graph classes. Finally, we build on an algorithm of Kannan, Mathieu, and Zhou [ICALP, 2015] to give a randomised algorithm for reconstructing graphs of treelength $k$ using $O_{\Delta,k}(n\log^2n)$ queries in expectation.

We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different (labelled) graphs may have the same set of connected triples, making unique reconstruction of the original graph from the triples impossible. We identify some families of graphs (including triangle-free graphs) for which all graphs have a different set of connected triples. We also give algorithms that reconstruct a graph from a set of triples, and for testing if this reconstruction is unique. Finally, we study a possible extension of the model in which the subsets of size $k$ that induce a connected graph are given for larger (fixed) values of $k$., Comment: 20 pages including appendices

The analogue of Hadwiger's conjecture for the immersion relation states that every graph $G$ contains an immersion of $K_{\chi(G)}$. For graphs with independence number 2, this is equivalent to stating that every such $n$-vertex graph contains an immersion of $K_{\lceil n/2 \rceil}$. We show that every $n$-vertex graph with independence number 2 contains every complete bipartite graph on $\lceil n/2 \rceil$ vertices as an immersion., Comment: 21 pages, 11 figures

Given an integer $n$, let $G(n)$ be the number of integer sequences $n-1\ge d_1\ge d_2\ge\dotsb\ge d_n\ge 0$ that are the degree sequence of some graph. We show that $G(n)=(c+o(1))4^n/n^{3/4}$ for some constant $c>0$, improving both the previously best upper and lower bounds by a factor of $n^{1/4}$ (up to polylog-factors). Additionally, we answer a question of Royle, extend the values of $n$ for which the exact value of $G(n)$ is known from $n\le290$ to $n\le 1651$ and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative., Comment: 46 pages, 2 figures

This paper studies a \emph{packing} problem in the so-called beyond-planar setting, that is when the host graph is ``almost-planar'' in some sense. Precisely, we consider the case that the host graph is $k$-planar, i.e., it admits an embedding with at most $k$ crossings per edge, and focus on families of $\Delta$-regular caterpillars, that are caterpillars whose non-leaf vertices have the same degree $\Delta$. We study the dependency of $k$ from the number $h$ of caterpillars that are packed, both in the case that these caterpillars are all isomorphic to one another (in which case the packing is called \emph{placement}) and when they are not. We give necessary and sufficient conditions for the placement of $h$ $\Delta$-regular caterpillars and sufficient conditions for the packing of a set of $\Delta_1$-, $\Delta_2$-, $\dots$, $\Delta_h$-regular caterpillars such that the degree $\Delta_i$ and the degree $\Delta_j$ of the non-leaf vertices can differ from one caterpillar to another, for $1 \leq i,j \leq h$, $i\neq j$.

In this paper we study partitions whose successive ranks belong to a given set. We enumerate such partitions while keeping track of the number of parts, the largest part, the side of the Durfee square, and the height of the Durfee rectangle. We also obtain a new bijective proof of a result of Andrews and Bressoud that the number of partitions of $N$ with all ranks at least $1-\ell$ equals the number of partitions of $N$ with no parts equal to $\ell+1$, for $\ell\ge0$, which allows us to refine it by the above statistics. Combining Foata's second fundamental transformation for words with Greene and Kleitman's mapping for subsets, interpreted in terms of lattice paths, we obtain enumeration formulas for partitions whose successive ranks satisfy certain constraints, such as being bounded by a constant.

We show several sharp upper and lower bounds for the sum of the largest eigenvalues of the signless Laplacian matrix. These bounds improve and extend previously known bounds., Comment: arXiv admin note: text overlap with arXiv:1412.0323

Let G be a graph of order $n$ with adjacency matrix $A(G)$ and diagonal matrix of degree $D(G)$. For every $\alpha \in [0,1]$, Nikiforov \cite{VN17} defined the matrix $A_\alpha(G) = \alpha D(G) + (1-\alpha)A(G)$. In this paper we present the $A_{\alpha}(G)$-characteristic polynomial when $G$ is obtained by coalescing two graphs, and if $G$ is a semi-regular bipartite graph we obtain the $A_{\alpha}$-characteristic polynomial of the line graph associated to $G$. Moreover, if $G$ is a regular graph we exhibit the $A_{\alpha}$-characteristic polynomial for the graphs obtained from some operations., Comment: 19 pages, 5 figures

A lazy transposition $(a,b,p)$ is the random permutation that equals the identity with probability $1-p$ and the transposition $(a,b)\in S_n$ with probability $p$. How long must a sequence of independent lazy transpositions be if their composition is uniformly distributed? It is known that there are sequences of length $\binom{n}2$, but are there shorter sequences? This was raised by Fitzsimons in 2011, and independently by Angel and Holroyd in 2018. We answer this question negatively by giving a construction of length $\frac23 \binom{n}2+O(n\log n)$, and consider some related questions., Comment: 23 pages, 5 figures, 1 table

We investigate a generalisation of permutation networks. We say a sequence $T=(T_1,\dots,T_\ell)$ of transpositions in $S_n$ forms a $t$-reachability network if for every choice of $t$ distinct points $x_1, \dots, x_t\in \{1,\dots,n\}$, there is a subsequence of $T$ whose composition maps $j$ to $x_j$ for every $1\leq j\leq t$. When $t=n$, any permutation in $S_n$ can be created and $T$ is a permutation network. Waksman [JACM, 1968] showed that the shortest permutation networks have length about $n \log_2n$. In this paper, we investigate the shortest $t$-reachability networks. Our main result settles the case of $t=2$: the shortest $2$-reachability network has length $\lceil 3n/2\rceil-2 $. For fixed $t$, we give a simple randomised construction which shows there exist $t$-reachability networks using $(2+o_t(n))n$ transpositions. We also study the case where all transpositions are of the form $(1, \cdot)$, separating 2-reachability from the related probabilistic variant of 2-uniformity. Many interesting questions are left open., Comment: 13 pages, 1 figure

For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use sat$^*(n, k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of sat$^*(n, k)$. Our result implies that sat$^*(n, k)=n(k-1)-\Theta(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat$^*(n,k)$ were only known for $k$ up to $6$. We also prove a generalisation of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one)., Comment: 31 pages, 3 figures

Two permutations $s$ and $t$ are $k$-similar if they can be decomposed into subpermutations $s^1, \ldots, s^k$ and $t^1, \ldots, t^k$ such that $s^i$ is order-isomorphic to $t^i$ for all $i$. Recently, Dudek, Grytczuk and Ruci\'nski posed the problem of determining the minimum $k$ for which two permutations chosen independently and uniformly at random are $k$-similar. We show that two such permutations are $O(n^{1/3}\log^{11/6}(n))$-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalises to simultaneous decompositions of multiple permutations., Comment: 11 pages, 2 figures

A square is a factor $S = (S_1; S_2)$ where $S_1$ and $S_2$ have the same pattern, and a permutation is said to be square-free if it contains no non-trivial squares. The permutation is further said to be bicrucial if every extension to the left or right contains a square. We completely classify for which $n$ there exists a bicrucial square-free permutation of length $n$., Comment: 24 pages, 4 figures

We describe the simplicial complex $\Delta$ such that the initial ideal of $J_G$ is the Stanley-Reisner ideal of $\Delta$. By $\Delta$ we show that if $J_G$ is $(S_2)$ then $G$ is accessible. We also characterize all accessible blocks with whiskers of cycle rank 3 and we define a new infinite class of accessible blocks with whiskers for any cycle rank. Finally, by using a computational approach, we show that the graphs with at most 12 vertices whose binomial edge ideal is Cohen-Macaulay are all and only the accessible ones., Comment: In this new version we added the case n=12 in Theorem 5.1

An independent transversal of a graph $G$ with a vertex partition $\mathcal P$ is an independent set of $G$ intersecting each block of $\mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $\mathcal P$ has size at least $t$ and the average degree of vertices in each block is at most $t/4$, then an independent transversal of $\mathcal P$ exists. We present a construction showing that this result is optimal: for any $\varepsilon > 0$ and sufficiently large $t$, there is a family of forests with vertex partitions whose block size is at least $t$, average degree of vertices in each block is at most $(\frac14+\varepsilon)t$, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version., Comment: 12 pages, 2 figures

The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. We say that a graph is reconstructible from its $\ell$-deck if no other graph has the same $\ell$-deck. In 1957, Kelly showed that every tree with $n\ge3$ vertices can be reconstructed from its $(n-1)$-deck, and Giles strengthened this in 1976, proving that trees on at least 6 vertices can be reconstructed from their $(n-2)$-decks. Our main theorem states that trees are reconstructible from their $(n-r)$-decks for all $r\le n/{9}+o(n)$, making substantial progress towards a conjecture of N\'ydl from 1990. In addition, we can recognise the connectedness of a graph from its $\ell$-deck when $\ell\ge 9n/10$, and reconstruct the degree sequence when $\ell\ge\sqrt{2n\log(2n)}$. All of these results are significant improvements on previous bounds., Comment: 29 pages, improvements to exposition and proof clarity

A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$ coincide with the distances between the corresponding vertices in $G$. We show that for any integer $n\ge 1$, there is a graph on $3^{n+O(\log^2 n)}$ vertices that contains isometric copies of all $n$-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest., Comment: 13 pages, no figure. v2: revised version

The deck of a graph $G$ is the multiset of cards $\{G-v:v\in V(G)\}$. Myrvold (1992) showed that the degree sequence of a graph on $n\geq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing., Comment: 10 pages

Following a given ordering of the edges of a graph $G$, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index $\chi'(G)$, and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let $\chi_c'(G)$ be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether $\chi_c'(G)>\chi'(G)$. We prove that $\chi'(G)=\chi_c'(G)$ if $G$ is bipartite, and that $\chi_c'(G)\leq 4$ if $G$ is subcubic., Comment: Comments welcome, 12 pages

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to prove optimal results for the asymptotic dimension of graphs of bounded layered treewidth and graphs of polynomial growth, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours., Comment: This paper is essentially a combination of arXiv:2007.03582 and the non-algorithmic part of arXiv:2007.08771, where some results in arXiv:2007.03582 are strengthened. v2: fix the authors names. v3: update based on referees' comments, improve the bound for layered treewidth in Theorem 1.12 from 12 to 1, and simplify the proof without the use of fat bananas

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing $2^{\Omega(n^2)}$ $n$-vertex graphs as $n\to \infty$. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of $n/4+o(n)$ bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of $n/4+o(n)$ bits per vertex and comparability labelling scheme for posets with labels of $n/4+o(n)$ bits per element. All these results are best possible, up to the lower order term., Comment: 17 pages - to appear in the proceedings of STOC 2021

Eilers et al. have recently completed the geometric classification of unital graph $C^\ast$-algebras up to Morita equivalence using a set of moves on the corresponding digraphs. We explore the question of whether these moves preserve the nonzero elements of the spectrum of a finite digraph, which in this paper is allowed to have loops and parallel edges. We consider several different digraph spectra that have been studied in the literature, answering this question for the Laplace and adjacency spectra, their skew counterparts, the symmetric adjacency spectrum, the adjacency spectrum of the line digraph, the Hermitian adjacency spectrum, and the normalized Laplacian, considering in most cases two ways that these spectra can be defined in the presence of parallel edges. We show that the adjacency spectra of the digraph and line digraph are preserved by a subset of the moves, and the skew adjacency and Laplace spectra are preserved by the Cuntz splice. We give counterexamples to show that the other spectra are not preserved by the remaining moves. The same results hold if one restricts to the class of strongly connected digraphs., Comment: 29 pages, 8 figures, 2 tables. v2: corrected errors, improved exposition, added Example 5.3

Alon and F\"{u}redi (1993) showed that the number of hyperplanes required to cover $\{0,1\}^n\setminus \{0\}$ without covering $0$ is $n$. We initiate the study of such exact hyperplane covers of the hypercube for other subsets of the hypercube. In particular, we provide exact solutions for covering $\{0,1\}^n$ while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open., Comment: Small fixes and updated code

Let G be a graph on n vertices. The Laplacian matrix of G, denoted by L(G), is defined as L(G) = D(G) - A(G), where A(G) is the adjacency matrix of G and D(G) is the diagonal matrix of the vertex degrees of G. A graph G is said to be L-integral is all eigenvalues of the matrix L(G) are integers. In this paper, we characterize all L-integral non-bipartite graphs among all connected graphs with at most two vertices of degree larger than or equal to three., Comment: 17 pages

We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first algorithm to achieve an $f(t)$-approximation for some function $f$. Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least $th+2$ has treewidth at least $t$ or contains a subdivision of a complete binary tree of height $h+1$. The bound $th+2$ is best possible up to a multiplicative constant. This result was motivated by, and implies (with $c=2$), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant $c$ such that every graph with pathwidth $\Omega(k^c)$ has treewidth at least $k$ or contains a subdivision of a complete binary tree of height $k$. Our main technical algorithm takes a graph $G$ and some (not necessarily optimal) tree decomposition of $G$ of width $t'$ in the input, and it computes in polynomial time an integer $h$, a certificate that $G$ has pathwidth at least $h$, and a path decomposition of $G$ of width at most $(t'+1)h+1$. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height $h$. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth., Comment: v4: small changes following further comments from a referee. v3: revised following referees' comments, corrects a serious error in the previous version

In this paper we study the growth of the differential identities of some algebras with derivations, i.e., associative algebras where a Lie algebra $L$ (and its universal enveloping algebra $U(L)$) acts on them by derivations. In particular, we study in detail the differential identities and the cocharacter sequences of some algebras whose sequence of differential codimensions has polynomial growth. Moreover, we shall give a complete description of the differential identities of the algebra $UT_2$ of $2\times 2$ upper triangular matrices endowed with all possible action of a Lie algebra by derivations. Finally, we present the structure of the differential identities of the infinite dimensional Grassmann $G$ with respect to the action of a finite dimensional Lie algebra $L$ of inner derivations., Comment: Proceedings of workshop "Polynopmial identities in algebras", Springer INdAM Series

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. When restricted to graphs and their shortest paths metric, the asymptotic dimension can be seen as a large scale version of weak diameter colorings (also known as weak diameter network decompositions), i.e. colorings in which each monochromatic component has small weak diameter. In this paper, we prove that for any $p$, the class of graphs excluding $K_{3,p}$ as a minor has asymptotic dimension at most 2. This implies that the class of all graphs embeddable on any fixed surface (and in particular the class of planar graphs) has asymptotic dimension 2, which gives a positive answer to a recent question of Fujiwara and Papasoglu. Our result extends from graphs to Riemannian surfaces. We also prove that graphs of bounded pathwidth have asymptotic dimension at most 1 and graphs of bounded layered pathwidth have asymptotic dimension at most 2. We give some applications of our techniques to graph classes defined in a topological or geometrical way, and to graph classes of polynomial growth. Finally we prove that the class of bounded degree graphs from any fixed proper minor-closed class has asymptotic dimension at most 2. This can be seen as a large scale generalization of the result that bounded degree graphs from any fixed proper minor-closed class are 3-colorable with monochromatic components of bounded size. This also implies that (infinite) Cayley graphs avoiding some minor have asymptotic dimension at most 2, which solves a problem raised by Ostrovskii and Rosenthal., Comment: 35 pages, 4 figures - v3: correction of the statements of Theorem 5.2, Corollary 5.3 and Theorem 5.9. Most of the results in this paper have been merged to arXiv:2012.02435

In this work, we continue the study of vertex colorings of graphs, in which adjacent vertices are allowed to be of the same color as long as each monochromatic connected component is of relatively small cardinality. We focus on colorings with two and three available colors and present improved bounds on the size of the monochromatic connected components for two meaningful subclasses of planar graphs, namely maximal outerplanar graphs and complete planar 3-trees.

It is known that the polyomino ideal of simple polyominoes is prime. In this paper, we focus on multiply connected polyominoes, namely polyominoes with holes, and observe that the non-existence of a certain sequence of inner intervals of the polyomino, called zig-zag walk, gives a necessary condition for the primality of the polyomino ideal. Moreover, by computational approach, we prove that for all polyominoes with rank less than or equal to 14 the above condition is also sufficient. Lastly, we present an infinite class of prime polyomino ideals., Comment: In this version we proved that the grid polyominoes are primes without the use of Groebner basis (see previous version). In particular, we prove that the polyomino ideal is equal to the toric ideal J_P associated to the polyomino as we defined in Section 3

A subspace of $\mathbb{F}_2^n$ is called cyclically covering if every vector in $\mathbb{F}_2^n$ has a cyclic shift which is inside the subspace. Let $h_2(n)$ denote the largest possible codimension of a cyclically covering subspace of $\mathbb{F}_2^n$. We show that $h_2(p)= 2$ for every prime $p$ such that 2 is a primitive root modulo $p$, which, assuming Artin's conjecture, answers a question of Peter Cameron from 1991. We also prove various bounds on $h_2(ab)$ depending on $h_2(a)$ and $h_2(b)$ and extend some of our results to a more general set-up proposed by Cameron, Ellis and Raynaud., Comment: 36 pages

A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph $G$ is a decomposition $\mathcal{D}$ of $G$ such that every subgraph $H \in \mathcal{D}$ is locally irregular. A graph is said to be decomposable if it admits a locally irregular decomposition. We prove that any decomposable split graph can be decomposed into at most three locally irregular subgraphs and we characterize all split graphs whose decomposition can be into one, two or three locally irregular subgraphs.

We continue the study by Melo and Winter [arXiv:1712.01763, 2017] on the possible intersection sizes of a $k$-dimensional subspace with the vertices of the $n$-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than $2^{k-1}$ (the "large" sizes) are of the form $2^{k-1}+2^i$. We show that this is almost true: the large intersection sizes are either of this form or of the form $35\cdot 2^{k-6}$. We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the "small" values is missing.

The deck of a graph $G$ is given by the multiset of (unlabelled) subgraphs $\{G-v:v\in V(G)\}$. The subgraphs $G-v$ are referred to as the cards of $G$. Brown and Fenner recently showed that, for $n\geq29$, the number of edges of a graph $G$ can be computed from any deck missing 2 cards. We show that, for sufficiently large $n$, the number of edges can be computed from any deck missing at most $\frac1{20}\sqrt{n}$ cards., Comment: 15 pages

If $\mathcal{W}$ is the simple random walk on the square lattice $\mathbb{Z}^2$, then $\mathcal{W}$ induces a random walk $\mathcal{W}_G$ on any spanning subgraph $G\subset \mathbb{Z}^2$ of the lattice as follows: viewing $\mathcal{W}$ as a uniformly random infinite word on the alphabet $\{\mathbf{x}, -\mathbf{x}, \mathbf{y}, -\mathbf{y} \}$, the walk $\mathcal{W}_G$ starts at the origin and follows the directions specified by $\mathcal{W}$, only accepting steps of $\mathcal{W}$ along which the walk $\mathcal{W}_G$ does not exit $G$. For any fixed subgraph $G \subset \mathbb{Z}^2$, the walk $\mathcal{W}_G$ is distributed as the simple random walk on $G$, and hence $\mathcal{W}_G$ is almost surely recurrent in the sense that $\mathcal{W}_G$ visits every site reachable from the origin in $G$ infinitely often. This fact naturally leads us to ask the following: does $\mathcal{W}$ almost surely have the property that $\mathcal{W}_G$ is recurrent for \emph{every} subgraph $G \subset \mathbb{Z}^2$? We answer this question negatively, demonstrating that exceptional subgraphs exist almost surely. In fact, we show more to be true: exceptional subgraphs continue to exist almost surely for a countable collection of independent simple random walks, but on the other hand, there are almost surely no exceptional subgraphs for a branching random walk., Comment: 19 pages, submitted

A graph is called $P_t$-free if it does not contain the path on $t$ vertices as an induced subgraph. Let $H$ be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for (list) graph homomorphisms from $G$ to $H$ can be calculated in subexponential time $2^{O\left(\sqrt{tn\log(n)}\right)}$ for $n=|V(G)|$ in the class of $P_t$-free graphs $G$. As a corollary, we show that the number of 3-colourings of a $P_t$-free graph $G$ can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of $P_t$-free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that $P_t$-free graphs have pathwidth that is linear in their maximum degree., Comment: Fixed some typo's

We give a lower bound for the Castelnuovo-Mumford regularity of binomial edge ideals of block graphs by computing the two distinguished extremal Betti numbers of a new family of block graphs, called flower graphs. Moreover, we present a linear time algorithm to compute the Castelnuovo-Mumford regularity and Krull dimension of binomial edge ideals of block graphs., Comment: Accepted in Journal of Algebra and Application

Let A be a finite or countable alphabet and let $\theta$ be a literal (anti-)automorphism onto A * (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under $\theta$ ($\theta$-invariant for short) that is, languages L such that $\theta$ (L) is a subset of L.We establish an extension of the famous defect theorem. With regards to the so-called notion of completeness, we provide a series of examples of finite complete $\theta$-invariant codes. Moreover, we establish a formula which allows to embed any non-complete $\theta$-invariant code into a complete one. As a consequence, in the family of the so-called thin $\theta$--invariant codes, maximality and completeness are two equivalent notions., Comment: arXiv admin note: text overlap with arXiv:1705.05564

Let $k$ be a positive integer and let $D$ be a digraph. A path partition $\sP$ of $D$ is a set of vertex-disjoint paths which covers $V(D)$. Its $k$-norm is defined as $\sum_{P \in \sP} \Min{|V(P)|, k}$. A path partition is $k$-optimal if its $k$-norm is minimum among all path partitions of $D$. A partial $k$-coloring is a collection of $k$ disjoint stable sets. A partial $k$-coloring $\sC$ is orthogonal to a path partition $\sP$ if each path $P \in \sP$ meets $\min\{|P|,k\}$ distinct sets of $\sC$. Berge (1982) conjectured that every $k$-optimal path partition of $D$ has a partial $k$-coloring orthogonal to it. A (path) $k$-pack of $D$ is a collection of at most $k$ vertex-disjoint paths in $D$. Its weight is the number of vertices it covers. A $k$-pack is optimal if its weight is maximum among all $k$-packs of $D$. A coloring of $D$ is a partition of $V(D)$ into stable sets. A $k$-pack $\sP$ is orthogonal to a coloring $\sC$ if each set $C \in \sC$ meets $\Min{|C|, k}$ paths of $\sP$. Aharoni, Hartman and Hoffman (1985) conjectured that every optimal $k$-pack of $D$ has a coloring orthogonal to it. A digraph $D$ is semicomplete if every pair of distinct vertices of $D$ is adjacent. A digraph $D$ is locally in-semicomplete if, for every vertex $v \in V(D)$, the in-neighborhood of $v$ induces a semicomplete digraph. Locally out-semicomplete digraphs are defined similarly. In this paper, we prove Berge's and Aharoni-Hartman-Hoffman's Conjectures for locally in/out-semicomplete digraphs.

Let $G=(V,E)$ be an $n$-vertex graph with $m$ edges. A function $f : V \cup E \rightarrow \{1, \ldots, n+m\}$ is an edge-magic labeling of $G$ if $f$ is bijective and, for some integer $k$, we have $f(u)+f(v)+f(uv) = k$ for every edge $uv \in E$. Furthermore, if $f(V) = \{1, \ldots, n\}$, then we say that $f$ is a super edge-magic labeling. A constellation, which is a collection of stars, is symmetric if the number of stars of each size is even except for at most one size. We prove that every symmetric constellation with an odd number of stars admits a super edge-magic labeling. We say that a caterpillar is of type $(r,s)$ if $r$ and $s$ are the sizes of its parts, where $r \leq s$. We also prove that every collection with an odd number of same-type caterpillars admits an edge-magic labeling.

In 1997 Bousquet-M\'elou and Eriksson introduced lecture hall partitions as the inversion vectors of elements of the parabolic quotient $\widetilde{C}/C$. We provide a new view of their correspondence that allows results in one domain to be translated into the other. We determine the equivalence between combinatorial statistics in each domain and use this correspondence to translate certain generating function formulas on lecture hall partitions to new observations about $\widetilde{C}/C$., Comment: 15 pages

Let $A$ be a finite or countable alphabet and let $\theta$ be literal (anti)morphism onto $A^*$ (by definition, such a correspondence is determinated by a permutation of the alphabet). This paper deals with sets which are invariant under $\theta$ ($\theta$-invariant for short).We establish an extension of the famous defect theorem. Moreover, we prove that for the so-called thin $\theta$-invariant codes, maximality and completeness are two equivalent notions. We prove that a similar property holds in the framework of some special families of $\theta$-invariant codes such as prefix (bifix) codes, codes with a finite deciphering delay, uniformly synchronized codes and circular codes. For a special class of involutive antimorphisms, we prove that any regular $\theta$-invariant code may be embedded into a complete one., Comment: To appear in Acts of WORDS 2017

Inversion sequences of length $n$, $\mathbf{I}_n$, are integer sequences $(e_1, \ldots, e_n)$ with $0 \leq e_i < n$ for each $i$. The study of patterns in inversion sequences was initiated recently by Mansour-Shattuck and Corteel-Martinez-Savage-Weselcouch through a systematic study of inversion sequences avoiding words of length 3. We continue this investigation by generalizing the notion of a pattern to a fixed triple of binary relations $(\rho_1,\rho_2,\rho_3)$ and consider the set $\mathbf{I}_n(\rho_1,\rho_2,\rho_3)$ consisting of those $e \in \mathbf{I}_n$ with no $i < j < k$ such that $e_i \rho_1 e_j$, $e_j \rho_2 e_k$, and $e_i \rho_3 e_k$. We show that "avoiding a triple of relations" can characterize inversion sequences with a variety of monotonicity or unimodality conditions, or with multiplicity constraints on the elements. We uncover several interesting enumeration results and relate pattern avoiding inversion sequences to familiar combinatorial families. We highlight open questions about the relationship between pattern avoiding inversion sequences and families such as plane permutations and Baxter permutations. For several combinatorial sequences, pattern avoiding inversion sequences provide a simpler interpretation than otherwise known.

We present an application of Hilbert quasi-polynomials to order domains, allowing the effective check of the second order-domain condition in a direct way. We also provide an improved algorithm for the computation of the related Hilbert quasi-polynomials. This allows to identify order domain codes more easily.

Over the past twenty years, lecture hall partitions have emerged as fundamental combinatorial structures, leading to new generalizations and interpretations of classical theorems and new results. In recent years, geometric approaches to lecture hall partitions have used polyhedral geometry to discover further properties of these rich combinatorial objects. In this paper we give an overview of some of the surprising connections that have surfaced in the process of trying to understand the lecture hall partitions., Comment: 37 pages, to appear in JCTA

In this paper we show that the diameter of a d-dimensional lattice polytope in [0,k]^n is at most (k - 1/2) d. This result implies that the diameter of a d-dimensional half-integral polytope is at most 3/2 d. We also show that for half-integral polytopes the latter bound is tight for any d.