bluuebunny/crossref_metadata_2025_split huggingface dataset:
Can Colour-Blind Distinguish Colour Palettes?
Authors: Kalinowski Rafał , Pilśniak Monika , Przybyło Jakub , Woźniak Mariusz 
Published: January 2020

Let $c:E(G)\rightarrow [k]$ be a colouring, not necessarily proper, of edges of a graph $G$. For a vertex $v\in V$, let $\overline{c}(v)=(a_1,\ldots,a_k)$, where $ a_i =|\{u:uv\in E(G),\;c(uv)=i\}|$, for $i\in [k].$ If we re-order the sequence $\overline{c}(v)$ non-decreasingly, we obtain a sequence $c^*(v)=(d_1,\ldots,d_k)$, called a palette of a vertex $v$. This can be viewed as the most comprehensive information about colours incident with $v$ which can be delivered by a person who is unable to name colours but distinguishes one from another. The smallest $k$ such that $c^*$ is a proper colouring of vertices of $G$ is called the colour-blind index of a graph $G$, and is denoted by dal$(G)$. We conjecture that there is a constant $K$ such that dal$(G)\leq K$ for every graph $G$ for which the parameter is well defined. As our main result we prove that $K\leq 6$ for regular graphs of sufficiently large degree, and for irregular graphs with $\delta (G)$ and $\Delta(G)$ satisfying certain conditions. The proofs are based on the Lopsided Lovász Local Lemma. We also show that $K=3$ for all regular bipartite graphs, and for complete graphs of order $n\geq 8$.
Drawing Hamiltonian Cycles with no Large Angles
Authors: Dumitrescu Adrian , Pach János , Tóth Géza 
Published: January 2020

Let $n \geq 4$ be even. It is shown that every set $S$ of $n$ points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of $n$ straight-line edges such that the angle between any two consecutive edges is at most $2\pi/3$. For $n=4$ and $6$, this statement is tight. It is also shown that every even-element point set $S$ can be partitioned into at most two subsets, $S_1$ and $S_2$, each admitting a spanning tour with no angle larger than $\pi/2$. Fekete and Woeginger conjectured that for sufficiently large even $n$, every $n$-element set admits such a spanning tour. We confirm this conjecture for point sets in convex position. A much stronger result holds for large point sets randomly and uniformly selected from an open region bounded by finitely many rectifiable curves: for any $\epsilon>0$, these sets almost surely admit a spanning tour with no angle larger than $\epsilon$.
Cospectral Graphs and Regular Orthogonal Matrices of Level 2
Authors: Abiad Aida , Haemers Willem H 
Published: January 2020

For a graph $\Gamma$ with adjacency matrix $A$, we consider a switching operation that takes $\Gamma$ into a graph $\Gamma'$ with adjacency matrix $A'$, defined by $A'=Q^\top A Q$, where $Q$ is a regular orthogonal matrix of level $2$ (that is, $Q^\top Q=I$, $Q$1 $=$ 1, $2Q$ is integral, and $Q$ is not a permutation matrix). If such an operation exists, and $\Gamma$ is nonisomorphic with $\Gamma'$, then we say that $\Gamma'$ is semi-isomorphic with $\Gamma$. Semi-isomorphic graphs are $\mathbb {R}$-cospectral, which means that they are cospectral and so are their complements. Wang and Xu [On the asymptotic behavior of graphs determined by their generalized spectra, Discrete Math. 310 (2010)] expect that almost all pairs of nonisomorphic $\mathbb {R}$-cospectral graphs are semi-isomorphic.Regular orthogonal matrices of level $2$ have been classified. By use of this classification we work out the requirements for this switching operation to work in case $Q$ has one nontrivial indecomposable block of size $4$, $6$, $7$ or $8$. Size $4$ corresponds to Godsil-McKay switching. The other cases provide new methods for constructions of $\mathbb {R}$-cospectral graphs. For graphs with eight vertices all these constructions are carried out. As a result we find that, out of the 1166 graphs on eight vertices which are $\mathbb {R}$-cospectral to another graph, only 44 are not semi-isomorphic to another graph.
Probabilities of Boolean Functions given by Random Implicational Formulas
Authors: Genitrini Antoine , Gittenberger Bernhard , Kraus Veronika , Mailler Cécile 
Published: January 2020

