bluuebunny/crossref_metadata_2025 huggingface dataset:
Respiratory complications in Cerebral Palsy: physiopathological consequences and clinical manifestations
Authors: Giancarlo Garuti  , Gian Piero Bandelli  , Mirco Lusuardi
Published: January 2020

Cerebral palsy (CP) is a condition that can occur at any time during brain development. Although its etiology is multifactorial, CP is usually linked to brain injury or infections during prenatal, perinatal, neonatal or early childhood period. The disability associated with CP varies from mild to severe, and may include involuntary movements, poor coordination, maintaining balance problems and the difficulty of performing voluntary movements. Although this condition (brain impairment) does not directly cause pulmonary complications, neuromuscular dysfunctions do so. In fact, aspiration and ineffective coughing could interfere with normal airway clearance, impair respiratory function, and worsen lung damage, resulting in increased mucus production and reduced secretions elimination. This consequent alteration of the pulmonary defense system increases the susceptibility to serious, progressive lung diseases. Physiotherapy is an essential component in the management of respiratory complications associated with severe CP. For optimal results, however, it is important customized treatment for every patient. This mini non-ystematic review would highlight the possible complications and the possible interventions for reduce them.
La imagen algorítmica. Hacia una nueva (in)visibilidad
Authors: Martínez Luna Sergio
Published: January 2020

El artículo estudia las relaciones entre imagen y técnica desde las actuales transformaciones generadas por la digitalización. Estos procesos configuran una imagen algorítmica que trastoca los parámetros perceptivos y políticos establecidos desde la perspectiva lineal. La imagen algorítmica opera sobre sus usuarios y desarrolla nuevas formas de control y ofuscación. La imagen es un tipo de imagen técnica que adquiere una dimensión performativa capaz de operar sobre sus espectadores-usuarios. El espectador queda descentrado porque no puede percibir las operaciones de las que es objeto. Se recomponen las relaciones entre los registros de lo visible y lo invisible desde los que se impone una reducción de lo real a lo presentado en la pantalla. Por ello se hace necesario explorar nuevos conceptos y prácticas para entender las sujeciones e imperativos que la nueva visualidad digital establece
Sinergias: el arte y sus huellas, construcciones taxonómicas de los puentes del río Medellín que habitan los marginales en el centro de la ciudad
Authors: Pérez Taborda Juan Felipe
Published: January 2020

Este artículo pretende evidenciar algunos procesos de investigación-creación que indaga en las inquietudes y dinámicas relacionadas con los términos arte y etnografía, los cuales son parte integral de la estrategia metodológica de creación para las prácticas artísticas contemporáneas abordadas en un proyecto de Maestría, a partir del cual busco crear consciencia sobre las problemáticas sociales que afectan a la sociedad marginal y los habitantes de calle de la ciudad de Medellín. Desde diversos referentes y disciplinas, como la sociología, la etnografía, la antropología y la microbiología, ahondaré en la identificación y recolección de objetos de tipo taxonómico, arquitectura urbana y el espacio para habitar, en la búsqueda de nuevas expresiones estéticas cuya integración permita trazar un camino hacia la co-creación en las prácticas artística contemporáneas fundamentadas en temas sociales y la habitabilidad en la calle como un objeto de estudio.    La instalación como propuesta de obra, recolecta y procesa de forma creativa sus vestigios, rastros y huellas de existencia en estos espacios urbanos, evidencia así un resultado de investigación-creación, se presenta como el dispositivo artístico que permite en diálogo entre lenguajes, símbolos y construcciones disímiles de cómo se vive la realidad de calle en la ciudad, especialmente desde la perspectiva de quienes la habitan y moran bajo los puentes y viaductos al margen del río Medellín, en la zona céntrica de la ciudad.
The Minimum Size of Complete Caps in $({\Bbb Z}/n{\Bbb Z})^2$
Authors: Huizenga Jack
Published: January 2020

A line in $({\Bbb Z}/n{\Bbb Z})^2$ is any translate of a cyclic subgroup of order $n$. A subset $X\subset ({\Bbb Z}/n{\Bbb Z})^2$ is a cap if no three of its points are collinear, and $X$ is complete if it is not properly contained in another cap. We determine bounds on $\Phi(n)$, the minimum size of a complete cap in $({\Bbb Z}/n{\Bbb Z})^2$. The other natural extremal question of determining the maximum size of a cap in $({\Bbb Z}/n{\Bbb Z})^2$ is considered in a separate preprint by the present author. These questions are closely related to well-studied questions in finite affine and projective geometry. If $p$ is the smallest prime divisor of $n$, we prove that $$\max\{4,\sqrt{2p}+{1\over2}\}\leq \Phi(n)\leq \max\{4,p+1\}.$$ We conclude the paper with a large number of open problems in this area.
A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics
Authors: Flajolet Philippe , Fusy Eric , Gourdon Xavier , Panario Daniel , Pouyanne Nicolas
Published: January 2020

A "hybrid method", dedicated to asymptotic coefficient extraction in combinatorial generating functions, is presented, which combines Darboux's method and singularity analysis theory. This hybrid method applies to functions that remain of moderate growth near the unit circle and satisfy suitable smoothness assumptions—this, even in the case when the unit circle is a natural boundary. A prime application is to coefficients of several types of infinite product generating functions, for which full asymptotic expansions (involving periodic fluctuations at higher orders) can be derived. Examples relative to permutations, trees, and polynomials over finite fields are treated in this way.
Propagation Connectivity of Random Hypergraphs
Authors: Coja-Oghlan Amin , Onsjö Mikael , Watanabe Osamu
Published: January 2020

We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple propagation algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold. Our proof is based on a kind of large deviations analysis of a time-dependent random walk. Based on the analysis, we also give an upper bound on the expected running time of the simple propagation algorithm.
Geometrically Constructed Bases for Homology of Non-Crossing Partition Lattices
Authors: Kenny Aisling
Published: January 2020

