bluuebunny/crossref_metadata_2025_split huggingface dataset:
Biclique Covers and Partitions
Authors: Pinto Trevor 
Published: January 2020

The biclique cover number (resp. biclique partition number) of a graph $G$, $\mathrm{bc}(G$) (resp. $\mathrm{bp}(G)$), is the least number of bicliques - complete bipartite subgraphs - that are needed to cover (resp. partition) the edges of $G$.The local biclique cover number (resp. local biclique partition number) of a graph $G$, $\mathrm{lbc}(G$) (resp. $\mathrm{lbp}(G)$), is the least $r$ such that there is a cover (resp. partition) of the edges of $G$ by bicliques with no vertex in more than $r$ of these bicliques.We show that $\mathrm{bp}(G)$ may be bounded in terms of $\mathrm{bc}(G)$, in particular, $\mathrm{bp}(G)\leq \frac{1}{2}(3^\mathrm{bc(G)}-1)$. However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that $\mathrm{lbp}(G)$ can be arbitrarily large, even for graphs with $\mathrm{lbc}(G)=2$. For such graphs, $G$, we try to bound $\mathrm{lbp}(G)$ in terms of additional information about biclique covers of $G$. We both answer and leave open questions related to this.There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least $r(n)$ for which every graph on $n$ vertices can be represented as a subcube intersection graph in which every subcube has dimension $r$. We reduce this problem to the much studied question of finding the least $d(n)$ such that every graph on $n$ vertices is the intersection graph of subcubes of a $d$-dimensional cube.
Hyperoctahedral Eulerian Idempotents, Hodge Decompositions, and Signed Graph Coloring Complexes
Authors: Braun Benjamin , Crown Rundell Sarah 
Published: January 2020

Phil Hanlon proved that the coefficients of the chromatic polynomial of a graph $G$ are equal (up to sign) to the dimensions of the summands in a Hodge-type decomposition of the top homology of the coloring complex for $G$. We prove a type B analogue of this result for chromatic polynomials of signed graphs using hyperoctahedral Eulerian idempotents.
Colour-blind Can Distinguish Colour Pallets
Authors: Przybyło Jakub 
Published: January 2020

Let $c:E\to\{1,\ldots,k\}$ be an edge colouring of a connected graph $G=(V,E)$. Each vertex $v$ is endowed with a naturally defined pallet under $c$, understood as the multiset of colours incident with $v$. If $\delta(G)\geq 2$, we obviously (for $k$ large enough) may colour the edges of $G$ so that adjacent vertices are distinguished by their pallets of colours. Suppose then that our coloured graph is examined by a person who is unable to name colours, but perceives if two object placed next to each other are coloured differently. Can we colour $G$ so that this individual can distinguish colour pallets of adjacent vertices? It is proved that if $\delta(G)$ is large enough, then it is possible using just colours 1, 2 and 3. This result is sharp and improves all earlier ones. It also constitutes a strengthening of a result by Addario-Berry, Aldred, Dalal and Reed (2005).
The Terwilliger Algebra of the Incidence Graphs of Johnson Geometry
Authors: Kong Qian , Lv Benjian , Wang Kaishun 
Published: January 2020

In 2007, Levstein and Maldonado computed the Terwilliger algebra of the Johnson graph $J(n,m)$ when $3m\leq n$. It is well known that the halved graphs of the incidence graph $J(n,m,m+1)$ of Johnson geometry are Johnson graphs. In this paper, we determine the Terwilliger algebra of $J(n,m,m+1)$ when $3m\leq n$, give two bases of this algebra, and calculate its dimension.
On Compact Symmetric Regularizations of Graphs
Authors: Vandell R. , Walsh M. , Weakley W. D. 
Published: January 2020

