Combinatorics (math.CO)

Abstract: In this purely experimental work we try to represent the set of plane maps with 3 vertices and 3 faces as a bipartite ribbon graph. In particular, this construction allows one to estimate the genus of the initial set.

Abstract: Let $G$ be a graph. A total dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex in $G$ is adjacent to a vertex in $S$. Recently, the following question was proposed: "Is it true that every connected cubic graph containing a $3$-cycle has two vertex disjoint total dominating sets?" In this paper, we give a negative answer to this question. Moreover, we prove that if we replace $3$-cycle with $4$-cycle the answer is affirmative. This implies every connected cubic graph containing a diamond (the complete graph of order $4$ minus one edge) as a subgraph can be partitioned into two total dominating sets, a result that was proved in 2017.

Abstract: Let $G$ and $H$ be finite-dimensional vector spaces over $\mathbb{F}_p$. A subset $A \subseteq G \times H$ is said to be transverse if all of its rows $\{x \in G \colon (x,y) \in A\}$, $y \in H$, are subspaces of $G$ and all of its columns $\{y \in H \colon (x,y) \in A\}$, $x \in G$, are subspaces of $H$. As a corollary of a bilinear version of Bogolyubov argument, Gowers and the author proved that dense transverse sets contain bilinear varieties of bounded codimension. In this paper, we provide a direct combinatorial proof of this fact. In particular, we improve the bounds and evade the use of Fourier analysis and Freiman's theorem and its variants.

Abstract: For an arbitrary finite family of graphs, the distance labeling problem asks to assign labels to all nodes of every graph in the family in a way that allows one to recover the distance between any two nodes of any graph from their labels. The main goal is to minimize the number of unique labels used. We study this problem for the families $\mathcal{C}_n$ consisting of cycles of all lengths between 3 and $n$. We observe that the exact solution for directed cycles is straightforward and focus on the undirected case. We design a labeling scheme requiring $\frac{n\sqrt{n}}{\sqrt{6}}+O(n)$ labels, which is almost twice less than is required by the earlier known scheme. Using the computer search, we find an optimal labeling for each $n\le 17$, showing that our scheme gives the results that are very close to the optimum.

Abstract: A hereditary class $\cal G$ of graphs is {\em $\chi$-bounded} if there is a {\em $\chi$-binding function}, say $f$, such that $\chi(G)\le f(\omega(G))$ for every $G\in\cal G$, where $\chi(G)(\omega(G))$ denotes the chromatic (clique) number of $G$. It is known that for every $(P_3\cup P_2)$-free graph $G$, $\chi(G)\le \frac{1}{6}\omega(G)(\omega(G)+1)(\omega(G)+2)$ \cite{BA18}, and the class of $(2K_2, 3K_1)$-free graphs does not admit a linear $\chi$-binding function\cite{BBS19}. In this paper, we prove that (\romannumeral 1) $\chi(G)\le2\omega(G)$ if $G$ is ($P_3\cup P_2$, kite)-free, (\romannumeral 2) $\chi(G)\le\omega^2(G)$ if $G$ is ($P_3\cup P_2$, hammer)-free, (\romannumeral 3) $\chi(G)\le\frac{3\omega^2(G)+\omega(G)}{2}$ if $G$ is ($P_3\cup P_2, C_5$)-free. Furthermore, we also discuss $\chi$-binding functions for $(P_3\cup P_2, K_4)$-free graphs.

Abstract: We consider two multiplicative statistics on the set of integer partitions: the norm of a partition, which is the product of its parts, and the supernorm of a partition, which is the product of the prime numbers $p_i$ indexed by its parts $i$. We introduce and study new statistics that are sums of reciprocals of supernorms on three statistical ensembles of partitions, labelled by their size $|\lambda|=n$, their perimeter equaling $n$, and their largest part equaling $n$. We show that the cumulative statistics of the reciprocal supernorm for each of the three ensembles are asymptotic to $e^{\gamma} \log n$ as $n \to \infty$.

Abstract: We introduce a recursive procedure for computing the number of realizations of a minimally rigid graph on the sphere up to rotations. We accomplish this by combining two ingredients. The first is a framework that allows us to think of such realizations as of elements of a moduli space of stable rational curves with marked points. The second is the idea of splitting a minimally rigid graph into two subgraphs, called calligraphs, that admit one degree of freedom and that share only a single edge and a further vertex. This idea has been recently employed for realizations of graphs in the plane up to isometries. The key result is that we can associate to a calligraph a triple of natural numbers with a special property: whenever a minimally rigid graph is split into two calligraphs, the number of realizations of the former equals the product of the two triples of the latter, where this product is specified by a fixed quadratic form. These triples and quadratic form codify the fact that we express realizations as intersections of two curves on the blowup of a sphere along two pairs of complex conjugate points.

Abstract: A classical problem, due to Gerencs\'er and Gy\'arf\'as from 1967, asks how large a monochromatic connected component can we guarantee in any $r$-edge colouring of $K_n$? We consider how big a connected component can we guarantee in any $r$-edge colouring of $K_n$ if we allow ourselves to use up to $s$ colours. This is actually an instance of a more general question of Bollob\'as from about 20 years ago which asks for a $k$-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided $n$ is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. We also consider a generalisation in a similar direction of a question first considered by Erd\H{o}s and R\'enyi in 1956, who considered given $n$ and $m$, what is the smallest number of $m$-cliques which can cover all edges of $K_n$? This problem is essentially equivalent to the question of what is the minimum number of vertices that are certain to be incident to at least one edge of some colour in any $r$-edge colouring of $K_n$. We consider what happens if we allow ourselves to use up to $s$ colours. We obtain a more complete understanding of the answer to this question for large $n$, in particular determining it up to a constant factor for all $1\le s \le r$, as well as obtaining much more precise results for various ranges including the correct asymptotics for essentially the whole range.

Abstract: A Neumaier graph is a non-complete edge-regular graph containing a regular clique. In this work, we prove several results on the existence of small strictly Neumaier graphs. In particular, we present a theoretical proof of the uniqueness of the smallest Neumaier graphs with parameters $(16,9,4;2,4)$, we establish the existence of $(25,12,5;2,5)$, and we disprove the existence of Neumaier graphs with parameters $(25,16,9;3,5)$, $(28,18,11;4,7)$, $(33,24,17;6,9)$, $(35,22,12;3,5)$ and $(55,30,18;3,5)$. Our proofs use combinatorial techniques and a novel application of integer programming methods.