For any finite, real reflection group $W$, we construct a geometric basis for the homology of the corresponding non-crossing partition lattice. We relate this to the basis for the homology of the corresponding intersection lattice introduced by Björner and Wachs using a general construction of a generic affine hyperplane for the central hyperplane arrangement defined by $W$.
Improved LP Lower Bounds for Difference Triangle Sets
Authors: Shearer James B.
Published: January 2020

In 1991 Lorentzen and Nilsen showed how to use linear programming to prove lower bounds on the size of difference triangle sets. In this note we show how to improve these bounds by including additional valid linear inequalities in the LP formulation. We also give some new optimal difference triangle sets found by computer search.
Lattice Paths, Sampling Without Replacement, and Limiting Distributions
Authors: Kuba M. , Panholzer A. , Prodinger H.
Published: January 2020

In this work we consider weighted lattice paths in the quarter plane ${\Bbb N}_0\times{\Bbb N}_0$. The steps are given by $(m,n)\to(m-1,n)$, $(m,n)\to(m,n-1)$ and are weighted as follows: $(m,n)\to(m-1,n)$ by $m/(m+n)$ and step $(m,n)\to(m,n-1)$ by $n/(m+n)$. The considered lattice paths are absorbed at lines $y=x/t -s/t$ with $t\in{\Bbb N}$ and $s\in{\Bbb N}_0$. We provide explicit formulæ for the sum of the weights of paths, starting at $(m,n)$, which are absorbed at a certain height $k$ at lines $y=x/t -s/t$ with $t\in{\Bbb N}$ and $s\in{\Bbb N}_0$, using a generating functions approach. Furthermore these weighted lattice paths can be interpreted as probability distributions arising in the context of Pólya-Eggenberger urn models, more precisely, the lattice paths are sample paths of the well known sampling without replacement urn. We provide limiting distribution results for the underlying random variable, obtaining a total of five phase changes.
Competitive Colorings of Oriented Graphs
Authors: Kierstead H. A. , Trotter W. T.
Published: January 2020

Nešetřil and Sopena introduced a concept of oriented game chromatic number and developed a general technique for bounding this parameter. In this paper, we combine their technique with concepts introduced by several authors in a series of papers on game chromatic number to show that for every positive integer $k$, there exists an integer $t$ so that if ${\cal C}$ is a topologically closed class of graphs and ${\cal C}$ does not contain a complete graph on $k$ vertices, then whenever $G$ is an orientation of a graph from ${\cal C}$, the oriented game chromatic number of $G$ is at most $t$. In particular, oriented planar graphs have bounded oriented game chromatic number. This answers a question raised by Nešetřil and Sopena. We also answer a second question raised by Nešetřil and Sopena by constructing a family of oriented graphs for which oriented game chromatic number is bounded but extended Go number is not.
The Packing Density of Other Layered Permutations
Authors: Hästö Peter A.
Published: January 2020