Let $G$ be a finite simple graph of order $n$, maximum degree $\Delta$, and minimum degree $\delta$. A compact regularization of $G$ is a $\Delta$-regular graph $H$ of which $G$ is an induced subgraph: $H$ is symmetric if every automorphism of $G$ can be extended to an automorphism of $H$. The index $|H:G|$ of a regularization $H$ of $G$ is the ratio $|V(H)|/|V(G)|$. Let $\mbox{mcr}(G)$ denote the index of a minimum compact regularization of $G$ and let $\mbox{mcsr}(G)$ denote the index of a minimum compact symmetric regularization of $G$.Erdős and Kelly proved that every graph $G$ has a compact regularization and $\mbox{mcr}(G) \leq 2$. Building on a result of König, Chartrand and Lesniak showed that every graph has a compact symmetric regularization and $\mbox{mcsr}(G) \leq 2^{\Delta - \delta}$. Using a partial Cartesian product construction, we improve this to $\mbox{mcsr}(G) \leq \Delta - \delta + 2$ and give examples to show this bound cannot be reduced below $\Delta - \delta + 1$.
Maximum Induced Forests in Graphs of Bounded Treewidth
Authors: Chappell Glenn G. , Pelsmajer Michael J. 
Published: January 2020

Given a nonnegative integer $d$ and a graph $G$, let $f_d(G)$ be the maximum order of an induced forest in $G$ having maximum degree at most $d$. We seek lower bounds for $f_d(G)$ based on the order and treewidth of $G$.We show that, for all $k,d\ge 2$ and $n\ge 1$, if $G$ is a graph with order $n$ and treewidth at most $k$, then $f_d(G)\ge\lceil{(2dn+2)/(kd+d+1)}\rceil$, unless $G\in\{K_{1,1,3},K_{2,3}\}$ and $k=d=2$. We give examples that show that this bound is tight to within $1$.We conjecture a bound for $d=1$: $f_1(G) \ge\lceil{2n/(k+2)}\rceil$, which would also be tight to within $1$, and we prove it for $k\le 3$. For $k\ge 4$ the conjecture remains open, and we prove a weaker bound: $f_1(G)\ge (2n+2)/(2k+3)$. We also examine the cases $d=0$ and $k=0,1$.Lastly, we consider open problems relating to $f_d$ for graphs on a given surface, rather than graphs of bounded treewidth.
The Distinguishing Index of Infinite Graphs
Authors: Broere Izak , Pilśniak Monika 
Published: January 2020

