Combinatorics (math.CO)

Abstract: Similar pictures appear in various branches of mathematics. Sometimes this similarity gives rise to deep theorems. Mentioning such a similarity between hexagonal tilings, cubes in 3-space, configurations of lines and braid groups, we prove that braids act on configurations of lines.

Abstract: We prove that a lexicographical extension of a Euclidean oriented matroid remains Euclidean. Based on that result we show that in a Euclidean oriented matroid program there exists a topological sweep inducing a recursive atom-ordering (a shelling of the cocircuits) of the tope cell of the feasible region. We extend that sweep and obtain also a vertex-shelling of the whole oriented matroid and finally describe some connections to the notion of stackable zontope tilings and to a counterexample of a conjecture of A. Mandel.

Abstract: In Combinatorial Game Theory, short game forms are defined recursively over all the positions the two players are allowed to move to. A form is decomposable if it can be expressed as a disjunctive sum of two forms with smaller birthday. If there are no such summands, then the form is indecomposable. The main contribution of this document is the characterization of the indecomposable nimbers and the characterization of the indecomposable numbers. More precisely, a nimber is indecomposable if and only if its size is a power of two, and a number is indecomposable if and only if its absolute value is less or equal than one.

Abstract: Given a graph G, a colouring is an assignment of colours to the vertices of G so that no two adjacent vertices are coloured the same. If all colour classes have size at most t, then we call the colouring t-bounded, and the t-bounded chromatic number of G, denoted by $\chi_t(G)$, is the minimum number of colours in such a colouring. Every colouring of G is then $\alpha(G)$-bounded, where $\alpha(G)$ denotes the size of a largest independent set. We study colourings of the random graph G(n,1/2) and of the corresponding uniform random graph G(n,m) with $m=\left \lfloor \frac 12 {n \choose 2} \right \rfloor$. We show that $\chi_t(G(n,m))$ is maximally concentrated on at most two explicit values when $t = \alpha(G(n,m))-2$. This behaviour stands in stark contrast to the normal chromatic number, which was recently shown not to be concentrated on any sequence of intervals of length $n^{1/2-o(1)}$. Moreover, when $t = \alpha(G_{n, 1/2})-1$, we find an explicit interval of length $n^{0.99}$ that contains $\chi_t(G(n, 1/2))$ with high probability. Both results have profound consequences: the former is at the core of the tantalising Zigzag Conjecture on the distribution of the chromatic number of G(n, 1/2) and justifies one of its main hypotheses, while the latter is an important ingredient in the proof of a non-concentration result by the first author and Oliver Riordan for $\chi(G(n, 1/2))$ which is conjectured to be optimal. Our two aforementioned results are consequences of a more general statement. We consider a class of colourings that we call tame and which fulfil some natural, albeit technical, conditions. We provide tight bounds for the probability of existence of such colourings, and then we apply these bounds to the case of t-bounded colourings. As a further consequence of our general result, we show two-point concentration of the equitable chromatic number of G(n,m).