Combinatorics (math.CO)

Abstract: In this paper, we are interested in some problems related to chromatic number and clique number for the class of $(P_5,K_5-e)$-free graphs, and prove the following. $(a)$ If $G$ is a connected ($P_5,K_5-e$)-free graph with $\omega(G)\geq 7$, then either $G$ is the complement of a bipartite graph or $G$ has a clique cut-set. Moreover, there is a connected ($P_5,K_5-e$)-free imperfect graph $H$ with $\omega(H)=6$ and has no clique cut-set. This strengthens a result of Malyshev and Lobanova [Disc. Appl. Math. 219 (2017) 158--166]. $(b)$ If $G$ is a ($P_5,K_5-e$)-free graph with $\omega(G)\geq 4$, then $\chi(G)\leq \max\{7, \omega(G)\}$. Moreover, the bound is tight when $\omega(G)\notin \{4,5,6\}$. This result together with known results partially answers a question of Ju and Huang [arXiv:2303.18003 [math.CO] 2023], and also improves a result of Xu [Manuscript 2022]. While the "Chromatic Number Problem" is known to be $NP$-hard for the class of $P_5$-free graphs, our results together with some known results imply that the "Chromatic Number Problem" can be solved in polynomial time for the class of ($P_5,K_5-e$)-free graphs which may be independent interest.

Abstract: $\newcommand{\Max}{\mathrm{Max4PC}}$ The Four point condition (4PC henceforth) is a well known condition characterising distances in trees $T$. Let $w,x,y,z$ be four vertices in $T$ and let $d_{x,y}$ denote the distance between vertices $x,y$ in $T$. The 4PC condition says that among the three terms $d_{w,x} + d_{y,z}$, $d_{w,y} + d_{x,z}$ and $d_{w,z} + d_{x,y}$ the maximum value equals the second maximum value. We define an $\binom{n}{2} \times \binom{n}{2}$ sized matrix $\Max_T$ from a tree $T$ where the rows and columns are indexed by size-2 subsets. The entry of $\Max_T$ corresponding to the row indexed by $\{w,x\}$ and column $\{y,z\}$ is the maximum value among the three terms $d_{w,x} + d_{y,z}$, $d_{w,y} + d_{x,z}$ and $d_{w,z} + d_{x,y}$. In this work, we determine basic properties of this matrix like rank, give an algorithm that outputs a family of bases, and find the determinant of $\Max_T$ when restricted to our basis. We further determine the inertia and the Smith Normal Form (SNF) of $\Max_T$.

Abstract: Let $box(G)$ be the boxicity of a graph $G$, $G[H_1,H_2,\ldots, H_n]$ be the $G$-generalized join graph of $n$-pairwise disjoint graphs $H_1,H_2,\ldots, H_n$, $G^d_k$ be a circular clique graph (where $k\geq 2d$) and $\Gamma(R)$ be the zero-divisor graph of a commutative ring $R$. In this paper, we prove that $\chi(G^d_k)\geq box(G^d_k)$, for all $k$ and $d$ with $k\geq 2d$. This generalizes the results proved in \cite{Aki}. Also we obtain that $box(G[H_1,H_2,\ldots,H_n])\leq \mathop\sum\limits_{i=1}^nbox(H_i)$. As a consequence of this result, we obtain a bound for boxicity of zero-divisor graph of a finite commutative ring with unity. In particular, if $R$ is a finite commutative non-zero reduced ring with unity, then $\chi(\Gamma(R))\leq box(\Gamma(R))\leq 2^{\chi(\Gamma(R))}-2$. where $\chi(\Gamma(R))$ is the chromatic number of $\Gamma(R)$. Moreover, we show that if $N= \prod\limits_{i=1}^{a}p_i^{2n_i} \prod\limits_{j=1}^{b}q_j^{2m_j+1}$ is a composite number, where $p_i$'s and $q_j$'s are distinct prime numbers, then $box(\Gamma(\mathbb{Z}_N))\leq \big(\mathop\prod\limits_{i=1}^{a}(2n_i+1)\mathop\prod\limits_{j=1}^{b}(2m_j+2)\big)-\big(\mathop\prod\limits_{i=1}^{a}(n_i+1)\mathop\prod\limits_{j=1}^{b}(m_j+1)\big)-1$, where $\mathbb{Z}_N$ is the ring of integers modulo $N$. Further, we prove that, $box(\Gamma(\mathbb{Z}_N))=1$ if and only if either $N=p^n$ for some prime number $p$ and some positive integer $n\geq 2$ or $N=2p$ for some odd prime number $p$.