The distinguishing index $D^\prime(G)$ of a graph $G$ is the least cardinal $d$ such that $G$ has an edge colouring with $d$ colours that is only preserved by the trivial automorphism. This is similar to the notion of the distinguishing number $D(G)$ of a graph $G$, which is defined with respect to vertex colourings.We derive several bounds for infinite graphs, in particular, we prove the general bound $D^\prime(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the infinite random graph and for uncountable tree-like graphs.We also investigate the concept of the motion of edges and its relationship with the Infinite Motion Lemma.
The Combinatorics of $\mathsf{A_2}$-Webs
Authors: Benkart Georgia , Cho Soojin , Moon Dongho 
Published: January 2020

The nonelliptic $\mathsf{A_2}$-webs with $k$ "$+$''s on the top boundary and $3n-2k$ "$-$''s on the bottom boundary combinatorially model the space $\mathsf{Hom}_{\mathfrak{sl}_3}(\mathsf{V}^{\otimes (3n-2k)}, \mathsf{V}^{\otimes k})$ of $\mathfrak{sl}_3$-module maps on tensor powers of the natural 3-dimensional $\mathfrak{sl}_3$-module $\mathsf{V}$, and they have connections with the combinatorics ofSpringer varieties. Petersen, Pylyavskyy, and Rhodes showed that the set of such $\mathsf{A_2}$-webs and the set of semistandard tableaux of shape $(3^n)$ and type $\{1^2,\dots,k^2,k+1,\dots, 3n-k\}$ have the same cardinalities. In this work, we use the $\sf{m}$-diagrams introduced by Tymoczko and the Robinson-Schensted correspondence to construct an explicit bijection, different from the one given by Russell, between these two sets. In establishing our result, we show that the pair of standard tableaux constructed using the notion of path depth is the same as the pair constructed from applying the Robinson-Schensted correspondence to a $3\,2\,1$-avoiding permutation. We also obtain a bijection between such pairs of standard tableaux and Westbury's $\mathsf{A_2}$ flow diagrams.
Small Snarks with Large Oddness
Authors: Lukoťka Robert , Máčajová Edita , Mazák Ján , Škoviera Martin 
Published: January 2020

We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph $G$ with oddness $\omega(G)$ other than the Petersen graph has at least $5.41\, \omega(G)$ vertices, and for each integer $k$ with $2\le k\le 6$ we construct an infinite family of cubic graphs with cyclic connectivity $k$ and small oddness ratio $|V(G)|/\omega(G)$. In particular, for cyclic connectivity $2$, $4$, $5$, and $6$ we improve the upper bounds on the oddness ratio of snarks to $7.5$, $13$, $25$, and $99$ from the known values $9$, $15$, $76$, and $118$, respectively. In addition, we construct a cyclically $4$-connected snark of girth $5$ with oddness $4$ on $44$ vertices, improving the best previous value of $46$. Corrigendum added March 19, 2018.
On Fence Patrolling by Mobile Agents
Authors: Dumitrescu Adrian , Ghosh Anirban , Tóth Csaba D. 
Published: January 2020

Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the idle time, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al. (2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively.In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their algorithm ${\mathcal A}_2$ for unidirectional patrolling of a closed fence; (ii) we present a schedule with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.
A Laurent Series Proof of the Habsieger-Kadell $q$-Morris Identity
Authors: Guoce Xin , Yue Zhou 
Published: January 2020

We give a Laurent series proof of the Habsieger-Kadell $q$-Morris identity, which is a common generalization of the $q$-Morris identity and the Aomoto constant term identity. The proof allows us to extend the theorem for some additional parameter cases.
On the Typical Structure of Graphs in a Monotone Property
Authors: Janson Svante , Uzzell Andrew J. 
Published: January 2020

Given a graph property $\mathcal{P}$, it is interesting to determine the typical structure of graphs that satisfy $\mathcal{P}$. In this paper, we consider monotone properties, that is, properties that are closed under taking subgraphs. Using results from the theory of graph limits, we show that if $\mathcal{P}$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\mathcal{P}$, then almost every graph with $\mathcal{P}$ is close to being a balanced $r$-partite graph.
On $m$-Closed Graphs
Authors: Sharifan Leila , Javanbakht Masoumeh 
Published: January 2020

A graph is closed when its vertices have a labeling by $[n]$ such that the binomial edge ideal $J_G$ has a quadratic Gröbner basis with respect to the lexicographic order induced by $x_1 > \ldots > x_n > y_1> \ldots > y_n$. In this paper, we generalize this notion and study the so called $m$-closed graphs. We find equivalent condition to $3$-closed property of an arbitrary tree $T$. Using it, we classify a class of $3$-closed trees. The primary decomposition of this class of graphs is also studied.
On a Refinement of Wilf-equivalence for Permutations
Authors: Yan Sherry  H.F. , Ge Huiyun , Zhang Yaqiu 
Published: January 2020

Recently, Dokos et al. conjectured that for all $k, m\geq 1$, the patterns $ 12\ldots k(k+m+1)\ldots (k+2)(k+1) $ and $(m+1)(m+2)\ldots (k+m+1)m\ldots 21$ are $maj$-Wilf-equivalent. In this paper, we confirm this conjecture for all $k\geq 1$ and $m=1$. In fact, we construct a descent set preserving bijection between $ 12\ldots k (k-1) $-avoiding permutations and $23\ldots k1$-avoiding permutations for all $k\geq 3$. As a corollary, our bijection enables us to settle a conjecture of Gowravaram and Jagadeesan concerning the Wilf-equivalence for permutations with given descent sets.
A Note on Goldbach Partitions of Large Even Integers
Authors: Mutafchiev Ljuben 
Published: January 2020

Let $\Sigma_{2n}$ be the set of all partitions of the even integers from the interval $(4,2n], n>2,$ into two odd prime parts. We show that $|\Sigma_{2n}| \sim 2n^2/\log^2{n}$ as $n\to\infty$. We also assume that a partition is selected uniformly at random from the set $\Sigma_{2n}$. Let $2X_n\in (4,2n]$ be the size of this partition. We prove a limit theorem which establishes that $X_n/n$ converges weakly to the maximum of two random variables which are independent copies of a uniformly distributed random variable in the interval $(0,1)$. Our method of proof is based on a classical Tauberian theorem due to Hardy, Littlewood and Karamata. We also show that the same asymptotic approach can be applied to partitions of integers into an arbitrary and fixed number of odd prime parts.
Density of Gallai Multigraphs
Authors: Magnant Colton 
Published: January 2020

Diwan and Mubayi asked how many edges of each color could be included in a $3$-edge-colored multigraph containing no rainbow triangle. We answer this question under the modest assumption that the multigraphs in question contain at least one edge between every pair of vertices. We also conjecture that this assumption is, in fact, without loss of generality.
Counting Permutations by Alternating Descents
Authors: Gessel Ira M. , Zhuang Yan 
Published: January 2020

We find the exponential generating function for permutations with all valleys even and all peaks odd, and use it to determine the asymptotics for its coefficients, answering a question posed by Liviu Nicolaescu. The generating function can be expressed as the reciprocal of a sum involving Euler numbers: \[\left(1-E_1x+E_{3}\frac{x^{3}}{3!}-E_{4}\frac{x^{4}}{4!}+E_{6}\frac{x^{6}}{6!}-E_{7}\frac{x^{7}}{7!}+\cdots\right)^{-1},\tag{$*$}\]where $\sum_{n=0}^\infty E_n x^n\!/n! = \sec x + \tan x$. We give two proofs of this formula. The first uses a system of differential equations whose solution gives the generating function\begin{equation*}\frac{3\sin\left(\frac{1}{2}x\right)+3\cosh\left(\frac{1}{2}\sqrt{3}x\right)}{3\cos\left(\frac{1}{2}x\right)-\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}x\right)},\end{equation*} which we then show is equal to $(*)$. The second proof derives $(*)$ directly from general permutation enumeration techniques, using noncommutative symmetric functions. The generating function $(*)$ is an "alternating" analogue of David and Barton's generating function \[\left(1-x+\frac{x^{3}}{3!}-\frac{x^{4}}{4!}+\frac{x^{6}}{6!}-\frac{x^{7}}{7!}+\cdots\right)^{-1},\]for permutations with no increasing runs of length 3 or more. Our general results give further alternating analogues of permutation enumeration formulas, including results of Chebikin and Remmel.
Induced and Non-induced Forbidden Subposet Problems
Authors: Patkós Balázs 
Published: January 2020