We study the asymptotic relation between the probability and the complexity of Boolean functions in the implicational fragment which are generated by large random Boolean expressions involving variables and implication, as the number of variables tends to infinity. In contrast to models studied in the literature so far, we consider two expressions to be equal if they differ only in the order of the premises. A precise asymptotic formula is derived for functions of low complexity. Furthermore, we show that this model does not exhibit the Shannon effect.An erratum was added to this paper on Feb 20, 2014.
Some Quotients of Chain Products are Symmetric Chain Orders
Authors: Duffus Dwight , McKibben-Sanders Jeremy , Thayer Kyle 
Published: January 2020

Canfield and Mason have conjectured that for all subgroups $G$ of the automorphism group of the Boolean lattice $B_n$ (which can be regarded as the symmetric group $S_n$), the quotient order $B_n/G$ is a symmetric chain order. We provide a straightforward proof of a generalization of a result of K. K. Jordan: namely, $B_n/G$ is an SCO whenever $G$ is generated by powers of disjoint cycles. In addition, the Boolean lattice $B_n$ can be replaced by any product of finite chains. The symmetric chain decompositions of Greene and Kleitman provide the basis for partitions of these quotients.
An Iterative Approach to the Traceability Conjecture for Oriented Graphs
Authors: Van Aardt Susan , Burger Alewyn , Dunbar Jean , Frick Marietjie , Harris John , Singleton Joy 
Published: January 2020

A digraph is $k$-traceable if its order is at least $k$ and each of its subdigraphs of order $k$ is traceable. The Traceability Conjecture (TC) states that for $k\geq 2$ every $k$-traceable oriented graph of order at least $2k-1$ is traceable. It has been shown that for $2\leq k\leq 6$, every $k$-traceable oriented graph is traceable. We develop an iterative procedure to extend previous results regarding the TC. In particular, we prove that every $7$-traceable oriented graph of order at least 9 is traceable and every 8-traceable graph of order at least 14 is traceable.
A Set and Collection Lemma
Authors: Levit Vadim E. , Mandrescu Eugen 
Published: January 2020

A set $S\subseteq V(G)$ is independent if no two vertices from $S$ are adjacent. Let $\alpha\left( G\right) $ stand for the cardinality of a largest independent set.In this paper we prove that if $\Lambda$ is a nonempty collection of maximum independent sets of a graph $G$, and $S$ is an independent set, thenthere is a matching from $S-\bigcap\Lambda$ into $\bigcup\Lambda-S$, and$\left\vert S\right\vert +\alpha(G)\leq\left\vert \bigcap\Lambda\cap S\right\vert +\left\vert \bigcup\Lambda\cup S\right\vert $.Based on these findings we provide alternative proofs for a number of well-known lemmata, such as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to András Hajnal.
Optimal Divisibility Conditions for Loose Hamilton Cycles in Random Hypergraphs
Authors: Dudek Andrzej , Frieze Alan , Loh Po-Shen , Speiss Shelley 
Published: January 2020

In the random $k$-uniform hypergraph $H^{(k)}_{n,p}$ of order $n$, each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a cycle of order $n$ in which every pair of consecutive edges intersects in a single vertex. It was shown by Frieze that if $p\geq c(\log n)/n^2$ for some absolute constant $c>0$, then a.a.s. $H^{(3)}_{n,p}$ contains a loose Hamilton cycle, provided that $n$ is divisible by $4$. Subsequently, Dudek and Frieze extended this result for any uniformity $k\ge 4$, proving that if $p\gg (\log n)/n^{k-1}$, then $H^{(k)}_{n,p}$ contains a loose Hamilton cycle, provided that $n$ is divisible by $2(k-1)$. In this paper, we improve the divisibility requirement and show that in the above results it is enough to assume that $n$ is a multiple of $k-1$, which is best possible.
On a Recurrence Arising in Graph Compression
Authors: Choi Yongwook , Knessl Charles , Szpankowski Wojciech 
Published: January 2020

In a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains $n$ balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability $p$) or the right subtree (with probability $1-p$). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer $d$ is given, and at level $d$ or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after $n+d$ steps). Observe that when $d=\infty$ the above tree can be modeled as a trie that stores $n$ independent sequences generated by a binary memoryless source with parameter $p$. Therefore, we coin the name $(n,d)$-tries for the tree just described, and to which we often refer simply as $d$-tries. We study here in detail the path length, and show how much the path length of such a $d$-trie differs from that of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.
Balanced Vertex Decomposable Simplicial Complexes and their h-vectors
Authors: Biermann Jennifer , Van Tuyl Adam 
Published: January 2020