Abstract: Consider a group $G$ acting on a set $\Omega$, the vector $v_{a,b}$ is a vector with the entries indexed by the elements of $G$, and the $g$-entry is 1 if $g$ maps $a$ to $b$, and zero otherwise. A $(G,\Omega)$-Cameron-Liebler set is a subset of $G$, whose indicator function is a linear combination of elements in $\{v_{a, b}\ :\ a, b \in \Omega\}$. We investigate Cameron-Liebler sets in permutation groups, with a focus on constructions of Cameron-Liebler sets for 2-transitive groups.

Abstract: Let $\text{Fl}_{n,q}$ be the simplicial complex whose vertices are the non-trivial subspaces of $\mathbb{F}_q^n$ and whose simplices correspond to families of subspaces forming a flag. Let $\Delta^{+}_k(\text{Fl}_{n,q})$ be the $k$-dimensional weighted upper Laplacian on $ \text{Fl}_{n,q}$. The spectrum of $\Delta^{+}_k(\text{Fl}_{n,q})$ was first studied by Garland, who obtained a lower bound on its non-zero eigenvalues. Here, we focus on the $k=0$ case. We determine the asymptotic behavior of the eigenvalues of $\Delta_{0}^{+}(\text{Fl}_{n,q})$ as $q$ tends to infinity. In particular, we show that for large enough $q$, $\Delta_{0}^{+}(\text{Fl}_{n,q})$ has exactly $\left\lfloor n^2/4\right\rfloor+2$ distinct eigenvalues, and that every eigenvalue $\lambda\neq 0,n-1$ of $\Delta_{0}^{+}(\text{Fl}_{n,q})$ tends to $n-2$ as $q$ goes to infinity. This solves the $0$-dimensional case of a conjecture of Papikian.

Abstract: Let $G$ and $H$ be hypergraphs on $n$ vertices, and suppose $H$ has large enough minimum degree to necessarily contain a copy of $G$ as a subgraph. We give a general method to randomly embed $G$ into $H$ with good "spread". More precisely, for a wide class of $G$, we find a randomised embedding $f\colon G\hookrightarrow H$ with the following property: for every $s$, for any partial embedding $f'$ of $s$ vertices of $G$ into $H$, the probability that $f$ extends $f'$ is at most $O(1/n)^s$. This is a common generalisation of several streams of research surrounding the classical Dirac-type problem. For example, setting $s=n$, we obtain an asymptotically tight lower bound on the number of embeddings of $G$ into $H$. This recovers and extends recent results of Glock, Gould, Joos, K\"uhn, and Osthus and of Montgomery and Pavez-Sign\'e regarding enumerating Hamilton cycles in Dirac hypergraphs. Moreover, using the recent developments surrounding the Kahn--Kalai conjecture, this result implies that many Dirac-type results hold robustly, meaning $G$ still embeds into $H$ after a random sparsification of its edge set. This allows us to recover a recent result of Kang, Kelly, K\"uhn, Osthus, and Pfenninger and of Pham, Sah, Sawhney, and Simkin for perfect matchings, and obtain novel results for Hamilton cycles and factors in Dirac hypergraphs. Notably, our randomised embedding algorithm is self-contained and does not require Szemer\'edi's regularity lemma or iterative absorption.