The problem of determining the maximum size $La(n,P)$ that a $P$-free subposet of the Boolean lattice $B_n$ can have, attracted the attention of many researchers, but little is known about the induced version of these problems. In this paper we determine the asymptotic behavior of $La^*(n,P)$, the maximum size that an induced $P$-free subposet of the Boolean lattice $B_n$ can have for the case when $P$ is the complete two-level poset $K_{r,t}$ or the complete multi-level poset $K_{r,s_1,\dots,s_j,t}$ when all $s_i$'s either equal 4 or are large enough and satisfy an extra condition. We also show lower and upper bounds for the non-induced problem in the case when $P$ is the complete three-level poset $K_{r,s,t}$. These bounds determine the asymptotics of $La(n,K_{r,s,t})$ for some values of $s$ independently of the values of $r$ and $t$.
Maximal Clades in Random Binary Search Trees
Authors: Janson Svante 
Published: January 2020

We study maximal clades in random phylogenetic trees with the Yule-Harding model or, equivalently, in binary search trees. We use probabilistic methods to reprove and extend earlier results on moment asymptotics and asymptotic normality. In particular, we give an explanation of the curious phenomenon observed by Drmota, Fuchs and Lee (2014) that asymptotic normality holds, but one should normalize using half the variance.
Flag-Transitive Non-Symmetric 2-Designs with $(r,\lambda)=1$ and Alternating Socle
Authors: Zhou Shenglin , Wang Yajie 
Published: January 2020

