Combinatorics (math.CO)

Abstract: The $r$-flip-width of a graph, for $r\in \mathbb{N}\cup \{\infty\}$, is a graph parameter defined in terms of a variant of the cops and robber game, called a flipper game, and it was introduced by Toru\'{n}czyk [Flip-width: Cops and robber on dense graphs, arXiv:2302.00352]. We prove that for every $r\in (\mathbb{N}\setminus \{1\})\cup \{\infty\}$, the class of graphs of $r$-flip-width at most $2$ is exactly the class of ($C_5$, bull, gem, co-gem)-free graphs, which are known as totally decomposable graphs with respect to bi-joins.

Abstract: We give new characterizations for the class of uniformly dense matroids, and we describe applications to graphic and real representable matroids. We show that a matroid is uniformly dense if and only if its base polytope contains a point with constant coordinates, and if and only if there exists a measure on the bases such that every element of the ground set has equal probability to be in a random basis with respect to this measure. As one application, we derive new spectral, structural and classification results for uniformly dense graphic matroids. In particular, we show that connected regular uniformly dense graphs are $1$-tough and thus contain a (near-)perfect matching. As a second application, we show that strictly uniformly dense real representable matroids can be represented by projection matrices with constant diagonal and that they are parametrized by a subvariety of the real Grassmannian.

Abstract: Let $m_{\lambda }$ be the monomial symmetric functions with $\lambda $ integer partition of $n=\left| \lambda \right| $. For the specialization of the $q$-deformation of the exponential, we prove that to each $m_{\lambda }$ is accociated a polynomial $J_{\lambda }\left( q\right) $% , whose coefficients belong to $\mathbb{Z}$. $J_{\lambda }$ is a generalization of the case $\lambda =\left( n\right) $ for which $J_{\left( n\right) }=J_{n}$ is the enumerator polynomial of inversion in tree on $n$ vertices. Some relations between $J_{\lambda }$ and $J_{n,r}$ are obtained, these $J_{n,r}$ having been introduced in $\left[ 4\right] $ from a $q$% -analog of certain symmetric functions, and being themselves inversion enumerator polynomials which generalize $J_{n,1}=J_{n}$. From the calculation of $J_{\lambda }$ for $\left| \lambda \right| \leq 6$, we conjecture that the coefficients of each $J_{\lambda }$\ are strictly positive and log-concave. As a consequence of Huh's works on the $h$-vector of matroid complex (Theorem 3 of $\left[ 7\right] $), it is shown that the coefficients of \ all $J_{n,r}$ are strictly positive and log-concave, which gives a second argument for these conjectures. We prove that the last $n-1$ coefficients of $J_{\lambda }$ are proportional to the first $n-1$ coefficients of column $n-r-1$ of Pascal's triangle, $r$ being the length of $\lambda $. This is a third argument to state the conjectures since the log-concavity of these columns are well known. The calculation of $J_{\left( 3,2,1\right) }$ shows the existence of a obstacle, if one wants to prove the conjectures by application of the theorem of Huh, quoted above.

Abstract: For a simple graph $G$, the $2$-distance graph, $D_2(G)$, is a graph with the vertex set $V(G)$ and two vertices are adjacent if and only if their distance is $2$ in the graph $G$. In this paper, we characterize all graphs with connected 2-distance graph. For graphs with diameter 2, we prove that $D_2(G)$ is connected if and only if $G$ has no spanning complete bipartite subgraphs. For graphs with a diameter greater than 2, we define a maximal Fine set and by contracting $G$ on these subsets, we get a new graph $\hat G$ such that $D_2(G)$ is connected if and only if $D_2(\hat G)$ is connected. Especially, $D_2(G)$ is disconnected if and only if $\hat G$ is bipartite.

Abstract: We introduce the Primitive Eulerian polynomial $P_{\cal A}(z)$ of a central hyperplane arrangement ${\cal A}$. It is a reparametrization of its cocharacteristic polynomial. Previous work of the first author implicitly show that, for simplicial arrangements, $P_{\cal A}(z)$ has nonnegative coefficients. For reflection arrangements of type A and B, the same work interprets the coefficients of $P_{\cal A}(z)$ using the (flag)excedance statistic on (signed) permutations. The main result of this article is to provide an interpretation of the coefficients of $P_{\cal A}(z)$ for all simplicial arrangements only using the geometry and combinatorics of ${\cal A}$. This new interpretation sheds more light to the case of reflection arrangements and, for the first time, gives combinatorial meaning to the coefficients of the Primitive Eulerian polynomial of the reflection arrangement of type D. In type B, we find a connection between the Primitive Eulerian polynomial and the $1/2$-Eulerian polynomial of Savage and Viswanathan (2012). We present some real-rootedness results and conjectures for $P_{\cal A}(z)$.

Abstract: The quadratic embedding constant (QEC) of a finite, simple, connected graph $G$ is the maximum of the quadratic form of the distance matrix of $G$ on the subset of the unit sphere orthogonal to the all-ones vector. The study of these QECs was motivated by the classical work of Schoenberg on quadratic embedding of metric spaces [Ann. of Math., 1935] and [Trans. Amer. Math. Soc., 1938]. In this article, we provide sharp upper and lower bounds for the QEC of trees. We next explore the relation between distance spectra and quadratic embedding constants of graphs - and show two further results: $(i)$ We show that the quadratic embedding constant of a graph is zero if and only if its second largest distance eigenvalue is zero. $(ii)$ We identify a new subclass of nonsingular graphs whose QEC is the second largest distance eigenvalue. Finally, we show that the QEC of the cluster of an arbitrary graph $G$ with either a complete or star graph can be computed in terms of the QEC of $G$. As an application of this result, we provide new families of examples of graphs of QE class.