Combinatorics (math.CO)

Abstract: We are looking for integer sets that resemble classical Cantor set and investigate the structure of their sum sets. Especially we investigate $FS(B)$ the subset sum of sequence type $B=\{\lfloor p^n\alpha\rfloor\}^\infty_{n=0}$. When $p=2$, then we prove $FS(B)+FS(B)=\N$ by analogy with the Cantor set, and some structure theorem for $p>2$

Abstract: We prove new lower bounds on the modularity of graphs. Specifically, the modularity of a graph $G$ with average degree $\bar d$ is $\Omega(\bar{d}^{-1/2})$, under some mild assumptions on the degree sequence of $G$. The lower bound $\Omega(\bar{d}^{-1/2})$ applies, for instance, to graphs with a power-law degree sequence or a near-regular degree sequence. It has been suggested that the relatively high modularity of the Erd\H{o}s-R\'enyi random graph $G_{n,p}$ stems from the random fluctuations in its edge distribution, however our results imply high modularity for any graph with a degree sequence matching that typically found in $G_{n,p}$. The proof of the new lower bound relies on certain weight-balanced bisections with few cross-edges, which build on ideas of Alon [Combinatorics, Probability and Computing (1997)] and may be of independent interest.

Abstract: The set $S_{\{i,j\}_{n}^{m}}=\{0,1,2,\ldots,m-1,m,m,m+1,\ldots,n-1,n\}\setminus\{i,j\},\quad 0<i<j\leqslant n$, is called Laplacian realizable if there exists a simple connected graph $G$ whose Laplacian spectrum is $S_{\{i,j\}_{n}^{m}}$. In this case, the graph $G$ is said to realize $S_{\{i,j\}_{n}^{m}}$. In this paper, we completely describe graphs realizing the sets $S_{\{i,j\}_{n}^{m}}$ with $m=1,2$ and determine the structure of these graphs.

Abstract: We investigate circular planar nearrings constructed from finite fields as well the complex number field using a multiplicative subgroup of order $k$, and characterize the overlaps of the basic graphs which arise in the associated $2$-designs.

Abstract: We derive attainable upper bounds on the algebraic connectivity (spectral gap) of a regular graph in terms of its diameter and girth. This bound agrees with the well-known Alon-Boppana-Friedman bound for graphs of even diameter, but is an improvement for graphs of odd diameter. For the girth bound, we show that only Moore graphs can attain it, and these only exist for very few possible girths. For diameter bound, we use a combination of stochastic algorithms and exhaustive search to find graphs which attain it. For 3-regular graphs, we find attainable graphs for all diameters $D$ up to and including $D=9$ (the case of $D=10$ is open). These graphs are extremely rare and also have high girth; for example we found exactly 45 distinct cubic graphs on 44 vertices attaining the upper bound when $D=7$; all have girth 8 (out of a total of about $10^{20}$ cubic graphs on 44 vertices, including 266362 having girth 8). We also exhibit families of $d$-regular graphs attaining upper bounds with $D=3$ and $4$, and with $g=6.$ Several conjectures are proposed.

Abstract: We study the problem of finding a minimum $k$-critical-bipartite graph of order $(n,m)$: a bipartite graph $G=(U,V;E)$, with $|U|=n$, $|V|=m$, and $n>m>1$, which is $k$-critical-bipartite, and the tuple $(|E|, \Delta_U, \Delta_V)$, where $\Delta_U$ and $\Delta_V$ denote the maximum degree in $U$ and $V$, respectively, is lexicographically minimum over all such graphs. $G$ is $k$-critical-bipartite if deleting at most $k=n-m$ vertices from $U$ yields $G'$ that has a complete matching, i.e., a matching of size $m$. Cichacz and Suchan solved the problem for biregular bipartite graphs. Here, we extend their results to bipartite graphs that are not biregular. We also prove tight lower bounds on the connectivity of $k$-critical-bipartite graphs.

Abstract: The inner plethysm of symmetric functions corresponds to the $\lambda$-ring operations of the representation ring $R({\mathfrak S}_n)$ of the symmetric group. It is known since the work of Littlewood that this operation possesses stability properties w.r.t. $n$. These properties have been explained in terms of vertex operators [Scharf and Thibon, Adv. Math. 104 (1994), 30-58]. Another approach [Orellana and Zabrocki, Adv. Math. 390 (2021), \# 107943], based on an expression of character values as symmetric functions of the eigenvalues of permutation matrices, has been proposed recently. This note develops the theory from scratch, discusses the link between both approaches and provides new proofs of some recent results.

Abstract: This paper studies planar algebras of Jones' style associated with the Young graph. We first see that, every time we fix a harmonic function on the Young graph, we may obtain a planar algebra whose structure is defined in terms of a state sum over the ways of filling planar tangles with Young diagrams. We delve into the case that the harmonic function is related to the Plancherel measures on Young diagrams. Along with an element that is depicted as a cross of two strings, we see that the defining relations among morphisms for the Khovanov Heisenberg category are recovered in the planar algebra. We also identify certain elements in the planar algebra with particular functions of Young diagrams that include the moments, Boolean cumulants and normalized characters. This paper thereby bridges diagramatical categorification and asymptotic representation theory. In fact, the Khovanov Heisenberg category is one of the most fundamental examples of diagramatical categorification whereas the harmonic functions on the Young graph have been a central object in the asymptotic representation theory of symmetric groups.

Abstract: We say that a pair of nonnegative integer sequences $(\{a_k\}_{k\geq 0},\{b_k\}_{k\geq 0})$ is Whitney-realizable if there exists a poset $P$ for which (the absolute values) of the Whitney numbers of the first and second kind are given by the numbers $a_k$ and $b_k$ respectively. The pair is said to be Whitney-dualizable if, in addition, there exists another poset $Q$ for which their Whitney numbers of the first and second kind are instead given by $b_k$ and $a_k$ respectively. In this case, we say that $P$ and $Q$ are Whitney duals. We use results on Whitney duality, recently developed by the first two authors, to exhibit a family of sequences which allows for multiple realizations and Whitney-dual realizations. More precisely, we study edge labelings for the families of posets of pointed partitions $\Pi_n^{\bullet}$ and weighted partitions $\Pi_n^{w}$ which are associated to the operads $\mathcal{P}erm$ and $\mathcal{C}om^2$ respectively. The first author and Wachs proved that these two families of posets share the same pair of Whitney numbers. We find EW-labelings for $\Pi_n^{\bullet}$ and $\Pi_n^{w}$ and use them to show that they also share multiple nonisomorphic Whitney dual posets. In addition to EW-labelings, we also find two new EL-labelings for $\Pi_n^\bullet$ answering a question of Chapoton and Vallette. Using these EL-labelings of $\Pi_n^\bullet$, and an EL-labeling of $\Pi_n^w$ introduced by the first author and Wachs, we give combinatorial descriptions of bases for the operads $\mathcal{P}re\mathcal{L}ie, \mathcal{P}erm,$ and $\mathcal{C}om^2$. We also show that the bases for $\mathcal{P}erm$ and $\mathcal{C}om^2$ are PBW bases.