This paper deals with flag-transitive non-symmetric 2-designs with $(r,\lambda)=1$. We prove that if $\mathcal D$ is a non-trivial non-symmetric $2$-$(v,k,\lambda)$ design with $(r,\lambda)=1$ and $G\leq Aut(\mathcal D)$ is flag-transitive with $Soc(G)=A_n$ for $n\geq 5$, then $\mathcal D$ is a $2$-$(6,3,2)$ design, the projective space $PG(3,2)$, or a $2$-$(10,6,5)$ design.
Solution to a Conjecture on the Maximum Skew-Spectral Radius of Odd-Cycle Graphs
Authors: Chen Xiaolin , Li Xueliang , Lian Huishu 
Published: January 2020

Let $G$ be a simple graph with no even cycle, called an odd-cycle graph. Cavers et al. [Linear Algebra Appl. 436(12):4512-1829, 2012] showed that the spectral radius of $G^\sigma$ is the same for every orientation $\sigma$ of $G$, and equals the maximum matching root of $G$. They proposed a conjecture that the graphs which attain the maximum skew spectral radius among the odd-cycle graphs $G$ of order $n$ are isomorphic to the odd-cycle graph with one vertex degree $n-1$ and size $m=\lfloor 3(n-1)/2\rfloor$. By using the Kelmans transformation, we give a proof to the conjecture. Moreover, sharp upper bounds of the maximum matching roots of the odd-cycle graphs with given order $n$ and size $m$ are given and extremal graphs are characterized.
Schubert Calculus and the Homology of the Peterson Variety
Authors: Insko Erik 
Published: January 2020

We use the tight correlation between the geometry of the Peterson variety and the combinatorics the symmetric group to prove that homology of the Peterson variety injects into the homology of the flag variety. Our proof counts the points of intersection between certain Schubert varieties in the full flag variety and the Peterson variety, and shows that these intersections are proper and transverse.
A Deza–Frankl Type Theorem for Set Partitions
Authors: Ku Cheng Yeaw , Wong Kok Bin 
Published: January 2020

A set partition of $[n]$ is a collection of pairwise disjoint nonempty subsets (called blocks) of $[n]$ whose union is $[n]$. Let $\mathcal{B}(n)$ denote the family of all set partitions of $[n]$. A family $\mathcal{A} \subseteq \mathcal{B}(n)$ is said to be $m$-intersecting if any two of its members have at least $m$ blocks in common. For any set partition $P \in \mathcal{B}(n)$, let $\tau(P) = \{x: \{x\} \in P\}$ denote the union of its singletons. Also, let $\mu(P) = [n] -\tau(P)$ denote the set of elements that do not appear as a singleton in $P$. Let \begin{align*} {\mathcal F}_{2t} & =\left\{P \in \mathcal{B}(n)\ : \ \vert \mu (P)\vert\leq t\right\};\\{\mathcal F}_{2t+1}(i_0) & =\left\{P \in \mathcal{B}(n)\ : \ \vert\mu (P)\cap ([n]\setminus \{i_0\})\vert\leq t\right\}.\end{align*} In this paper, we show that for $r\geq 3$, there exists a $n_0=n_0(r)$ depending on $r$ such that for all $n\geq n_0$, if $\mathcal{A} \subseteq\mathcal{B}(n)$ is $(n-r)$-intersecting, then \[ |\mathcal{A}| \leq \begin{cases} \vert {\mathcal F}_{2t} \vert, & \text{if $r=2t$};\\ \vert {\mathcal F}_{2t+1}(1) \vert, & \text{if $r=2t+1$}.\end{cases}\]Moreover, equality holds if and only if \[ \mathcal{A}= \begin{cases} {\mathcal F}_{2t}, & \text{if $r=2t$};\\ {\mathcal F}_{2t+1}(i_0), & \text{if $r=2t+1$},\end{cases}\]for some $i_0\in [n]$.
Output Sum of Transducers: Limiting Distribution and Periodic Fluctuation
Authors: Heuberger Clemens , Kropf Sara , Prodinger Helmut 
Published: January 2020

