Combinatorics (math.CO)

Abstract: We show that an adjoint of a loopless matroid is connected if and only if it itself is connected. Our first goal is to study the adjoint of modular matroids. We prove that a modular matroid has only one adjoint (up to isomorphism) which can be given by its opposite lattice, and proceed to present some alternative characterizations of modular matroids associated to adjoints and opposite lattices. The other purpose is to investigate the adjoint sequence $ad^0M,adM,ad^2M,\ldots$ of a connected matroid $M$. We classify such adjoint sequences into three types: finite, cyclic and convergent. For the first two types, the adjoint sequences eventually stabilize at the finite projective geometries except for free matroids. For the last type, the infinite non-repeating adjoint sequences are convergent to the infinite projective geometries.

Abstract: For graphs $G_0$, $G_1$ and $G_2$, write $G_0\longmapsto(G_1, G_2)$ if each red-blue-edge-coloring of $G_0$ yields a red $G_1$ or a blue $G_2$. The Ramsey number $r(G_1, G_2)$ is the minimum number $n$ such that the complete graph $K_n\longmapsto(G_1, G_2)$. In [Discrete Math. 312(2012)], Schelp formulated the following question: for which graphs $H$ there is a constant $0<c<1$ such that for any graph $G$ of order at least $r(H, H)$ with $\delta(G)>c|V(G)|$, $G\longmapsto(H, H)$. In this paper, we prove that for any $m>n$, if $G$ is a balanced bipartite graph of order $2(m+n-1)$ with $\delta(G)>\frac{3}{4}(m+n-1)$, then $G\longmapsto(CM_m, CM_n)$, where $CM_i$ is a matching with $i$ edges contained in a connected component. By Szem\'{e}redi's Regularity Lemma, using a similar idea as introduced by [J. Combin. Theory Ser. B 75(1999)], we show that for every $\eta>0$, there is an integer $N_0>0$ such that for any $N>N_0$ the following holds: Let $\alpha_1>\alpha_2>0$ such that $\alpha_1+\alpha_2=1$. Let $G[X, Y]$ be a balanced bipartite graph on $2(N-1)$ vertices with $\delta(G)>(\frac{3}{4}+3\eta)(N-1)$. Then for each red-blue-edge-coloring of $G$, either there exist red even cycles of each length in $\{4, 6, 8, \ldots, (2-3\eta^2)\alpha_1N\}$, or there exist blue even cycles of each length in $\{4, 6, 8, \ldots, (2-3\eta^2)\alpha_2N\}$. Furthermore, the bound $\delta(G)\geq(\frac{3}{4}+3\eta)(N-1)$ is asymptotically tight. Previous studies on Schelp's question on cycles are on diagonal case, we obtain an asymptotic result of Schelp's question for all non-diagonal cases.

Abstract: Let $A$ and $B$ be sets in a finite vector space. In this paper, we study the magnitude of the set $A\cap f(B)$, where $f$ runs through a set of transformations. More precisely, we will focus on the cases that the set of transformations is given by orthogonal matrices or orthogonal projections. One of the most important contributions of this paper is to show that if $A, B\subset \mathbb{F}_q^d$ satisfy some natural conditions then, for almost every $g\in O(d)$, there are at least $\gg q^d$ elements $z\in \mathbb{F}_q^d$ such that \[|A\cap (g(B)+z)| \sim \frac{|A||B|}{q^d}.\] This infers that $|A-gB|\gg q^d$ for almost every $g\in O(d)$. In the flavor of expanding functions, with $|A|\le |B|$, we also show that the image $A-gB$ grows exponentially. In two dimensions, the result simply says that if $|A|=q^x$ and $|B|=q^y$, as long as $0<x\le y<2$, then for almost every $g\in O(2)$, we can always find $\epsilon=\epsilon(x, y)>0$ such that $|A-gB|\gg |B|^{1+\epsilon}$. To prove these results, we need to develop a new and robust incidence bound between points and rigid motions by using a number of techniques including algebraic methods and discrete Fourier analysis. Our results are essentially sharp in odd dimensions.

Abstract: Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if $P$ is a poset with a planar cover graph, then the dimension of $P$ is bounded in terms of the number of minimal elements of $P$ and the treewidth of the cover graph of $P$. We settle this conjecture in the affirmative by strengthening a recent breakthrough result [14] by Blake, Micek, and Trotter, who proved that for each poset $P$ admitting a planar cover graph and a unique minimal element we have $\mathrm{dim}(P) \leq 2 \mathrm{se}(P) + 2$, namely, we prove that $\mathrm{dim}(P) \leq 2 \mathrm{wheel}(P) + 2$.