Given any finite simplicial complex $\Delta$, we show how to construct from a colouring $\chi$ of $\Delta$ a new simplicial complex $\Delta_{\chi}$ that is balanced and vertex decomposable. In addition, the $h$-vector of $\Delta_{\chi}$ is precisely the $f$-vector of $\Delta$. Our construction generalizes the "whiskering'' construction of Villarreal, and Cook and Nagel. We also reverse this construction to prove a special case of a conjecture of Cook and Nagel, and Constantinescu and Varbaro on the $h$-vectors of flag complexes.
General Lower Bounds on Maximal Determinants of Binary Matrices
Authors: Brent Richard P. , Osborn Judy-anne H. 
Published: January 2020

We give general lower bounds on the maximal determinant of $n \times n$ $\{+1,-1\}$-matrices, both with and without the assumption of the Hadamard conjecture. Our bounds improve on earlier results of de Launey and Levin (2010) and, for certain congruence classes of $n \bmod 4$, the results of Koukouvinos, Mitrouli and Seberry (2000). In an Appendix we give a new proof, using Jacobi's determinant identity, of a result of Szöllősi (2010) on minors of Hadamard matrices.
Invariant Principal Order Ideals under Foata’s Transformation
Authors: Li Teresa X.S. , Miao Melissa Y.F. 
Published: January 2020

Let $\Phi$ denote Foata's second fundamental transformation on permutations. For a permutation $\sigma$ in the symmetric group $S_n$, let $\widetilde{\Lambda}_{\sigma}=\{\pi\in S_n\colon\pi\leq_{w} \sigma\}$ be the principal order ideal generated by $\sigma$ in the weak order $\leq_{w}$. Björner and Wachs have shown that $\widetilde{\Lambda}_{\sigma}$ is invariant under $\Phi$ if and only if $\sigma$ is a 132-avoiding permutation. In this paper, we consider the invariance property of $\Phi$ on the principal order ideals ${\Lambda}_{\sigma}=\{\pi\in S_n\colon \pi\leq \sigma\}$ with respect to the Bruhat order $\leq$. We obtain a characterization of permutations $\sigma$ such that ${\Lambda}_{\sigma}$ are invariant under $\Phi$. We also consider the invariant principal order ideals with respect to the Bruhat order under Han's bijection $H$. We find that ${\Lambda}_{\sigma}$ is invariant under the bijection $H$ if and only if it is invariant under the transformation $\Phi$.
A Characterization of Graphs by Codes from their Incidence Matrices
Authors: Dankelmann Peter , Key Jennifer D. , Rodrigues Bernardo G. 
Published: January 2020

We continue our earlier investigation of properties of linear codes generated by the rows of incidence matrices of $k$-regular connected graphs on $n$ vertices. The notion of edge connectivity is used to show that, for a wide range of such graphs, the $p$-ary code, for all primes $p$, from an $n \times \frac{1}{2}nk$ incidence matrix has dimension $n$ or $n-1$, minimum weight $k$, the minimum words are the scalar multiples of the rows, there is a gap in the weight enumerator between $k$ and $2k-2$, and the words of weight $2k-2$ are the scalar multiples of the differences of intersecting rows of the matrix. For such graphs, the graph can thus be retrieved from the code.
On Blow-Ups and Injectivity of Quivers
Authors: Grilliette Will , Seacrest Deborah E. , Seacrest Tyler 
Published: January 2020

This work connects the idea of a "blow-up" of a quiver with that of injectivity, showing that for a class of monic maps $\Phi$, a quiver is $\Phi$-injective if and only if all blow-ups of it are as well. This relationship is then used to characterize all quivers that are injective with respect to the natural embedding of $P_{n}$ into $C_{n}$.
Random Graphs from a Weighted Minor-Closed Class
Authors: McDiarmid Colin 
Published: January 2020

There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable minor-closed class, such as the class of all planar graphs. Here we use combinatorial and probabilistic methods to investigate a more general model. We consider random graphs from a 'well-behaved' class of graphs: examples of such classes include all minor-closed classes of graphs with 2-connected excluded minors (such as forests, series-parallel graphs and planar graphs), the class of graphs embeddable on any given surface, and the class of graphs with at most $k$ vertex-disjoint cycles. Also, we give weights to edges and components to specify probabilities, so that our random graphs correspond to the random cluster model, appropriately conditioned.We find that earlier results extend naturally in both directions, to general well-behaved classes of graphs, and to the weighted framework, for example results concerning the probability of a random graph being connected; and we also give results on the 2-core which are new even for the uniform (unweighted) case.
On some Generalized $q$-Eulerian Polynomials
Authors: Lin Zhicong 
Published: January 2020