As a generalization of the sum of digits function and other digital sequences, sequences defined as the sum of the output of a transducer are asymptotically analyzed. The input of the transducer is a random integer in $[0, N)$. Analogues in higher dimensions are also considered. Sequences defined by a certain class of recursions can be written in this framework.Depending on properties of the transducer, the main term, the periodic fluctuation and an error term of the expected value and the variance of this sequence are established. The periodic fluctuation of the expected value is Hölder continuous and, in many cases, nowhere differentiable. A general formula for the Fourier coefficients of this periodic function is derived. Furthermore, it turns out that the sequence is asymptotically normally distributed for many transducers. As an example, the abelian complexity function of the paperfolding sequence is analyzed. This sequence has recently been studied by Madill and Rampersad.
Developing New Locality Results for the Prüfer Code using a Remarkable Linear-Time Decoding Algorithm
Authors: Paulden Tim , Smith David K. 
Published: January 2020

The Prüfer Code is a bijection between the $n^{n-2}$ trees on the vertex set $[1,n]$ and the $n^{n-2}$ strings in the set $[1,n]^{n-2}$ (known as Prüfer strings of order $n$). Efficient linear-time algorithms for decoding (i.e., converting string to tree) and encoding (i.e., converting tree to string) are well-known. In this paper, we examine an improved decoding algorithm (due to Cho et al.) that scans the elements of the Prüfer string in reverse order, rather than in the usual forward direction. We show that the algorithm runs in linear time without requiring additional data strutures or sorting routines, and is an 'online' algorithm — every time a new string element is read, the algorithm can correctly output an additional tree edge without any knowledge of the future composition of the string.	This new decoding algorithm allows us to derive results concerning the 'locality' properties of the Prüfer Code (i.e., the effect of making small changes to a Prüfer string on the structure of the corresponding tree). First, we show that mutating the $\mu$th element of a Prüfer string (of any order) causes at most $\mu + 1$ edge-changes in the corresponding tree. We also show that randomly mutating the first element of a random Prüfer string of order $n$ causes two edge-changes in the corresponding tree with probability $2(n-3)/n(n-1)$, and one edge-change otherwise. Then, based on computer-aided enumerations, we make three conjectures concerning the locality properties of the Prüfer Code, including a formula for the probability that a random mutation to the $\mu$th element of a random Prüfer string of order $n$ causes exactly one edge-change in the corresponding tree. We show that if this formula is correct, then the probability that a random mutation to a random Prüfer string of order $n$ causes exactly one edge-change in the corresponding tree is asymptotically equal to one-third, as $n$ tends to infinity.
La rencontre entre équipes et familles,…individualisme et déstabilisation des alliances
Authors: Mellier Denis 
Published: January 2020

La rencontre entre les équipes et les familles dépend de l’évolution de ces deux types d’institution, de leur imbrication et de la place ainsi faite aux alliances institutionnelles qui définissent leur espace mais qui actuellement se délitent. 1) Leur évolution depuis la Seconde Guerre mondiale converge : la désinstitutionalisation s’accompagne de la généralisation de l’individualisme familial. La famille qui a vu sa structure se déstabiliser, ses formes changer en donnant une plus grande place aux professionnels, se positionne pour intervenir plus directement dans la sphère de la professionnalité. 2) L’imbrication des rapports entre professionnels et familles, qui est présente dès l’origine de l’institution, se traduit par différents types d’alliances (plus structurantes, défensives ou toxiques) qui se déstabilisent actuellement. 3) L’organisation des alliances à partir d’un scénario fantasmatique ternaire laisse possible un travail psychique fondé sur la tiercéité. De nouvelles alliances sont ainsi à construire à différents niveaux pour ré-instituer par le groupe les liens entre équipes et familles.