Combinatorics (math.CO)

Abstract: A $k$-uniform tight cycle is a $k$-graph with a cyclic order of its vertices such that every $k$ consecutive vertices from an edge. We show that for $k\geq 3$, every red-blue edge-coloured complete $k$-graph on $n$ vertices contains $k$ vertex-disjoint monochromatic tight cycles that together cover $n - o(n)$ vertices.

Abstract: In this paper, we present a generalization of Hayden's theorem [7, Theorem 4.2] for $G$-codes over finite Frobenius rings. A lattice theoretical form of this generalization is also given. Moreover, Astumi's MacWilliams identity [1, Theorem 1] is generalized in several ways for different weight enumerators of $G$-codes over finite Frobenius rings. Furthermore, we provide the Jacobi analogue of Astumi's MacWilliams identity for $G$-codes over finite Frobenius rings. Finally, we study the relation between $G$-codes and its corresponding $G$-lattices.

Abstract: A $k$-star colouring of a graph $G$ is a function $f:V(G)\to\{0,1,\dots,k-1\}$ such that $f(u)\neq f(v)$ for every edge $uv$ of $G$, and every bicoloured connected subgraph of $G$ is a star. The star chromatic number of $G$, $\chi_s(G)$, is the least integer $k$ such that $G$ is $k$-star colourable. We prove that $\chi_s(G)\geq \lceil (d+4)/2\rceil$ for every $d$-regular graph $G$ with $d\geq 3$. We reveal the structure and properties of even-degree regular graphs $G$ that attain this lower bound. The structure of such graphs $G$ is linked with a certain type of Eulerian orientations of $G$. Moreover, this structure can be expressed in the LC-VSP framework of Telle and Proskurowski (SIDMA, 1997), and hence can be tested by an FPT algorithm with the parameter either treewidth, cliquewidth, or rankwidth. We prove that for $p\geq 2$, a $2p$-regular graph $G$ is $(p+2)$-star colourable only if $n:=|V(G)|$ is divisible by $(p+1)(p+2)$. For each $p\geq 2$ and $n$ divisible by $(p+1)(p+2)$, we construct a $2p$-regular Hamiltonian graph on $n$ vertices which is $(p+2)$-star colourable. The problem $k$-STAR COLOURABILITY takes a graph $G$ as input and asks whether $G$ is $k$-star colourable. We prove that 3-STAR COLOURABILITY is NP-complete for planar bipartite graphs of maximum degree three and arbitrarily large girth. Besides, it is coNP-hard to test whether a bipartite graph of maximum degree eight has a unique 3-star colouring up to colour swaps. For $k\geq 3$, $k$-STAR COLOURABILITY of bipartite graphs of maximum degree $k$ is NP-complete, and does not even admit a $2^{o(n)}$-time algorithm unless ETH fails.

Abstract: The boundary rigidity problem is a classical question from Riemannian geometry: if $(M, g)$ is a Riemannian manifold with smooth boundary, is the geometry of $M$ determined up to isometry by the metric $d_g$ induced on the boundary $\partial M$? In this paper, we consider a discrete version of this problem: can we determine the combinatorial type of a finite cube complex from its boundary distances? As in the continuous case, reconstruction is not possible in general, but one expects a positive answer under suitable contractibility and non-positive curvature conditions. Indeed, in two dimensions Haslegrave gave a positive answer to this question when the complex is a finite quadrangulation of the disc with no internal vertices of degree less than $4$. We prove a $3$-dimensional generalisation of this result: the combinatorial type of a finite CAT(0) cube complex with an embedding in $\mathbb{R}^3$ can be reconstructed from its boundary distances. Additionally, we prove a direct strengthening of Haslegrave's result: the combinatorial type of any finite 2-dimensional CAT(0) cube complex can be reconstructed from its boundary distances.

Abstract: Sintiari and Trotignon showed that for every $h\geq 1$, there are (even-hole, $K_4$)-free graphs of arbitrarily large treewidth in which every $h$-vertex induced subgraph is chordal. We prove the converse: given a graph $H$, every (even-hole, $K_4$)-free graph of large enough treewidth contains an induced subgraph isomorphic to $H$, if and only if $H$ is chordal (and $K_4$-free). As an immediate corollary, the above result settles a conjecture of Sintiari and Trotignon, asserting that every (even-hole, $K_4$)-free graph of sufficiently large treewidth contains an induced subgraph isomorphic to the graph obtained from the two-edge path by adding a universal vertex (also known as the "diamond"). We further prove yet another extension of their conjecture with "$K_4$" replaced by an arbitrary complete graph and the "two-edge path" replaced by an arbitrary forest. This turns out to characterize forests: given a graph $F$, for every $t\geq 1$, every (even-hole, $K_t$)-free graph of sufficiently large treewidth contains an induced subgraph isomorphic to the graph obtained from $F$ by adding a universal vertex, if and only if $F$ is a forest.

Abstract: We say that a signed graph is $k$-critical if it is not $k$-colorable but every one of its proper subgraphs is $k$-colorable. Using the definition of colorability due to Naserasr, Wang, and Zhu that extends the notion of circular colorability, we prove that every $3$-critical signed graph on $n$ vertices has at least $\frac{3n-1}{2}$ edges, and that this bound is asymptotically tight. It follows that every signed planar or projective-planar graph of girth at least $6$ is (circular) $3$-colorable, and for the projective-planar case, this girth condition is best possible. To prove our main result, we reformulate it in terms of the existence of a homomorphism to the signed graph $C_{3}^*$, which is the positive triangle augmented with a negative loop on each vertex.

Abstract: An edge-coloured graph is said to be rainbow if no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decade as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstra\"ete from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on $n$ vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of $(\log n)^{2+o(1)}$ for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the $o(1)$ term in Tomon's bound, showing a bound of $O(\log^2 n)$. We prove an upper bound of $(\log n)^{1+o(1)}$ for this maximum possible average degree when there is no rainbow cycle. Our result is tight up to the $o(1)$ term, and so it essentially resolves this question. In addition, we observe a connection between this problem and several questions in additive number theory, allowing us to extend existing results on these questions for abelian groups to the case of non-abelian groups.