Combinatorics (math.CO)

Abstract: An edge e is normal in a proper edge-coloring of a cubic graph G if the number of distinct colors on four edges incident to e is 2 or 4: A normal edge-coloring of G is a proper edge-coloring in which every edge of G is normal. The Petersen Coloring Conjecture is equivalent to stating that every bridgeless cubic graph has a normal 5-edge-coloring. Since every 3-edge-coloring of a cubic graph is trivially normal, it is suficient to consider only snarks to establish the conjecture. In this paper, we consider a class of superpositioned snarks obtained by choosing a cycle C in a snark G and superpositioning vertices of C by one of two simple supervertices and edges of C by superedges Hx;y, where H is any snark and x; y any pair of nonadjacent vertices of H: For such superpositioned snarks, two suficient conditions are given for the existence of a normal 5-edge-coloring. The first condition yields a normal 5-edge-coloring for all hypohamiltonian snarks used as superedges, but only for some of the possible ways of connecting them. In particular, since the Flower snarks are hypohamiltonian, this consequently yields a normal 5-edge-coloring for many snarks superpositioned by the Flower snarks. The second sufficient condition is more demanding, but its application yields a normal 5-edge-colorings for all superpositions by the Flower snarks. The same class of snarks is considered in [S. Liu, R.-X. Hao, C.-Q. Zhang, Berge{Fulkerson coloring for some families of superposition snarks, Eur. J. Comb. 96 (2021) 103344] for the Berge-Fulkerson conjecture. Since we established that this class has a Petersen coloring, this immediately yields the result of the above mentioned paper.

Abstract: Given a tree T, one can define the local mean at some subtree S to be the average order of subtrees containing S. It is natural to ask which subtree of order k achieves the maximal/minimal local mean among all the subtrees of the same order and what properties it has. We call such subtrees k-maximal subtrees. Wagner and Wang showed in 2016 that a 1- maximal subtree is a vertex of degree 1 or 2. This paper shows that for any integer k = 1, . . . , |T| , a k-maximal subtree has at most one leaf whose degree is greater than 2 and at least one leaf whose degree is at most 2. Furthermore, we show that a k-maximal subtree has a leaf of degree greater than 2 only when all its other leaves are leaves in T as well. In the second part, this paper introduces the local density as a normalization of local means, for the sake of comparing subtrees of different orders, and shows that the local density at subtree S is lower-bounded by 1/2 with equality if and only if S contains the core of T. On the other hand, local density can be arbitrarily close to 1.

Abstract: Maxwell counts give bounds on the numbers of edges required for Euclidean bar-joint rigidity in $\mathbb{R}^d$ in terms of the number of vertices, as well as their sparsity. In this paper, we give the necessary lower bounds on each of the face numbers of a simplex required for that simplex to be $d$-volume rigid in $\mathbb{R}^d$, using a recent application of algebraic combinatorial techniques to $d$-volume rigidity. In order to do so, we prove some facts about the $d$-volume rigidity matroid, noting combinatorial characterisations when $d = 1$ and $2$. Finally, we state a $d$-volume rigidity Vertex Removal Lemma and give an improved statement using our lower bounds.

Abstract: The $\textit{planar Tur\'an number}$ $\textrm{ex}_{\mathcal P}(n,H)$ of a graph $H$ is the maximum number of edges in an $n$-vertex planar graph without $H$ as a subgraph. Let $C_{\ell}$ denote the cycle of length $\ell$. The planar Tur\'an number $\textrm{ex}_{\mathcal P}(n,C_{\ell})$ behaves differently for $\ell\le 10$ and for $\ell\ge 11$, and it is known when $\ell \in \{3,4,5,6\}$. We prove that $\textrm{ex}_{\mathcal P}(n,C_7) \le \frac{18n}{7} - \frac{48}{7}$ for all $n > 38$, and show that equality holds for infinitely many integers $n$.

Abstract: Real, complex, and tropical algebraic geometry join forces in a new branch of mathematical physics called positive geometry. We develop the positive geometry of del Pezzo surfaces and their moduli spaces, viewed as very affine varieties. Their connected components are derived from polyhedral spaces with Weyl group symmetries. We study their canonical forms and scattering amplitudes, and we solve the likelihood equations.