Abstract: We call a poset factorable if its characteristic polynomial has all positive integer roots. Inspired by inductive and divisional freeness of a central hyperplane arrangement, we introduce and study the notion of inductive posets and their superclass of divisional posets. It then motivates us to define the so-called inductive and divisional abelian (Lie group) arrangements, whose posets of layers serve as the main examples of our posets. Our first main result is that every divisional poset is factorable. Our second main result shows that the class of inductive posets contains strictly supersolvable posets, the notion recently introduced due to Bibby and Delucchi (2022). This result can be regarded as an extension of a classical result due to Jambu and Terao (1984), which asserts that every supersolvable hyperplane arrangement is inductively free. Our third main result is an application to toric arrangements, which states that the toric arrangement defined by an arbitrary ideal of a root system of type $A$, $B$ or $C$ with respect to the root lattice is inductive.

Abstract: The factorization number $F_2(G)$ of a finite group $G$ is the number of all possible factorizations of $G=HK$ as product of its subgroups $H$ and $K$, while the subgroup commutativity degree $\mathrm{sd}(G)$ of $G$ is the probability of finding two commuting subgroups in $G$ at random. It is known that $\mathrm{sd}(G)$ can be expressed in terms of $F_2(G)$. Denoting by $\mathrm{L}(G)$ the subgroups lattice of $G$, the non--permutability graph of subgroups $\Gamma_{\mathrm{L}(G)}$ of $G$ is the graph with vertices in $\mathrm{L}(G) \setminus \mathfrak{C}_{\mathrm{L}(G)}(\mathrm{L}(G))$, where $\mathfrak{C}_{\mathrm{L}(G)}(\mathrm{L}(G))$ is the smallest sublattice of $\mathrm{L}(G)$ containing all permutable subgroups of $G$, and edges obtained by joining two vertices $X,Y$ such that $XY\neq YX$. The spectral properties of $\Gamma_{\mathrm{L}(G)}$ have been recently investigated in connection with $F_2(G)$ and $\mathrm{sd}(G)$. Here we show a new combinatorial formula, which allows us to express $F_2(G)$, and so $\mathrm{sd}(G)$, in terms of adjacency and Laplacian matrices of $\Gamma_{\mathrm{L}(G)}$.

Abstract: Consider the point line-geometry ${\mathcal P}_t(n,k)$ having as points all the $[n,k]$-linear codes having minimum dual distance at least $t+1$ and where two points $X$ and $Y$ are collinear whenever $X\cap Y$ is a $[n,k-1]$-linear code having minimum dual distance at least $t+1$. We are interested in the collinearity graph $\Lambda_t(n,k)$ of ${\mathcal P}_t(n,k).$ The graph $\Lambda_t(n,k)$ is a subgraph of the Grassmann graph and also a subgraph of the graph $\Delta_t(n,k)$ of the linear codes having minimum dual distance at least $t+1$ introduced in~[M. Kwiatkowski, M. Pankov, On the distance between linear codes, Finite Fields Appl. 39 (2016), 251--263, doi:10.1016/j.ffa.2016.02.004, arXiv:1506.00215]. We shall study the structure of $\Lambda_t(n,k)$ in relation to that of $\Delta_t(n,k)$ and we will characterize the set of its isolated vertices. We will then focus on $\Lambda_1(n,k)$ and $\Lambda_2(n,k)$ providing necessary and sufficient conditions for them to be connected.

Abstract: We introduce and study a notion of dually Lorentzian polynomials, and show that if $s$ is non-zero and dually Lorentzian then the operator \[s(\partial_{x_1},\ldots,\partial_{x_n}):\mathbb R[x_1,\ldots,x_n] \to \mathbb R[x_1,\ldots,x_n]\] preserves (strictly) Lorentzian polynomials. From this we conclude that any theory that admits a mixed Alexandrov-Fenchel inequality also admits a generalized Alexandrov-Fenchel inequality involving dually Lorentzian polynomials. As such we deduce generalized Alexandrov-Fenchel inequalities for mixed discriminants, for integrals of K\"ahler classes, for mixed volumes, and in the theory of valuations.