Combinatorics (math.CO)

Abstract: We define the Laplacian matrix and the Jacobian group of a finite graph of groups. We prove analogues of the matrix tree theorem and the class number formula for the order of the Jacobian of a graph of groups. Given a group $G$ acting on a graph $X$, we define natural pushforward and pullback maps between the Jacobian groups of $X$ and the quotient graph of groups $X/\!/G$. For the case $G=\mathbb{Z}/2\mathbb{Z}$, we also prove a combinatorial formula for the order of the kernel of the pushforward map.

Abstract: Ceballos and Pons introduced the $s$-weak order on $s$-decreasing trees, for any weak composition $s$. They proved that it has a lattice structure and further conjectured that it can be realized as the $1$-skeleton of a polyhedral subdivision of a polytope. We answer their conjecture in the case where $s$ is a strict composition by providing three geometric realizations of the $s$-permutahedron. The first one is the dual graph of a triangulation of a flow polytope of high dimension. The second one, obtained using the Cayley trick, is the dual graph of a fine mixed subdivision of a sum of hypercubes that has the conjectured dimension. The third one, obtained using tropical geometry, is the $1$-skeleton of a polyhedral complex for which we can provide explicit coordinates of the vertices and whose support is a permutahedron as conjectured.

Abstract: In this note we study the uniqueness problem for collections of pennies and marbles. More generally, consider a collection of unit $d$-spheres that may touch but not overlap. Given the existence of such a collection, one may analyse the contact graph of the collection. In particular we consider the uniqueness of the collection arising from the contact graph. Using the language of graph rigidity theory, we prove a precise characterisation of uniqueness (global rigidity) in dimensions 2 and 3 when the contact graph is additionally chordal. We then illustrate a wide range of examples in these cases. That is, we illustrate collections of marbles and pennies that can be perturbed continuously (flexible), are locally unique (rigid) and are unique (globally rigid). We also contrast these examples with the usual generic setting of graph rigidity.

Abstract: Let $\mathcal{F}$ and $\mathcal{G}$ be two families of $[n]$, where $[n]=\{1,2,...,n\}$. If $A\not\subset B$ and $B\not\subset A$ hold for all $A\in\mathcal{F}$ and $B\in\mathcal{G}$, P. Frankl and Jian Wang called that $\mathcal{F}$ and $\mathcal{G}$ are cross-Sperner. Set $\mathcal{I}(\mathcal{F},\mathcal{G})=\{A\cap B:A\in\mathcal{F},B\in\mathcal{G}\}$. Define $m(n)={\rm{max}}\{|\mathcal{I}(\mathcal{F},\mathcal{G})|:\mathcal{F},\mathcal{G}\subset2^{[n]}~{\rm{are~cross}}$-${\rm{sperner}}\}$. In this note, we prove that $2^n-2^{\lfloor\frac{n}{2}\rfloor}-2^{\lceil\frac{n}{2}\rceil}+1$ for $n>1$. This not only solves an open problem proposed by P. Frankl and Jian Wang but also completes the extremal problem of cross-sperner families.

Abstract: In this paper, we provide a construction of $(q+1)$-ovoids of the hyperbolic quadric $Q^+(7,q)$, $q$ an odd prime power, by glueing $(q+1)/2$-ovoids of the elliptic quadric $Q^-(5,q)$. This is possible by controlling some intersection properties of (putative) $m$-ovoids of elliptic quadrics. It yields eventually $(q+1)$-ovoids of $Q^+(7,q)$ not coming from a $1$-system. Secondly, we also construct $m$-ovoids for $m \in \{ 2,4,6,8,10\}$ in $Q^+(7,3)$. Therefore we first investigate how to construct spreads of $\pg(3,q)$ that have as many secants to an elliptic quadric as possible.

Abstract: A graph $H$ is common if the limit as $n\to\infty$ of the minimum density of monochromatic labelled copies of $H$ in an edge colouring of $K_n$ with red and blue is attained by a sequence of quasirandom colourings. We apply an information-theoretic approach to show that certain graphs obtained from odd cycles and paths via gluing operations are common. In fact, for every pair $(H_1,H_2)$ of such graphs, there exists $p\in(0,1)$ such that an appropriate linear combination of red copies of $H_1$ and blue copies of $H_2$ is minimized by a quasirandom colouring in which $p\binom{n}{2}$ edges are red; such a pair $(H_1,H_2)$ is said to be $(p,1-p)$-common. Our approach exploits a strengthening of the common graph property for odd cycles that was recently proved using Schur convexity. We also exhibit a $(p,1-p)$-common pair $(H_1,H_2)$ such that $H_2$ is uncommon.

Abstract: We consider the eccentric graph of a graph $G$, denoted by $ecc(G)$, which has the same vertex set as $G$, and two vertices in the eccentric graph are adjacent iff their distance in $G$ is equal to the eccentricity of one of them. In this paper, we present a fundamental requirement for the isomorphism between $ecc(G)$ and the complement of $G$, and show that the previous necessary condition given in the literature is inadequate. Also we obtain that diameter of $ecc(T)$ is at most $3$ for any tree and get some characterizations of the eccentric graph of trees.