The $(q,r)$-Eulerian polynomials are the (maj-exc,fix,exc) enumerative polynomials of permutations. Using Shareshian and Wachs' exponential generating function of these Eulerian polynomials, Chung and Graham proved two symmetrical $q$-Eulerian identities and asked for bijective proofs. We provide such proofs using Foata and Han's three-variable statistic (inv-lec,pix,lec). We also prove a new recurrence formula for the $(q,r)$-Eulerian polynomials and study a $q$-analogue of Chung and Graham's restricted descent polynomials. In particular, we obtain a generalized symmetrical identity for these restricted $q$-Eulerian polynomials with a combinatorial proof.
Fixed Point Polynomials of Permutation Groups
Authors: Harden C. M. , Penman D. B. 
Published: January 2020

In this paper we study, given a group $G$ of permutations of a finite set, the so-called fixed point polynomial $\sum_{i=0}^{n}f_{i}x^{i}$, where $f_{i}$ is the number of permutations in $G$ which have exactly $i$ fixed points. In particular, we investigate how root location relates to properties of the permutation group. We show that for a large family of such groups most roots are close to the unit circle and roughly uniformly distributed round it. We prove that many families of such polynomials have few real roots. We show that many of these polynomials are irreducible when the group acts transitively. We close by indicating some future directions of this research. A corrigendum was appended to this paper on 10th October 2014.
Hom Complexes of Set Systems
Authors: Jonsson Jakob 
Published: January 2020

A set system is a pair $\mathcal{S} = (V(\mathcal{S}),\Delta(\mathcal{S}))$, where $\Delta(\mathcal{S})$ is a family of subsets of the set $V(\mathcal{S})$. We refer to the members of $\Delta(\mathcal{S})$ as the stable sets of $\mathcal{S}$. A homomorphism between two set systems $\mathcal{S}$ and $\mathcal{T}$ is a map $f : V(\mathcal{S}) \rightarrow V(\mathcal{T})$ such that the preimage under $f$ of every stable set of $\mathcal{T}$ is a stable set of $\mathcal{S}$. Inspired by a recent generalization due to Engström of Lovász's Hom complex construction, the author associates a cell complex $\mathrm{Hom}(\mathcal{S},\mathcal{T})$ to any two finite set systems $\mathcal{S}$ and $\mathcal{T}$. The main goal of the paper is to examine basic topological and homological properties of this cell complex for various pairs of set systems.
Crossings in Grid Drawings
Authors: Dujmović Vida , Morin Pat , Sheffer Adam 
Published: January 2020

We prove tight crossing number inequalities for geometric graphs whose vertex sets are taken from a $d$-dimensional grid of volume $N$ and give applications of these inequalities to counting the number of crossing-free geometric graphs that can be drawn on such grids.In particular, we show that any geometric graph with $m\geq 8N$ edges and with vertices on a 3D integer grid of volume $N$, has $\Omega((m^2/N)\log(m/N))$ crossings. In $d$-dimensions, with $d\ge 4$, this bound becomes $\Omega(m^2/N)$. We provide matching upper bounds for all $d$. Finally, for $d\ge 4$ the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some $d$-dimensional grid of volume $N$ is $N^{\Theta(N)}$. In 3 dimensions it remains open to improve the trivial bounds, namely, the $2^{\Omega(N)}$ lower bound and the $N^{O(N)}$ upper bound.
The Cost of 2-Distinguishing Cartesian Powers
Authors: Boutin Debra 
Published: January 2020

A graph $G$ is said to be $2$-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the label classes. The minimum size of a label class in any such labeling of $G$ is called the cost of $2$-distinguishing $G$ and is denoted by $\rho(G)$. The determining number of a graph $G$, denoted $\det(G)$, is the minimum size of a set of vertices whose pointwise stabilizer is trivial. The main result of this paper is that if $G^k$ is a $2$-distinguishable Cartesian power of a prime, connected graph $G$ on at least three vertices with $\det(G)\leq k$ and $\max\{2, \det(G)\} < \det(G^k)$, then $\rho(G^k) \in \{\det(G^k), \det(G^k)+1\}$. In particular, for $n\geq 3$, $\rho(K_3^n)\in \{ \left\lceil {\log_3 (2n+1)} \right\rceil$ $+1, \left\lceil {\log_3 (2n+1)} \right\rceil$ $+2\}$.
On Wilf Equivalence for Alternating Permutations
Authors: Yan Sherry H.F. 
Published: January 2020