In this paper the packing density of various layered permutations is calculated, thus solving some problems suggested by Albert, Atkinson, Handley, Holton $\&$ Stromquist [Electron. J. Combin. 9 (2002), $\#$R5]. Specifically, the density is found for layered permutations of type $[m_1, \ldots, m_r]$ when $\log(r+1)\le \min\{ m_i\}$. It is also shown how to derive good estimates for the packing density of permutations of type $[k,1,k]$ when $k\ge 3$. Both results are based on establishing the number of layers in near optimal permutations using a layer-merging technique.
A Schröder Generalization of Haglund's Statistic on Catalan Paths
Authors: Egge E. S. , Haglund J. , Killpatrick K. , Kremer D.
Published: January 2020

Garsia and Haiman (J. Algebraic. Combin. $\bf5$ $(1996)$, $191-244$) conjectured that a certain sum $C_n(q,t)$ of rational functions in $q,t$ reduces to a polynomial in $q,t$ with nonnegative integral coefficients. Haglund later discovered (Adv. Math., in press), and with Garsia proved (Proc. Nat. Acad. Sci. ${\bf98}$ $(2001)$, $4313-4316$) the refined conjecture $C_n(q,t) = \sum q^{{\rm area}}t^{{\rm bounce}}$. Here the sum is over all Catalan lattice paths and ${\rm area}$ and ${\rm bounce}$ have simple descriptions in terms of the path. In this article we give an extension of $({\rm area},{\rm bounce})$ to Schröder lattice paths, and introduce polynomials defined by summing $q^{{\rm area}}t^{{\rm bounce}}$ over certain sets of Schröder paths. We derive recurrences and special values for these polynomials, and conjecture they are symmetric in $q,t$. We also describe a much stronger conjecture involving rational functions in $q,t$ and the $\nabla$ operator from the theory of Macdonald symmetric functions.
On Zudilin's $q$-Question about Schmidt's Problem
Authors: Guo Victor J. W. , Zeng Jiang
Published: January 2020

We propose an elemantary approach to Zudilin's $q$-question about Schmidt's problem [Electron. J. Combin. 11 (2004), #R22], which has been solved in a previous paper [Acta Arith. 127 (2007), 17--31]. The new approach is based on a  $q$-analogue of our recent result in  [J. Number Theory 132 (2012), 1731--1740] derived from $q$-Pfaff-Saalschütz identity.
Euler's Partition Theorem with Upper Bounds on Multiplicities
Authors: Chen William Y.C. , Yee Ae Ja , Zhu Albert J. W.
Published: January 2020

We show that the number of partitions of $n$ with alternating sum $k$ such that the multiplicity of each part is bounded by $2m+1$ equals the number of partitions of $n$ with $k$ odd parts such that the multiplicity of each even part is bounded by $m$. The first proof relies on two formulas with two parameters that are related to the four-parameter formulas of Boulet. We also give a combinatorial proof of this result by using Sylvester's bijection, which implies a stronger partition theorem. For $m=0$, our result reduces to Bessenrodt's refinement of Euler's partition theorem. If the alternating sum and the number of odd parts are not taken into account, we are led to a generalization of Euler's partition theorem, which can be deduced from a theorem of Andrews on equivalent upper bound sequences of multiplicities. Analogously, we show that the number of partitions of $n$ with alternating sum $k$ such that the multiplicity of each even part is bounded by $2m+1$ equals the number of partitions of $n$ with $k$ odd parts such that the multiplicity of each even part is also bounded by $2m+1$. We provide a combinatorial proof as well.
Game Colouring Directed Graphs
Authors: Yang Daqing , Zhu Xuding
Published: January 2020

In this paper, a colouring game and two versions of marking games (the weak and the strong) on digraphs are studied. We introduce the weak game chromatic number $\chi_{\rm wg}(D)$ and the weak game colouring number ${\rm wgcol}(D)$ of digraphs $D$. It is proved that if $D$ is an oriented planar graph, then $\chi_{\rm wg}(D)$ $\le {\rm wgcol}(D) \le 9$, and if $D$ is an oriented outerplanar graph, then $\chi_{\rm wg}(D)$ $\le {\rm wgcol}(D) \le 4$. Then we study the strong game colouring number ${\rm sgcol}\left( D \right)$ (which was first introduced by Andres as game colouring number) of digraphs $D$. It is proved that if $D$ is an oriented planar graph, then ${\rm sgcol}\left( D \right) \le 16$. The asymmetric versions of the colouring and marking games of digraphs are also studied. Upper and lower bounds of related parameters for various classes of digraphs are obtained.
The Maximal Length of a $k$-Separator Permutation
Authors: Gunby Benjamin
Published: January 2020

A permutation $\sigma\in S_n$ is a $k$-separator if all of its patterns of length $k$ are distinct. Let $F(k)$ denote the maximal length of a $k$-separator. Hegarty (2013) showed that $k+\left\lfloor\sqrt{2k-1}\right\rfloor-1\leq F(k)\leq k+\left\lfloor\sqrt{2k-3}\right\rfloor$, and conjectured that $F(k)=k+\left\lfloor\sqrt{2k-1}\right\rfloor-1$. This paper will strengthen the upper bound to prove the conjecture for all sufficiently large $k$ (in particular, for all $k\geq 320801$).
A Combinatorial Proof of the Non-Vanishing of Hankel Determinants of the Thue-Morse Sequence
Authors: Bugeaud Yann , Han Guo-Niu
Published: January 2020

In 1998, Allouche, Peyrière, Wen and Wen established that the Hankel determinants associated with the Thue-Morse sequence on $\{-1,1\}$ are always nonzero. Their proof depends on a set of sixteen recurrence relations. We present an alternative, purely combinatorial proof of the same result. We also re-prove a recent result of Coons on the non-vanishing of the Hankel determinants associated to two other classical integer sequences.
Arc-Transitive Dihedral Regular Covers of Cubic Graphs
Authors: Ma Jicheng
Published: January 2020

A regular covering projection is called dihedral or abelian if the covering transformation group is dihedral or abelian. A lot of work has been done with regard to the classification of arc-transitive abelian (or elementary abelian, or cyclic) covers of symmetric graphs. In this paper, we investigate arc-transitive dihedral regular covers of symmetric (arc-transitive) cubic graphs. In particular, we classify all arc-transitive dihedral regular covers of $K_4$, $K_{3,3}$, the 3-cube $Q_3$ and the Petersen graph.
The Degree-Diameter Problem for Sparse Graph Classes
Authors: Pineda-Villavicencio Guillermo , Wood David R.
Published: January 2020

The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree $\Delta$ and diameter $k$. For fixed $k$, the answer is $\Theta(\Delta^k)$. We consider the degree-diameter problem for particular classes of sparse graphs, and establish the following results. For graphs of bounded average degree the answer is $\Theta(\Delta^{k-1})$, and for graphs of bounded arboricity the answer is $\Theta(\Delta^{\lfloor k/2\rfloor})$, in both cases for fixed $k$. For graphs of given treewidth, we determine the maximum number of vertices up to a constant factor. Other precise bounds are given for graphs embeddable on a given surface and apex-minor-free graphs.
A Theory of Transformation Monoids: Combinatorics and Representation Theory
Authors: Steinberg Benjamin
Published: January 2020

The aim of this paper is to develop a theory of finite transformation monoids and in particular to study primitive transformation monoids. We introduce the notion of orbitals and orbital digraphs for transformation monoids and prove a monoid version of D. Higman's celebrated theorem characterizing primitivity in terms of connectedness of orbital digraphs. A thorough study of the module (or representation) associated to a transformation monoid is initiated. In particular, we compute the projective cover of the transformation module over a field of characteristic zero in the case of a transitive transformation or partial transformation monoid. Applications of probability theory and Markov chains to transformation monoids are also considered and an ergodic theorem is proved in this context. In particular, we obtain a generalization of a lemma of P. Neumann, from the theory of synchronizing groups, concerning the partition associated to a transformation of minimal rank.
A Slight Improvement to the Colored Bárány's Theorem
Authors: Jiang Zilin
Published: January 2020

Suppose $d+1$ absolute continuous probability measures $m_0, \ldots, m_d$ on $\mathbb{R}^d$ are given. In this paper, we prove that there exists a point of $\mathbb{R}^d$ that belongs to the convex hull of $d+1$ points $v_0, \ldots, v_d$ with probability at least $\frac{2d}{(d+1)!(d+1)}$, where each point $v_i$ is sampled independently according to probability measure $m_i$.
Sandpiles and Dominos
Authors: Florescu Laura , Morar Daniela , Perkinson David , Salter Nicholas , Xu Tianyuan
Published: January 2020

We consider the subgroup of the abelian sandpile group of the grid graph consisting of configurations of sand that are symmetric with respect to central vertical and horizontal axes. We show that the size of this group is (i) the number of domino tilings of a corresponding weighted rectangular checkerboard; (ii) a product of special values of Chebyshev polynomials; and (iii) a double-product whose factors are sums of squares of values of trigonometric functions. We provide a new derivation of the formula due to Kasteleyn and to Temperley and Fisher for counting the number of domino tilings of a $2m \times 2n$ rectangular checkerboard and a new way of counting the number of domino tilings of a $2m \times 2n$ checkerboard on a Möbius strip.
Proof of the Combinatorial Nullstellensatz over Integral Domains, in the Spirit of Kouba
Authors: Heinig Peter
Published: January 2020

It is shown that by eliminating duality theory of vector spaces from a recent proof of Kouba [A duality based proof of the Combinatorial Nullstellensatz, Electron. J. Combin. 16 (2009), #N9] one obtains a direct proof of the nonvanishing-version of Alon's Combinatorial Nullstellensatz for polynomials over an arbitrary integral domain. The proof relies on Cramer's rule and Vandermonde's determinant to explicitly describe a map used by Kouba in terms of cofactors of a certain matrix. That the Combinatorial Nullstellensatz is true over integral domains is a well-known fact which is already contained in Alon's work and emphasized in recent articles of Michałek and Schauz; the sole purpose of the present note is to point out that not only is it not necessary to invoke duality of vector spaces, but by not doing so one easily obtains a more general result.
A Note on Statistical Averages for Oscillating Tableaux
Authors: Hopkins Sam , Zhang Ingrid
Published: January 2020

Oscillating tableaux are certain walks in Young's lattice of partitions; they generalize standard Young tableaux. The shape of an oscillating tableau is the last partition it visits and the length of an oscillating tableau is the number of steps it takes. We define a new statistic for oscillating tableaux that we call weight: the weight of an oscillating tableau is the sum of the sizes of all the partitions that it visits.  We show that the average weight of all oscillating tableaux of shape $\lambda$ and length $|\lambda|+2n$ (where $|\lambda|$ denotes the size of $\lambda$ and $n \in \mathbb{N}$) has a surprisingly simple formula: it is a quadratic polynomial in $|\lambda|$ and $n$. Our proof via the theory of differential posets is largely computational. We suggest how the homomesy paradigm of Propp and Roby may lead to a more conceptual proof of this result and reveal a hidden symmetry in the set of perfect matchings.
Gammoids, Pseudomodularity and Flatness Degree
Authors: Olarte Jorge Alberto
Published: January 2020

We introduce the concept of flatness degree for matroids, as a generalization of submodularity. This represents weaker variations of the concept of flatness which characterize strict gammoids for finite matroids. We prove that having flatness degree 3, which is the smallest non-trivial flatness degree, implies pseudomodularity on the lattice of flats of the matroid. We show however an example of a gammoid for which the converse is not true. We also show examples of gammoids with each possible flatness degree. All of this examples show that pseudomodular gammoids are not necessarily strict.
A Recurrence Relation for the "inv" Analogue of $q$-Eulerian Polynomials
Authors: Chow Chak-On
Published: January 2020

We study in the present work a recurrence relation, which has long been overlooked, for the $q$-Eulerian polynomial $A_n^{{\rm des},{\rm inv}}(t,q) =\sum_{\sigma\in\mathfrak{S}_n} t^{{\rm des}(\sigma)}q^{{\rm inv}(\sigma)}$, where ${\rm des}(\sigma)$ and ${\rm inv}(\sigma)$ denote, respectively, the descent number and inversion number of $\sigma$ in the symmetric group $\mathfrak{S}_n$ of degree $n$. We give an algebraic proof and a combinatorial proof of the recurrence relation.
Ratio Monotonicity of Polynomials Derived from Nondecreasing Sequences
Authors: Chen William Y. C. , Yang Arthur L. B. , Zhou Elaine L. F.
Published: January 2020

The ratio monotonicity of a polynomial is a stronger property than log-concavity. Let $P(x)$ be a polynomial with nonnegative and nondecreasing coefficients. We prove the ratio monotone property of $P(x+1)$, which leads to the log-concavity of $P(x+c)$ for any $c\geq 1$ due to Llamas and Martínez-Bernal. As a consequence, we obtain the ratio monotonicity of the Boros-Moll polynomials obtained by Chen and Xia without resorting to the recurrence relations of the coefficients.
Characteristic Flows on Signed Graphs and Short Circuit Covers
Authors: Máčajová Edita , Škoviera Martin
Published: January 2020

We generalise to signed graphs a classical result of Tutte [Canad. J. Math. 8 (1956), 13—28] stating that every integer flow can be expressed as a sum of characteristic flows of circuits. In our generalisation, the rôle of circuits is taken over by signed circuits of a signed graph which occur in two types — either balanced circuits or pairs of disjoint unbalanced circuits connected with a path intersecting them only at its ends. As an application of this result we show that a signed graph $G$ admitting a nowhere-zero $k$-flow has a covering with signed circuits of total length at most $2(k-1)|E(G)|$.
Backward Jeu de Taquin Slides for Composition Tableaux and a Noncommutative Pieri Rule
Authors: Tewari Vasu
Published: January 2020

We give a backward jeu de taquin slide analogue on semistandard reverse composition tableaux. These tableaux were first studied by Haglund, Luoto, Mason and van Willigenburg when defining quasisymmetric Schur functions. Our algorithm for performing backward jeu de taquin slides on semistandard reverse composition tableaux results in a natural operator on compositions that we call the jdt operator. This operator in turn gives rise to a new poset structure on compositions whose maximal chains we enumerate. As an application, we also give a noncommutative Pieri rule for noncommutative Schur functions that uses the jdt operators.
Which Haar graphs are Cayley graphs?
Authors: Estélyi István , Pisanski Tomaž
Published: January 2020

For a finite group $G$ and subset $S$ of $G,$ the Haar graph $H(G,S)$ is a bipartite regular graph, defined as a regular $G$-cover of a dipole with $|S|$ parallel arcs labelled by elements of $S$. If $G$ is an abelian group, then $H(G,S)$ is well-known to be a Cayley graph; however, there are examples of non-abelian groups $G$ and subsets $S$ when this is not the case. In this paper we address the problem of classifying finite non-abelian groups $G$ with the property that every Haar graph $H(G,S)$ is a Cayley graph. An equivalent condition for $H(G,S)$ to be a Cayley graph of a group containing $G$ is derived in terms of $G, S$ and $\mathrm{Aut } G$. It is also shown that the dihedral groups, which are solutions to the above problem, are $\mathbb{Z}_2^2,D_3,D_4$ and $D_{5}$.
Polynomials Defined by Tableaux and Linear Recurrences
Authors: Alexandersson Per
Published: January 2020

We show that several families of polynomials defined via fillings of diagrams satisfy linear recurrences under a natural operation on the shape of the diagram. We focus on key polynomials, (also known as Demazure characters), and Demazure atoms. The same technique can be applied to Hall-Littlewood polynomials and dual Grothendieck polynomials.The motivation behind this is that such recurrences are strongly connected with other nice properties, such as interpretations in terms of lattice points in polytopes and divided difference operators.
Lattice Path Proofs of Extended Bressoud-Wei and Koike Skew Schur Function Identities
Authors: Hamel A. M. , King R. C.
Published: January 2020

A recent paper of the present authors provides extensions to two classical determinantal results of Bressoud and Wei, and of Koike. The proofs in that paper were algebraic. The present paper contains combinatorial lattice path proofs.
Random Subcube Intersection Graphs I: Cliques and Covering
Authors: Falgas-Ravry Victor , Markström Klas
Published: January 2020

We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube $Q_d$ to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model 'random compatibility' between vertices in a large network.For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube $Q_d$ and for the appearance of $s$-cliques. In addition we pose a number of open problems.
Completing Partial Latin Squares with One Nonempty Row, Column, and Symbol
Authors: Kuhl Jaromy , Schroeder Michael W.
Published: January 2020

Let $r,c,s\in\{1,2,\ldots,n\}$ and let $P$ be a partial latin square of order $n$ in which each nonempty cell lies in row $r$, column $c$, or contains symbol $s$. We show that if $n\notin\{3,4,5\}$ and row $r$, column $c$, and symbol $s$ can be completed in $P$, then a completion of $P$ exists. As a consequence, this proves a conjecture made by Casselgren and Häggkvist. Furthermore, we show exactly when row $r$, column $c$, and symbol $s$ can be completed.
Representations of Bicircular Lift Matroids
Authors: Chen Rong , Gao Zifei
Published: January 2020

Bicircular lift matroids are a class of matroids defined on the edge set of a graph. For a given graph $G$, the circuits of its bicircular lift matroid are the edge sets of those subgraphs of $G$ that contain at least two cycles, and are minimal with respect to this property. The main result of this paper is a characterization of when two graphs give rise to the same bicircular lift matroid, which answers a question proposed by Irene Pivotto. In particular, aside from some appropriately defined "small" graphs, two graphs have the same bicircular lift matroid if and only if they are $2$-isomorphic in the sense of Whitney.
On the Staircases of Gyárfás
Authors: Csányi János , Hajnal Peter , Nagy Gábor V.
Published: January 2020

In a 2011 paper, Gyárfás investigated a geometric Ramsey problem on convex, separated, balanced, geometric $K_{n,n}$. This led to appealing extremal problem on square 0-1 matrices. Gyárfás conjectured that any 0-1 matrix of size $n\times n$ has a staircase of size $n-1$.We introduce the non-symmetric version of Gyárfás' problem. We give upper bounds and in certain range matching lower bound on the corresponding extremal function. In the square/balanced case we improve the $(4/5+\epsilon)n$ lower bound of Cai, Gyárfás et al. to $5n/6-7/12$. We settle the problem when instead of considering maximum staircases we deal with the sum of the size of the longest $0$- and $1$-staircases.
Infinite Excursions of Rotor Walks on Regular Trees
Authors: Müller Sebastian , Orenshtein Tal
Published: January 2020

A rotor configuration on a graph contains in every vertex an infinite ordered sequence of rotors, each is pointing to a neighbor of the vertex. After sampling a configuration according to some probability measure, a rotor walk is a deterministic process: at each step it chooses the next unused rotor in its current location, and uses it to jump to the neighboring vertex to which it points. Rotor walks capture many aspects of the expected behavior of simple random walks. However, this similarity breaks down for the property of having an infinite excursion. In this paper we study that question for natural random configuration models on regular trees. Our results suggest that in this context the rotor model behaves like the simple random walk unless it is not "close to" the standard rotor-router model.
A $q$-Analog of Foulkes' Conjecture
Authors: Bergeron François
Published: January 2020

We propose a $q$-analog of classical plethystic conjectures due to Foulkes. In our conjectures, a divided difference of plethysms of Hall-Littlewood polynomials $H_n(\boldsymbol{x};q)$ replaces the analogous difference of plethysms of complete homogeneous symmetric functions $h_n(\boldsymbol{x})$ in Foulkes' conjecture. At $q=0$, we get back the original statement of Foulkes, and we show that our version holds at $q=1$. We discuss further supporting evidence, as well as various generalizations, including a $(q,t)$-version.
Minimum Weight $H$-Decompositions of Graphs: The Bipartite Case
Authors: Sousa Teresa
Published: January 2020

Given graphs $G$ and $H$ and a positive number $b$, a weighted $(H,b)$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms an $H$-subgraph. We assign a weight of $b$ to each $H$-subgraph in the decomposition and a weight of 1 to single edges. The total weight of the decomposition is the sum of the weights of all elements in the decomposition. Let $\phi(n,H,b)$ be the the smallest number such that any graph $G$ of order $n$ admits an $(H,b)$-decomposition with weight at most $\phi(n,H,b)$. The value of the function $\phi(n,H,b)$ when $b=1$ was determined, for large $n$, by Pikhurko and Sousa [Minimum $H$-Decompositions of Graphs, Journal of Combinatorial Theory, B, 97 (2007), 1041–1055.] Here we determine the asymptotic value of $\phi(n,H,b)$ for any fixed bipartite graph $H$ and any value of $b$ as $n$ tends to infinity.
Covers of D-Type Artin Groups
Authors: Amram Meirav , Shwartz Robert , Teicher Mina
Published: January 2020

We study certain quotients of generalized Artin groups which have a natural map onto D-type Artin groups, where the generalized Artin group $A(T)$ is defined by a signed graph $T$. Then we find a certain quotient $G(T)$ according to the graph $T$, which also have a natural map onto $A(D_n)$. We prove that $G(T)$ is isomorphic to a semidirect product of a group $K^{(m,n)}$, with the Artin group $A(D_n)$, where $K^{(m,n)}$ depends only on the number $m$ of cycles and on the number $n$ of vertices of the graph $T$.
Small Subgraphs in the Trace of a Random Walk
Authors: Krivelevich Michael , Michaeli Peleg
Published: January 2020

We consider the combinatorial properties of the trace of a random walk on the complete graph and on the random graph $G(n,p)$. In particular, we study the appearance of a fixed subgraph in the trace. We prove that for a subgraph containing a cycle, the threshold for its appearance in the trace of a random walk of length $m$ is essentially equal to the threshold for its appearance in the random graph drawn from $G(n,m)$. In the case where the base graph is the complete graph, we show that a fixed forest appears in the trace typically much earlier than it appears in $G(n,m)$.
Forbidden Pairs with a Common Graph Generating Almost the Same Sets
Authors: Chiba Shuya , Fujisawa Jun , Furuya Michitaka , Ikarashi Hironobu
Published: January 2020

Let $\mathcal{H}$ be a family of connected graphs. A graph $G$ is said to be $\mathcal{H}$-free if $G$ does not contain any members of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{F}(\mathcal{H})$ be the family of connected $\mathcal{H}$-free graphs. In this context, the members of $\mathcal{H}$ are called forbidden subgraphs.In this paper, we focus on two pairs of forbidden subgraphs containing a common graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $H_{1}$ is twin-less. If the symmetric difference of $\mathcal{F}(\{H_{1},H_{2}\})$ and $\mathcal{F}(\{H_{1},H_{3}\})$ is finite and the tuple $(H_{1};H_{2},H_{3})$ is non-trivial in a sense, then $H_{2}$ and $H_{3}$ are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [Combin. Probab. Comput. 22 (2013) 733–748] concerning forbidden pairs.
The Gorenstein Property for Projective Coordinate Rings of the Moduli of Parabolic $\mathrm{SL}_2$-Principal Bundles on a Smooth Curve
Authors: Faust Theodore , Manon Christopher
Published: January 2020

Using combinatorial methods, we determine that a projective coordinate ring of the moduli of parabolic principal $\mathrm{SL}_2-$bundles on a marked projective curve is not Gorenstein when the genus and number of marked points are greater than $1$.
Classification of $Q$-Multiplicity-Free Skew Schur $Q$-Functions
Authors: Schure Christopher
Published: January 2020

We classify the $Q$-multiplicity-free skew Schur $Q$-functions. Towards this result, we also provide new relations between the shifted Littlewood-Richardson coefficients.
On Reay's Relaxed Tverberg Conjecture and Generalizations of Conway's Thrackle Conjecture
Authors: Asada Megumi , Chen Ryan , Frick Florian , Huang Frederick , Polevy Maxwell , Stoner David , Tsang Ling Hei , Wellner Zoe
Published: January 2020

Reay's relaxed Tverberg conjecture and Conway's thrackle conjecture are open problems about the geometry of pairwise intersections. Reay asked for the minimum number of points in Euclidean $d$-space that guarantees any such point set admits a partition into $r$ parts, any $k$ of whose convex hulls intersect. Here we give new and improved lower bounds for this number, which Reay conjectured to be independent of $k$. We prove a colored version of Reay's conjecture for $k$ sufficiently large, but nevertheless $k$ independent of dimension $d$. Pairwise intersecting convex hulls have severely restricted combinatorics. This is a higher-dimensional analogue of Conway's thrackle conjecture or its linear special case. We thus study convex-geometric and higher-dimensional analogues of the thrackle conjecture alongside Reay's problem and conjecture (and prove in two special cases) that the number of convex sets in the plane is bounded by the total number of vertices they involve whenever there exists a transversal set for their pairwise intersections. We thus isolate a geometric property that leads to bounds as in the thrackle conjecture. We also establish tight bounds for the number of facets of higher-dimensional analogues of linear thrackles and conjecture their continuous generalizations.
New Upper Bound for Sums of Dilates
Authors: Bush Albert , Zhao Yi
Published: January 2020

For $\lambda \in \mathbb{Z}$, let $\lambda \cdot A = \{ \lambda a : a \in A\}$. Suppose $r, h\in \mathbb{Z}$ are sufficiently large and comparable to each other. We prove that if $|A+A| \le K |A|$ and $\lambda_1, \ldots, \lambda_h \le 2^r$, then \[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{ 7 rh /\ln (r+h) } |A|. \]This improves upon a result of Bukh who shows that\[ |\lambda_1 \cdot A + \ldots + \lambda_h \cdot A | \le K^{O(rh)} |A|. \]Our main technique is to combine Bukh's idea of considering the binary expansion of $\lambda_i$ with a result on biclique decompositions of bipartite graphs.
On Almost-Planar Graphs
Authors: Ding Guoli , Fallon Joshua , Marshall Emily
Published: January 2020

A nonplanar graph $G$ is called almost-planar if for every edge $e$ of $G$, at least one of $G\backslash e$ and $G/e$ is planar. In 1990, Gubser characterized 3-connected almost-planar graphs in his dissertation. However, his proof is so long that only a small portion of it was published. The main purpose of this paper is to provide a short proof of this result. We also discuss the structure of almost-planar graphs that are not 3-connected.
Unified Hanani–Tutte Theorem
Authors: Fulek Radoslav , Kynčl Jan , Pálvölgyi Dömötör
Published: January 2020

We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph $G$ has a drawing $D$ in the plane where every pair of independent edges crosses an even number of times, then $G$ has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in $D$. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.
Eigenvalue Bounds for the Signless $p$-Laplacian
Authors: Borba Elizandro Max , Schwerdtfeger Uwe
Published: January 2020

We consider the signless $p$-Laplacian $Q_p$ of a graph, a generalisation of the quadratic form of the signless Laplacian matrix (the case $p=2$). In analogy to Rayleigh's principle the minimum and maximum of $Q_p$ on the $p$-norm unit sphere are called its smallest and largest eigenvalues, respectively. We show a Perron-Frobenius property and basic inequalites for the largest eigenvalue and provide upper and lower bounds for the smallest eigenvalue in terms of a graph parameter related to the bipartiteness. The latter result generalises bounds by Desai and Rao and, interestingly, at $p=1$ upper and lower bounds coincide.
A Short Proof of Moll's Minimal Conjecture
Authors: Lv Lun
Published: January 2020

We give a short proof of Moll's minimal conjecture, which has been confirmed by Chen and Xia.
Hamilton Circles in Cayley Graphs
Authors: Miraftab Babak , Rühmann Tim
Published: January 2020

For locally finite infinite graphs the notion of Hamilton cycles can be extended to Hamilton circles, homeomorphic images of $S^1$ in the Freudenthal compactification. In this paper we prove a sufficient condition for the existence of Hamilton circles in locally finite Cayley graphs.
A Characterization of Hermitian Varieties as Codewords
Authors: Aguglia Angela , Bartoli Daniele , Storme Leo , Weiner Zsuzsa
Published: January 2020

It is known that the Hermitian varieties are codewords in the code defined by the points and hyperplanes of the projective spaces $\mathrm{PG}(r,q^2)$. In finite geometry, also quasi-Hermitian varieties are defined. These are sets of points of $\mathrm{PG}(r,q^2)$ of the same size as a non-singular Hermitian variety of $\mathrm{PG}(r,q^2)$, having the same intersection sizes with the hyperplanes of $\mathrm{PG}(r,q^2)$. In the planar case, this reduces to the definition of a unital. A famous result of Blokhuis, Brouwer, and Wilbrink states that every unital in the code of the points and lines of $\mathrm{PG}(2,q^2)$ is a Hermitian curve. We prove a similar result for the quasi-Hermitian varieties in $\mathrm{PG}(3,q^2)$, $q=p^{h}$, as well as in $\mathrm{PG}(r,q^2)$, $q=p$ prime, or $q=p^2$, $p$ prime, and $r\geq 4$.
Every Plane Graph is Facially-Non-Repetitively $C$-choosable
Authors: Gutowski Grzegorz
Published: January 2020

A sequence $\left(x_1,x_2,\ldots,x_{2n}\right)$ of even length is a repetition if $\left(x_1,\ldots,x_n\right) =\left(x_{n+1},\ldots,x_{2n}\right)$. We prove existence of a constant $C < 10^{4 \cdot 10^7}$ such that given any planar drawing of a graph $G$, and a list $L(v)$ of $C$ permissible colors for each vertex $v$ in $G$, there is a choice of a permissible color for each vertex such that the sequence of colors of the vertices on any facial simple path in $G$ is not a repetition.
Distribution of Coefficients of Rank Polynomials for Random Sparse Graphs
Authors: Jakobson Dmitry , MacRury Calum , Norin Sergey , Turner Lise
Published: January 2020

We study the distribution of coefficients of rank polynomials of random sparse graphs. We first discuss the limiting distribution for general graph sequences that converge in the sense of Benjamini-Schramm. Then we compute the limiting distribution and Newton polygons of the coefficients of the rank polynomial of random $d$-regular graphs.
Path Choosability of Planar Graphs
Authors: Chappell Glenn G. , Hartman Chris
Published: January 2020

A path coloring of a graph $G$ is a vertex coloring of $G$ such that each color class induces a disjoint union of paths. We consider a path-coloring version of list coloring for planar and outerplanar graphs. We show that if each vertex of a planar graph is assigned a list of $3$ colors, then the graph admits a path coloring in which each vertex receives a color from its list. We prove a similar result for outerplanar graphs and lists of size $2$.For outerplanar graphs we prove a multicoloring generalization. We assign each vertex of a graph a list of $q$ colors. We wish to color each vertex with $r$ colors from its list so that, for each color, the set of vertices receiving it induces a disjoint union of paths. We show that we can do this for all outerplanar graphs if and only if $q/r \ge 2$. For planar graphs we conjecture that a similar result holds with $q/r \ge 3$; we present partial results toward this conjecture.
On Arc-Transitive Metacyclic Covers of Graphs with Order Twice a Prime
Authors: Huang Zhaohong , Pan Jiangmin
Published: January 2020

Quite a lot of attention has been paid recently to the characterization and construction of edge- or arc-transitive abelian (mostly cyclic or elementary abelian) covers of symmetric graphs, but there are rare results for nonabelian covers since the voltage graph techniques are generally not easy to be used in this case. In this paper, we will classify certain metacyclic arc-transitive covers of all non-complete symmetric graphs with prime valency and twice a prime order $2p$ (involving the complete bipartite graph ${\sf K}_{p,p}$, the Petersen graph, the Heawood graph, the Hadamard design on $22$ points and an infinite family of prime-valent arc-regular graphs of dihedral groups). A few previous results are extended.
Lozenge Tilings of a Halved Hexagon with an Array of Triangles Removed from the Boundary, Part II
Authors: Lai Tri
Published: January 2020

Proctor's work on staircase plane partitions yields an exact enumeration of lozenge tilings of a halved hexagon on the triangular lattice. Rohatgi later extended this tiling enumeration to a halved hexagon with a triangle cut off from the boundary. In his previous paper, the author proved  a common generalization of Proctor's and Rohatgi's results by enumerating lozenge tilings of a halved hexagon in the case an array of an arbitrary number of triangles has been removed from a non-staircase side. In this paper we consider the other case when the array of triangles has been removed from the staircase side of the halved hexagon. Our result also implies an explicit formula for the number of tilings of a hexagon with an array of triangles removed perpendicularly to the symmetry axis.
On Monochromatic Pairs of Nondecreasing Diameters
Authors: O'Neal Adam , Schroeder Michael W.
Published: January 2020

Let $n$, $m$, $r$, $t$ be positive integers and $\Delta:[n]\to[r]$. We say $\Delta$ is $(m,r,t)$-permissible if there exist $t$ disjoint $m$-sets $B_1,\dots,B_t$ contained in $[n]$ for which

$|\Delta(B_i)|=1$ for each $i=1,2,\dots,t$,

$\max(B_i) < \min(B_{i+1})$ for each $i=1,2,\dots,t-1$, and

$\max(B_i)-\min(B_i) \leq \max(B_{i+1})-\max(B_{i+1})$ for each $i=1,2,\dots,t-1$.

Let $f(m,r,t)$ be the smallest such $n$ so that all colorings $\Delta$ are $(m,r,t)$-permissible. In this paper, we show that $f(2,2,t)=5t-4$.
Uniform Generation of Spanning Regular Subgraphs of a Dense Graph
Authors: Gao Pu , Greenhill Catherine
Published: January 2020

Let $H_n$ be a graph on $n$ vertices and let $\overline{H_n}$ denote the complement of $H_n$. Suppose that $\Delta = \Delta(n)$ is the maximum degree of $\overline{H_n}$. We analyse three algorithms for sampling $d$-regular subgraphs ($d$-factors) of $H_n$. This is equivalent to uniformly sampling $d$-regular graphs which avoid a set $E(\overline{H_n})$ of forbidden edges. Here $d=d(n)$ is a positive integer which may depend on $n$.

Two of these algorithms produce a uniformly random $d$-factor of $H_n$ in expected runtime which is linear in $n$ and low-degree polynomial in $d$ and $\Delta$. The first algorithm applies when $(d+\Delta)d\Delta = o(n)$. This improves on an earlier algorithm by the first author, which required constant $d$ and at most a linear number of edges in $\overline{H_n}$. The second algorithm applies when $H_n$ is regular and $d^2+\Delta^2 = o(n)$, adapting an approach developed by the first author together with Wormald. The third algorithm is a simplification of the second, and produces an approximately uniform $d$-factor of $H_n$ in time $O(dn)$.  Here the output distribution differs from uniform by $o(1)$ in total variation distance, provided that $d^2+\Delta^2 = o(n)$.
Permutations with Orders Coprime to a Given Integer
Authors: Bamberg John , Glasby S. P. , Harper Scott , Praeger Cheryl E.
Published: January 2020

Let $m$ be a positive integer and let $\rho(m,n)$ be the proportion of permutations of the symmetric group $\mathrm{Sym}(n)$ whose order is coprime to $m$. In 2002, Pouyanne proved that $\rho(n,m)n^{1-\frac{\phi(m)}{m}}\sim \kappa_m$ where $\kappa_m$ is a complicated (unbounded) function of $m$. We show that there exists a positive constant $C(m)$ such that, for all $n \geq m$,\[C(m) \left(\frac{n}{m}\right)^{\frac{\phi(m)}{m}-1} \leq \rho(n,m) \leq \left(\frac{n}{m}\right)^{\frac{\phi(m)}{m}-1}\]where $\phi$ is Euler's totient function.
A Counterexample to a Conjecture of Erdős, Graham and Spencer
Authors: Guo Song
Published: January 2020

It is conjectured by Erdős, Graham and Spencer that if $1 \leq a_1 \leq a_2 \leq \cdots \leq a_s$ with $\sum_{i=1}^s 1/a_i < n - 1/30$, then this sum can be decomposed into $n$ parts so that all partial sums are $\leq 1$. In this note we propose a counterexample which gives a negative answer to this conjecture.
The Tripartite Separability of Density Matrices of Graphs
Authors: Wang Zhen , Wang Zhixi
Published: January 2020

The density matrix of a graph is the combinatorial laplacian matrix of a graph normalized to have unit trace. In this paper we generalize the entanglement properties of mixed density matrices from combinatorial laplacian matrices of graphs discussed in Braunstein et al. [Annals of Combinatorics, 10 (2006) 291] to tripartite states. Then we prove that the degree condition defined in Braunstein et al. [Phys. Rev. A, 73 (2006) 012320] is sufficient and necessary for the tripartite separability of the density matrix of a nearest point graph.