In this paper, we obtain several new classes of Wilf-equivalent patterns for alternating permutations. In particular, we prove that for any nonempty pattern $\tau$, the patterns $12\ldots k\oplus\tau$ and $k\ldots 21\oplus\tau$ are Wilf-equivalent for alternating permutations, paralleling a result of Backelin, West, and Xin for Wilf equivalence for permutations.
Ascent-Descent Young Diagrams and Pattern Avoidance in Alternating Permutations
Authors: Jagadeesan Ravi 
Published: January 2020

We investigate pattern avoidance in alternating permutations and an alternating analogue of Young diagrams. In particular, using an extension of Babson and West's notion of shape-Wilf equivalence described in our recent paper (with N. Gowravaram), we generalize results of Backelin, West, and Xin and Ouchterlony to alternating permutations. Unlike Ouchterlony and Bóna's bijections, our bijections are not the restrictions of Backelin, West, and Xin's bijections to alternating permutations. This paper is the second of a two-paper series presenting the work of Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (with N. Gowravaram, arXiv:1301.6796v1). The first paper in the series is Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (with N. Gowravaram, Electronic Journal of Combinatorics 20(4):#P17, 2013).
Sisterhood in the Gale-Shapley Matching Algorithm
Authors: Gonczarowski Yannai A. , Friedgut Ehud 
Published: January 2020

Lying in order to manipulate the Gale-Shapley matching algorithm has been studied by Dubins and Freedman (1981) and by Gale and Sotomayor (1985), and was shown to be generally more appealing to the proposed-to side (denoted as the women in Gale and Shapley's seminal paper (1962)) than to the proposing side (denoted as men there). It can also be shown that in the case of lying women, for every woman who is better off due to lying, there exists a man who is worse off.In this paper, we show that an even stronger dichotomy between the goals of the sexes holds, namely, if no woman is worse off then no man is better off, while a form of sisterhood between the lying and the "innocent" women also holds, namely, if none of the former is worse off, then neither is any of the latter. These results are robust: they generalize to the one-to-many variants of the algorithm and do not require the resulting matching to be stable (i.e. they hold even in out-of-equilibria situations). The machinery we develop in our proofs sheds new light on the structure of lying by women in the Gale-Shapley matching algorithm.This paper is based upon an undergraduate thesis (2007) by the first author.
Eigenvalue Pairing in the Response Matrix for a Class of Network Models with Circular Symmetry
Authors: Farber Miriam , Johnson Charles R , Zhen Wei 
Published: January 2020

We consider the response matrices in certain weighted networks that display a circular symmetry. It had been observed empirically that these exhibit several paired (multiplicity two) eigenvalues. Here, this pairing is explained analytically for a version of the model more general than the original. The exact number of necessarily paired eigenvalues is given in terms of the structure of the model, and the special structure of the eigenvectors is also described. Examples are provided.
Coupon Collector Problem for Non-Uniform Coupons and Random Quotas
Authors: Shank Nathan B. , Yang Hannah 
Published: January 2020

We extend the classical coupon collector problem to find the expected number of selections needed to collect $m_i$ (possible random) copies of coupon $i$, when the distribution of the coupons is not necessarily equally likely. Upper and lower bounds which provide limiting asymptotics are also obtained for the expected number of selections needed to fulfill a random quota for each coupon.
Self-Dual Spherical Grids
Authors: Graver Jack E. , Hartung Elizabeth J. 
Published: January 2020

Self-dual plane graphs have been studied extensively. C. A. B Smith and W. T. Tutte published A class of self-dual maps in 1950; in 1992, Archdeacon and Richter described a method for constructing all self-dual plane graphs and a second construction was produced by Servatius and Christopher in 1992. Both constructions are inductive. In this paper, we produce four templates from which all self-dual plane graphs with maximum degree 4 (self-dual spherical grids) can be constructed. The self-dual spherical grids are further subdivided into 27 basic automorphism classes. Self-dual spherical grids in the same automorphism class have similar architecture. A smallest example of each class is constructed.
The Ihara Zeta Function of the Infinite Grid
Authors: Clair Bryan 
Published: January 2020

The infinite grid is the Cayley graph of $\mathbb{Z} \times \mathbb{Z}$ with the usual generators. In this paper, the Ihara zeta function for the infinite grid is computed using elliptic integrals and theta functions. The zeta function of the grid extends to an analytic, multivalued function which satisfies a functional equation. The set of singularities in its domain is finite.The grid zeta function is the first computed example which is non-elementary, and which takes infinitely many values at each point of its domain. It is also the limiting value of the normalized sequence of Ihara zeta functions for square grid graphs and torus graphs.