bluuebunny/crossref_metadata_2025 huggingface dataset:
Van der Waerden/Schrijver-Valiant like Conjectures and Stable (aka Hyperbolic) Homogeneous Polynomials: One Theorem for all
Authors: Gurvits Leonid
Published: January 2020

Let $p$ be a homogeneous polynomial of degree $n$ in $n$ variables, $p(z_1,...,z_n) = p(Z) , Z \in C^{n}$. We call a such polynomial $p$ H-Stable if $p(z_1,...,z_n) \neq 0$ provided the real parts $Re(z_i) > 0, 1 \leq i \leq n$. This notion from Control Theory is closely related to the notion of Hyperbolicity used intensively in the PDE theory. The main theorem in this paper states that if $p(x_1,...,x_n)$ is a homogeneous H-Stable polynomial of degree $n$ with nonnegative coefficients; $deg_{p}(i)$ is the maximum degree of the variable $x_i$, $C_i = \min(deg_{p}(i),i)$ and $Cap(p) = \inf_{x_i > 0, 1 \leq i \leq n} {p(x_1,...,x_n)\over x_1 \cdots x_n}$ then the following inequality holds $${\partial^n\over\partial x_1...\partial x_n} p(0,...,0) \geq Cap(p) \prod_{2 \leq i \leq n} \bigg({C_i-1\over C_i}\bigg)^{C_{i}-1}.$$ This inequality is a vast (and unifying) generalization of the Van der Waerden conjecture on the permanents of doubly stochastic matrices as well as the Schrijver-Valiant conjecture on the number of perfect matchings in $k$-regular bipartite graphs. These two famous results correspond to the H-Stable polynomials which are products of linear forms. Our proof is relatively simple and "noncomputational"; it uses just very basic properties of complex numbers and the AM/GM inequality.
On the Eulerian Enumeration of Involutions
Authors: Chow Chak-On
Published: January 2020

We consider in this work the enumeration of involutions by descent sets, and based on that, by descent numbers. Formulas of the number of involutions with a prescribed descent set, with a prescribed descent number and Frobenius-type formulas are given.
On Growth Rates of Permutations, Set Partitions, Ordered Graphs and Other Objects
Authors: Klazar Martin
Published: January 2020

For classes ${\cal O}$ of structures on finite linear orders (permutations, ordered graphs etc.) endowed with containment order $\preceq$ (containment of permutations, subgraph relation etc.), we investigate restrictions on the function $f(n)$ counting objects with size $n$ in a lower ideal in $({\cal O},\preceq)$. We present a framework of edge $P$-colored complete graphs $({\cal C}(P),\preceq)$ which includes many of these situations, and we prove for it two such restrictions (jumps in growth): $f(n)$ is eventually constant or $f(n)\ge n$ for all $n\ge 1$; $f(n)\le n^c$ for all $n\ge 1$ for a constant $c>0$ or $f(n)\ge F_n$ for all $n\ge 1$, $F_n$ being the Fibonacci numbers. This generalizes a fragment of a more detailed theorem of Balogh, Bollobás and Morris on hereditary properties of ordered graphs.
On the Number of Planar Orientations with Prescribed Degrees
Authors: Felsner Stefan , Zickfeld Florian
Published: January 2020

We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice models. The notion of orientations with out-degrees prescribed by a function $\alpha:V\rightarrow {\Bbb N}$ unifies many different combinatorial structures, including the afore mentioned. We call these orientations $\alpha$-orientations. The main focus of this paper are bounds for the maximum number of $\alpha$-orientations that a planar map with $n$ vertices can have, for different instances of $\alpha$. We give examples of triangulations with $2.37^n$ Schnyder woods, 3-connected planar maps with $3.209^n$ Schnyder woods and inner triangulations with $2.91^n$ bipolar orientations. These lower bounds are accompanied by upper bounds of $3.56^n$, $8^n$ and $3.97^n$ respectively. We also show that for any planar map $M$ and any $\alpha$ the number of $\alpha$-orientations is bounded from above by $3.73^n$ and describe a family of maps which have at least $2.598^n$ $\alpha$-orientations.
Asymptotically Optimal Box Packing Theorems
Authors: Reid Michael
Published: January 2020

Given a protoset of $d$-dimensional polyominoes, we ask which boxes can be packed by the protoset. In some cases, it may be too difficult to give a complete answer to this question, so we ask the easier question about determining all sufficiently large boxes that can be packed. (We say that a box is "sufficiently large" if all edge lengths are ${} \ge C$ for some large $C$.) We give numerous examples (mostly $2$-dimensional) where we can answer this easier question. The various techniques involved are: checkerboard-type colorings/numberings (tile homology), the boundary word method of Conway and Lagarias (tile homotopy), ad hoc geometric arguments, and a very nice theorem of Barnes. Barnes' Theorem asserts that all necessary conditions for a box to be packable can be given in a certain form, and these conditions are also sufficient for large boxes. Barnes' Theorem has not received the appreciation it deserves. We give a new, purely combinatorial proof of this important result. (Barnes' original proof uses techniques of algebraic geometry.) In the special case that all the prototiles are boxes themselves, we show how to determine all sufficiently large boxes that they pack. We prove a theorem based on Barnes' result that reduces this to a straightforward calculation.
Words with Simple Burrows-Wheeler Transforms
Authors: Simpson Jamie , Puglisi Simon J.
Published: January 2020

Mantaci et al have shown that if a word $x$ on the alphabet $\{a,b\}$ has a Burrows-Wheeler Transform of the form $b^ia^j$ then $x$ is a conjugate or a power of a conjugate of a standard word. We give an alternative proof of this result and describe words on the alphabet $\{a,b,c\}$ whose transforms have the form $c^ib^ja^k$. These words have some common properties with standard words. We also present some results about words on larger alphabets having similar properties.
Construction of Minimal Bracketing Covers for Rectangles
Authors: Gnewuch Michael
Published: January 2020

We construct explicit $\delta$-bracketing covers with minimal cardinality for the set system of (anchored) rectangles in the two dimensional unit cube. More precisely, the cardinality of these $\delta$-bracketing covers are bounded from above by $\delta^{-2} + o(\delta^{-2})$. A lower bound for the cardinality of arbitrary $\delta$-bracketing covers for $d$-dimensional anchored boxes from [M. Gnewuch, Bracketing numbers for axis-parallel boxes and applications to geometric discrepancy, J. Complexity 24 (2008) 154-172] implies the lower bound $\delta^{-2}+O(\delta^{-1})$ in dimension $d=2$, showing that our constructed covers are (essentially) optimal. We study also other $\delta$-bracketing covers for the set system of rectangles, deduce the coefficient of the most significant term $\delta^{-2}$ in the asymptotic expansion of their cardinality, and compute their cardinality for explicit values of $\delta$.
R-S Correspondence for $({\Bbb Z}_2 \times {\Bbb Z}_2) \wr S_n$ and Klein-$4$ Diagram Algebras
Authors: Parvathi M. , Sivakumar B.
Published: January 2020

In [PS] a new family of subalgebras of the extended ${\Bbb Z}_2$-vertex colored algebras, called Klein-$4$ diagram algebras, are studied. These algebras are the centralizer algebras of $G_n:=({\Bbb Z}_2 \times {\Bbb Z}_2) \wr S_n$ when it acts on $V^{\otimes k},$ where $V$ is the signed permutation module for $G_n.$ In this paper we give the Robinson-Schensted correspondence for $G_n$ on $4$-partitions of $n,$ which gives a bijective proof of the identity $\sum_{[\lambda] \vdash n } (f^{[\lambda]})^2 = 4^n n!,$ where $f^{[\lambda]}$ is the degree of the corresponding representation indexed by $[\lambda]$ for $G_n.$ We give proof of the identity $2^kn^k = \sum_{[\lambda] \in \Gamma_{n,k}^G} f^{[\lambda]} m_{k}^{[\lambda]}$ where the sum is over $4$-partitions which index the irreducible $G_n$-modules appearing in the decomposition of $V^{\otimes k} $ and $m_{k}^{[\lambda]}$ is the multiplicity of the irreducible $G_n$-module indexed by $[\lambda ].$ Also, we develop an R-S correspondence for the Klein-$4$ diagram algebras by giving a bijection between the diagrams in the basis and pairs of vacillating tableau of same shape.
Notes on Nonrepetitive Graph Colouring
Authors: Barát János , Wood David R.
Published: January 2020

A vertex colouring of a graph is nonrepetitive on paths if there is no path $v_1,v_2,\dots,v_{2t}$ such that $v_i$ and $v_{t+i}$ receive the same colour for all $i=1,2,\dots,t$. We determine the maximum density of a graph that admits a $k$-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a $4$-colouring that is nonrepetitive on paths. The best previous bound was $5$. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree $\Delta$ has a $f(\Delta)$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth $k$ and maximum degree $\Delta$ has a $O(k\Delta)$-colouring that is nonrepetitive on paths, and a $O(k\Delta^3)$-colouring that is nonrepetitive on walks.A corrigendum was added to this paper on Dec 12, 2014.
On the Number of Matchings in Regular Graphs
Authors: Friedland S. , Krop E. , Markström K.
Published: January 2020

For the set of graphs with a given degree sequence, consisting of any number of $2's$ and $1's$, and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of $m$-matchings. We find the expected value of the number of $m$-matchings of $r$-regular bipartite graphs on $2n$ vertices with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for $m$-matchings in $r$-regular bipartite graphs on $2n$ vertices, and their asymptotic versions for infinite $r$-regular bipartite graphs. We prove these conjectures for $2$-regular bipartite graphs and for $m$-matchings with $m\le 4$.
Saturation Numbers of Books
Authors: Chen Guantao , Faudree Ralph J. , Gould Ronald J.
Published: January 2020

A book $B_p$ is a union of $p$ triangles sharing one edge. This idea was extended to a generalized book $B_{b,p}$, which is the union of $p$ copies of a $K_{b+1}$ sharing a common $K_b$. A graph $G$ is called an $H$-saturated graph if $G$ does not contain $H$ as a subgraph, but $G\cup \{xy\}$ contains a copy of $H$, for any two nonadjacent vertices $x$ and $y$. The saturation number of $H$, denoted by $sat(H,n)$, is the minimum number of edges in $G$ for all $H$-saturated graphs $G$ of order $n$. We show that $$ sat(B_p, n) = {1\over2} \big( (p+1)(n-1) - \big\lceil {p\over2}\big\rceil \big\lfloor {p\over2} \big\rfloor + \theta(n,p)\big), $$ where $\theta(n, p) = \begin{cases} 1& \text{ if } p\equiv n -p/2 \equiv 0 \bmod 2 \\ 0& \text{ otherwise}\end{cases}$, provided $n \ge p^3 + p$. Moreover, we show that $$\eqalign{ sat(B_{b,p}, n) = \ & {1\over2} \big( (p+2b-3)(n-b+1) - \big\lceil {p\over2}\big\rceil \big\lfloor {p\over2} \big\rfloor\cr &+ \theta(n,p, b)+(b-1)(b-2) \big),\cr} $$ where $\theta(n, p, b) = \begin{cases} 1& \text{ if } p \equiv n -p/2 -b \equiv 0 \bmod 2 \\ 0 & \text{ otherwise} \end{cases}$, provided $n \ge 4(p+2b)^{b}$.
Graphs with Given Degree Sequence and Maximal Spectral Radius
Authors: Bıyıkoğlu Türker , Leydold Josef
Published: January 2020

We describe the structure of those graphs that have largest spectral radius in the class of all connected graphs with a given degree sequence. We show that in such a graph the degree sequence is non-increasing with respect to an ordering of the vertices induced by breadth-first search. For trees the resulting structure is uniquely determined up to isomorphism. We also show that the largest spectral radius in such classes of trees is strictly monotone with respect to majorization.
Global Alliances and Independent Domination in Some Classes of Graphs
Authors: Favaron Odile
Published: January 2020

A dominating set $S$ of a graph $G$ is a global (strong) defensive alliance if for every vertex $v\in S$, the number of neighbors $v$ has in $S$ plus one is at least (greater than) the number of neighbors it has in $V\setminus S$. The dominating set $S$ is a global (strong) offensive alliance if for every vertex $v\in V\setminus S$, the number of neighbors $v$ has in $S$ is at least (greater than) the number of neighbors it has in $V\setminus S$ plus one. The minimum cardinality of a global defensive (strong defensive, offensive, strong offensive) alliance is denoted by $\gamma_a(G)$ ($\gamma_{\hat a}(G)$, $\gamma_o(G)$, $\gamma_{\hat o}(G))$. We compare each of the four parameters $\gamma_a, \gamma_{\hat a}, \gamma_o, \gamma_{\hat o}$ to the independent domination number $i$. We show that $i(G)\le \gamma ^2_a(G)-\gamma_a(G)+1$ and $i(G)\le \gamma_{\hat{a}}^2(G)-2\gamma_{\hat{a}}(G)+2$ for every graph; $i(G)\le \gamma ^2_a(G)/4 +\gamma_a(G)$ and $i(G)\le \gamma_{\hat{a}}^2(G)/4 +\gamma_{\hat{a}}(G)/2$ for every bipartite graph; $i(G)\le 2\gamma_a(G)-1$ and $i(G)=3\gamma_{\hat{a}}(G)/2 -1$ for every tree and describe the extremal graphs; and that $\gamma_o(T)\le 2i(T)-1$ and $i(T)\le \gamma_{\hat o}(T)-1$ for every tree. We use a lemma stating that $\beta(T)+2i(T)\ge n+1$ in every tree $T$ of order $n$ and independence number $\beta(T)$.
Star Coloring High Girth Planar Graphs
Authors: Timmons Craig
Published: January 2020

A star coloring of a graph is a proper coloring such that no path on four vertices is 2-colored. We prove that every planar graph with girth at least 9 can be star colored using 5 colors, and that every planar graph with girth at least 14 can be star colored using 4 colors; the figure 4 is best possible. We give an example of a girth 7 planar graph that requires 5 colors to star color.
Generalizations of Partial Difference Sets from Cyclotomy to Nonelementary Abelian $p$-Groups
Authors: Polhill John
Published: January 2020

A partial difference set having parameters $(n^2, r(n-1), n+r^2-3r,r^2-r)$ is called a Latin square type partial difference set, while a partial difference set having parameters $(n^2, r(n+1), -n+r^2+3r,r^2+r)$ is called a negative Latin square type partial difference set. In this paper, we generalize well-known negative Latin square type partial difference sets derived from the theory of cyclotomy. We use the partial difference sets in elementary abelian groups to generate analogous partial difference sets in nonelementary abelian groups of the form $(Z_p)^{4s} \times (Z_{p^s})^4$. It is believed that this is the first construction of negative Latin square type partial difference sets in nonelementary abelian $p$-groups where the $p$ can be any prime number. We also give a generalization of subsets of Type Q, partial difference sets consisting of one fourth of the nonidentity elements from the group, to nonelementary abelian groups. Finally, we give a similar product construction of negative Latin square type partial difference sets in the additive groups of $(F_q)^{4t+2}$ for an integer $t \geq 1$. This construction results in some new parameters of strongly regular graphs.
Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs
Authors: Kiwi Marcos , Loebl Martin
Published: January 2020

We address the following question: When a randomly chosen regular bipartite multi–graph is drawn in the plane in the "standard way", what is the distribution of its maximum size planar matching (set of non–crossing disjoint edges) and maximum size planar subgraph (set of non–crossing edges which may share endpoints)? The problem is a generalization of the Longest Increasing Sequence (LIS) problem (also called Ulam's problem). We present combinatorial identities which relate the number of $r$-regular bipartite multi–graphs with maximum planar matching (maximum planar subgraph) of at most $d$ edges to a signed sum of restricted lattice walks in ${\Bbb Z}^d$, and to the number of pairs of standard Young tableaux of the same shape and with a "descend–type" property. Our results are derived via generalizations of two combinatorial proofs through which Gessel's identity can be obtained (an identity that is crucial in the derivation of a bivariate generating function associated to the distribution of the length of LISs, and key to the analytic attack on Ulam's problem). Finally, we generalize Gessel's identity. This enables us to count, for small values of $d$ and $r$, the number of $r$-regular bipartite multi-graphs on $n$ nodes per color class with maximum planar matchings of size $d$.Our work can also be viewed as a first step in the study of pattern avoidance in ordered bipartite multi-graphs.
Regularisation and the Mullineux Map
Authors: Fayers Matthew
Published: January 2020

We classify the pairs of conjugate partitions whose regularisations are images of each other under the Mullineux map. This classification proves a conjecture of Lyle, answering a question of Bessenrodt, Olsson and Xu.
On the First Eigenvalue of Bipartite Graphs
Authors: Bhattacharya Amitava , Friedland Shmuel , Peled Uri N.
Published: January 2020

In this paper we study the maximum value of the largest eigenvalue for simple bipartite graphs, where the number of edges is given and the number of vertices on each side of the bipartition is given. We state a conjectured solution, which is an analog of the Brualdi-Hoffman conjecture for general graphs, and prove the conjecture in some special cases.
Intersecting and Cross-Intersecting Families of Labeled Sets
Authors: Borg Peter
Published: January 2020

A family ${\cal A}$ of sets is said to be intersecting if any two sets in ${\cal A}$ intersect. Families ${\cal A}_1, ..., {\cal A}_p$ are said to be cross-intersecting if, for any $i, j \in \{1, ..., p\}$ such that $i \neq j$, any set in ${\cal A}_i$ intersects any set in ${\cal A}_j$. For ${\bf k} = (k_1, ..., k_n) \in {\Bbb N}^n$, $2 \leq k_1 \leq ... \leq k_n$, let ${\cal L}_{\bf{k}}$ be the family of labeled $n$-sets given by ${\cal L}_{\bf{k}} := \{\{(1,l_1), ..., (n,l_n)\} \colon l_i \in \{1, ..., k_i\}, i = 1, ..., n\}$. We point out a relationship between intersecting families and cross-intersecting families of labeled sets, and we show that, if ${\cal A}_1, ..., {\cal A}_p$ are cross-intersecting sub-families of ${\cal L}_{\bf{k}}$, then $$ \sum_{j = 1}^p |{\cal A}_j| \leq \left\{ \matrix{ k_1k_2...k_n & \hbox{if $p \leq k_1$};\cr pk_2...k_n & \hbox{if $p \geq k_1$}.\cr } \right. $$ We also determine the cases of equality. We then obtain a more general inequality, a special case of which is a sharp bound for cross-intersecting families of permutations.
A Note on the Component Structure in Random Intersection Graphs with Tunable Clustering
Authors: Lagerås Andreas N. , Lindholm Mathias
Published: January 2020

We study the component structure in random intersection graphs with tunable clustering, and show that the average degree works as a threshold for a phase transition for the size of the largest component. That is, if the expected degree is less than one, the size of the largest component is a.a.s. of logarithmic order, but if the average degree is greater than one, a.a.s. a single large component of linear order emerges, and the size of the second largest component is at most of logarithmic order.
The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence
Authors: Alon Noga , Friedland Shmuel
Published: January 2020

We show that the number of perfect matchings in a simple graph $G$ with an even number of vertices and degree sequence $d_1,d_2, \ldots ,d_n$ is at most $ \prod_{i=1}^n (d_i!)^{{1\over 2d_i}}$. This bound is sharp if and only if $G$ is a union of complete balanced bipartite graphs.
Induced Paths in Twin-Free Graphs
Authors: Auger David
Published: January 2020

Let $G=(V,E)$ be a simple, undirected graph. Given an integer $r \geq 1$, we say that $G$ is $r$-twin-free (or $r$-identifiable) if the balls $B(v,r)$ for $v \in V$ are all different, where $B(v,r)$ denotes the set of all vertices which can be linked to $v$ by a path with at most $r$ edges. These graphs are precisely the ones which admit $r$-identifying codes. We show that if a graph $G$ is $r$-twin-free, then it contains a path on $2r+1$ vertices as an induced subgraph, i.e. a chordless path.
A Note on Palindromic $\delta$-Vectors for Certain Rational Polytopes
Authors: Fiset Matthew H. J. , Kasprzyk Alexander M.
Published: January 2020

Let $P$ be a convex polytope containing the origin, whose dual is a lattice polytope. Hibi's Palindromic Theorem tells us that if $P$ is also a lattice polytope then the Ehrhart $\delta$-vector of $P$ is palindromic. Perhaps less well-known is that a similar result holds when $P$ is rational. We present an elementary lattice-point proof of this fact.
A Note about Bezdek's Conjecture on Covering an Annulus by Strips
Authors: Zhang Yuqin , Ding Ren
Published: January 2020

A closed plane region between two parallel lines is called a strip. András Bezdek posed the following conjecture: For each convex region $K$ there is an $\varepsilon>0$ such that if $\varepsilon K$ lies in the interior of $K$ and the annulus $K\backslash \varepsilon K$ is covered by finitely many strips, then the sum of the widths of the strips must be at least the minimal width of $K$. In this paper, we consider problems which are related to the conjecture.
Generalized Descents and Normality
Authors: Bóna Miklós
Published: January 2020

We use Janson's dependency criterion to prove that the distribution of $d$-descents of permutations of length $n$ converge to a normal distribution as $n$ goes to infinity. We show that this remains true even if $d$ is allowed to grow with $n$.
Rainbow $H$-Factors of Complete $s$-Uniform $r$-Partite Hypergraphs
Authors: Chen Ailian , Zhang Fuji , Li Hao
Published: January 2020

We say a $s$-uniform $r$-partite hypergraph is complete, if it has a vertex partition $\{V_1,V_2,...,V_r\}$ of $r$ classes and its hyperedge set consists of all the $s$-subsets of its vertex set which have at most one vertex in each vertex class. We denote the complete $s$-uniform $r$-partite hypergraph with $k$ vertices in each vertex class by ${\cal T}_{s,r}(k)$. In this paper we prove that if $h,\ r$ and $s$ are positive integers with $2\leq s\leq r\leq h$ then there exists a constant $k=k(h,r,s)$ so that if $H$ is an $s$-uniform hypergraph with $h$ vertices and chromatic number $\chi(H)=r$ then any proper edge coloring of ${\cal T}_{s,r}(k)$ has a rainbow $H$-factor.
Uniquely Hamiltonian Characterizations of Distance-Hereditary and Parity Graphs
Authors: McKee Terry A.
Published: January 2020

A graph is shown to be distance-hereditary if and only if no induced subgraph of order five or more has a unique hamiltonian cycle; this is also equivalent to every induced subgraph of order five or more having an even number of hamiltonian cycles. Restricting the induced subgraphs to those of odd order five or more gives two similar characterizations of parity graphs. The close relationship between distance-hereditary and parity graphs is unsurprising, but their connection with hamiltonian cycles of induced subgraphs is unexpected.
On the Non-Existence of Certain Hyperovals in Dual André Planes of Order $2^{2h}$
Authors: Aguglia Angela , Giuzzi Luca
Published: January 2020

No regular hyperoval of the Desarguesian affine plane $AG(2,2^{2h})$, with $h>1$, is inherited by a dual André plane of order $2^{2h}$ and dimension $2$ over its kernel.
Graphs of Morphisms of Graphs
Authors: Brown R. , Morris I. , Shrimpton J. , Wensley C. D.
Published: January 2020

This is an account for the combinatorially minded reader of various categories of directed and undirected graphs, and their analogies with the category of sets. As an application, the endomorphisms of a graph are in this context not only composable, giving a monoid structure, but also have a notion of adjacency, so that the set of endomorphisms is both a monoid and a graph. We extend Shrimpton's (unpublished) investigations on the morphism digraphs of reflexive digraphs to the undirected case by using an equivalence between a category of reflexive, undirected graphs and the category of reflexive, directed graphs with reversal. In so doing, we emphasise a picture of the elements of an undirected graph, as involving two types of edges with a single vertex, namely 'bands' and 'loops'. Such edges are distinguished by the behaviour of morphisms with respect to these elements.
Lower Bounds for the Size of Random Maximal $H$-Free Graphs
Authors: Wolfovitz Guy
Published: January 2020

We consider the next random process for generating a maximal $H$-free graph: Given a fixed graph $H$ and an integer $n$, start by taking a uniformly random permutation of the edges of the complete $n$-vertex graph $K_n$. Then, traverse the edges of $K_n$ according to the order imposed by the permutation and add each traversed edge to an (initially empty) evolving $n$-vertex graph - unless its addition creates a copy of $H$. The result of this process is a maximal $H$-free graph ${\Bbb M}_n(H)$. Our main result is a new lower bound on the expected number of edges in ${\Bbb M}_n(H)$, for $H$ that is regular, strictly $2$-balanced. As a corollary, we obtain new lower bounds for Turán numbers of complete, balanced bipartite graphs. Namely, for fixed $r \ge 5$, we show that ex$(n, K_{r,r}) = \Omega(n^{2-2/(r+1)}(\ln\ln n)^{1/(r^2-1)})$. This improves an old lower bound of Erdős and Spencer. Our result relies on giving a non-trivial lower bound on the probability that a given edge is included in ${\Bbb M}_n(H)$, conditioned on the event that the edge is traversed relatively (but not trivially) early during the process.
Component Evolution in Random Intersection Graphs
Authors: Behrisch Michael
Published: January 2020

We study the evolution of the order of the largest component in the random intersection graph model which reflects some clustering properties of real–world networks. We show that for appropriate choice of the parameters random intersection graphs differ from $G_{n,p}$ in that neither the so-called giant component, appearing when the expected vertex degree gets larger than one, has linear order nor is the second largest of logarithmic order. We also describe a test of our result on a protein similarity network.
Truncations of Random Unitary Matrices and Young Tableaux
Authors: Novak J.
Published: January 2020

Let $U$ be a matrix chosen randomly, with respect to Haar measure, from the unitary group $U(d).$ For any $k \leq d,$ and any $k \times k$ submatrix $U_k$ of $U,$ we express the average value of $|{\rm Tr}(U_k)|^{2n}$ as a sum over partitions of $n$ with at most $k$ rows whose terms count certain standard and semistandard Young tableaux. We combine our formula with a variant of the Colour-Flavour Transformation of lattice gauge theory to give a combinatorial expansion of an interesting family of unitary matrix integrals. In addition, we give a simple combinatorial derivation of the moments of a single entry of a random unitary matrix, and hence deduce that the rescaled entries converge in moments to standard complex Gaussians. Our main tool is the Weingarten function for the unitary group.
Distance Domination and Distance Irredundance in Graphs
Authors: Hansberg Adriana , Meierling Dirk , Volkmann Lutz
Published: January 2020

A set $D\subseteq V$ of vertices is said to be a (connected) distance $k$-dominating set of $G$ if the distance between each vertex $u\in V-D$ and $D$ is at most $k$ (and $D$ induces a connected graph in $G$). The minimum cardinality of a (connected) distance $k$-dominating set in $G$ is the (connected) distance $k$-domination number of $G$, denoted by $\gamma_k(G)$ ($\gamma_k^c(G)$, respectively). The set $D$ is defined to be a total $k$-dominating set of $G$ if every vertex in $V$ is within distance $k$ from some vertex of $D$ other than itself. The minimum cardinality among all total $k$-dominating sets of $G$ is called the total $k$-domination number of $G$ and is denoted by $\gamma_k^t(G)$. For $x\in X\subseteq V$, if $N^k[x]-N^k[X-x]\neq\emptyset$, the vertex $x$ is said to be $k$-irredundant in $X$. A set $X$ containing only $k$-irredundant vertices is called $k$-irredundant. The $k$-irredundance number of $G$, denoted by $ir_k(G)$, is the minimum cardinality taken over all maximal $k$-irredundant sets of vertices of $G$. In this paper we establish lower bounds for the distance $k$-irredundance number of graphs and trees. More precisely, we prove that ${5k+1\over 2}ir_k(G)\geq \gamma_k^c(G)+2k$ for each connected graph $G$ and $(2k+1)ir_k(T)\geq\gamma_k^c(T)+2k\geq |V|+2k-kn_1(T)$ for each tree $T=(V,E)$ with $n_1(T)$ leaves. A class of examples shows that the latter bound is sharp. The second inequality generalizes a result of Meierling and Volkmann and Cyman, Lemańska and Raczek regarding $\gamma_k$ and the first generalizes a result of Favaron and Kratsch regarding $ir_1$. Furthermore, we shall show that $\gamma_k^c(G)\leq{3k+1\over2}\gamma_k^t(G)-2k$ for each connected graph $G$, thereby generalizing a result of Favaron and Kratsch regarding $k=1$.
A Combinatorial Representation with Schröder Paths of Biorthogonality of Laurent Biorthogonal Polynomials
Authors: Kamioka Shuhei
Published: January 2020

Combinatorial representation in terms of Schröder paths and other weighted plane paths are given of Laurent biorthogonal polynomials (LBPs) and a linear functional with which LBPs have orthogonality and biorthogonality. Particularly, it is clarified that quantities to which LBPs are mapped by the corresponding linear functional can be evaluated by enumerating certain kinds of Schröder paths, which imply orthogonality and biorthogonality of LBPs.
Repetition Number of Graphs
Authors: Caro Yair , West Douglas B.
Published: January 2020

Every $n$-vertex graph has two vertices with the same degree (if $n\ge2$). In general, let rep$(G)$ be the maximum multiplicity of a vertex degree in $G$. An easy counting argument yields rep$(G)\ge n/(2d-2s+1)$, where $d$ is the average degree and $s$ is the minimum degree of $G$. Equality can hold when $2d$ is an integer, and the bound is approximately sharp in general, even when $G$ is restricted to be a tree, maximal outerplanar graph, planar triangulation, or claw-free graph. Among large claw-free graphs, repetition number $2$ is achievable, but if $G$ is an $n$-vertex line graph, then rep$(G)\ge{1\over4}n^{1/3}$. Among line graphs of trees, the minimum repetition number is $\Theta(n^{1/2})$. For line graphs of maximal outerplanar graphs, trees with perfect matchings, or triangulations with 2-factors, the lower bound is linear.
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.
Enumeration and Asymptotic Properties of Unlabeled Outerplanar Graphs
Authors: Bodirsky Manuel , Fusy Éric , Kang Mihyun , Vigerske Stefan
Published: January 2020

We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number $g_{n}$ of unlabeled outerplanar graphs on $n$ vertices can be computed in polynomial time, and $g_{n}$ is asymptotically $g\, n^{-5/2}\rho^{-n}$, where $g\approx0.00909941$ and $\rho^{-1}\approx7.50360$ can be approximated. Using our enumerative results we investigate several statistical properties of random unlabeled outerplanar graphs on $n$ vertices, for instance concerning connectedness, the chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics.
Maximum Cardinality 1-Restricted Simple 2-Matchings
Authors: Hartvigsen David
Published: January 2020

A simple 2-matching in a graph is a subgraph all of whose nodes have degree $1$ or $2$. A simple 2-matching is called $k$-restricted if every connected component has $>k$ edges. We consider the problem of finding a $k$-restricted simple 2-matching with a maximum number of edges, which is a relaxation of the problem of finding a Hamilton cycle in a graph. Our main result is a min-max theorem for the maximum number of edges in a 1-restricted simple 2-matching. We prove this result constructively by presenting a polynomial time algorithm for finding a 1-restricted simple 2-matching with a maximum number of edges.
On the Quantum Chromatic Number of a Graph
Authors: Cameron Peter J. , Montanaro Ashley , Newman Michael W. , Severini Simone , Winter Andreas
Published: January 2020

We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince a referee that they have a colouring of the graph.After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is $2$, nor if it is $3$ in a restricted quantum model; on the other hand, we exhibit a graph on $18$ vertices and $44$ edges with chromatic number $5$ and quantum chromatic number $4$.
Evidence and Bias: The Case of the Evidential Future in Italian
Authors: Frana Ilaria , Menéndez-Benito Paula
Published: January 2020

Evidential markers encode the source of information that an individual (the evidential Origo) has for a proposition. In root declaratives, the Origo is always the speaker (see Korotkova 2016 and references therein). Instead, questions often display interrogative flip: the Origo shifts to the hearer (Garrett 2001; Speas & Tenny 2003, a.o.). While interrogative flip is widely attested across languages, some evidentials have been reported not to flip in questions (see, e.g., San Roque, Floyd & Norcliffe 2017; Bhadra 2017). What determines whether evidentials flip or not? Recent work (Korotkova 2016; Bhadra 2017) has proposed that there is a correlation between lack of flip and bias in questions. This paper contributes to our understanding of the interaction of evidentials and bias by investigating the behaviour of questions with the Italian non-predictive future. We characterize the non-predictive future as an inferential evidential marker (see also Mari 2009; Eckardt & Beltrama forthcoming), and show that lack of flip for the future correlates only with a particular type of bias: a reversal of the default bias associated with negative polar questions (Frana & Rawlins forthcoming). We trace back this pattern to an interaction between the evidential component of the future and the operator that triggers bias reversal.
Comparison of Cortical Auditory Evoked Potential Findings in Presbycusis with Low and High Word-Recognition Score
Authors: G¨urkan Selhan , Durankaya Serpil M. , Mutlu Basak , ˙Isler Yalc¸ın , Uzun Yig˘it  O¨. , Basokc¸u O˘guz , Erda˘ Taner K. , Kırkım G¨unay
Published: January 2020

Background: Deteriorated speech understanding is a common complaint in elderly people, and behavioraltests are used for routine clinical assessment of this problem. Cortical auditory evoked potentials(CAEPs) are frequently used for assessing speech detection and discrimination abilities of the elderly,and give promise for differential diagnosis of speech-understanding problems.
Purpose: The aim of the study was to compare the P1, N1, and P2 CAEP latencies and amplitudes inpresbycusis with low and high word recognition score (WRS).
Research Design: A cross-sectional study design was used for the study. Two groups were formed fromthe patients with presbycusis based on their scores on the speech-recognition test.
Study Sample: Fifty-seven elderly volunteers participated in the study. The first group composed of 27participants with high WRS, the other group composed of 30 participants with low WRS.
Data Collection and Analysis: The CAEP waves were recorded from these participants using speech signals.Latencies and amplitudes of P1-N1-P2 waves of the two groups were compared with the t-test statistic.
Results: There were significant prolongation of P1 and N1 latencies in presbycusis with low WRS whencompared with presbycusis with a relatively high word score (p < 0.05).
Conclusion: According to the result of the research, P1 and N1 latencies of presbycusis with low WRSwere longer than the participants with high WRS. Factors affecting peripheral auditory system, such asstimulus sensation level, might be responsible for P1 and N1 latency prolongation of the low WRS group.
Gymnosporangium species on Malus: species delineation, diversity and host alternation
Authors: Zhao P. , Qi X.H. , Crous P.W. , Duan W.J. , Cai L.
Published: January 2020

Gymnosporangium species (Pucciniaceae, Pucciniales, Basidiomycota) are the causal agents of cedarapple rust diseases, which can lead to significant economic losses to apple cultivars. Currently, the genus contains 17 described species that alternate between
spermogonial/aecial stages on Malus species and telial stages on Juniperus or Chamaecyparis species, although these have yet to receive a modern systematic treatment. Furthermore, prior studies have shown that Gymnosporangium does not belong to the Pucciniaceae
sensu stricto (s.str.), nor is it allied to any currently defined rust family. In this study we examine the phylogenetic placement of the genus Gymnosporangium. We also delineate interspecific boundaries of the Gymnosporangium species on Malus based on phylogenies inferred
from concatenated data of rDNA SSU, ITS and LSU and the holomorphic morphology of the entire life cycle. Based on these results, we propose a new family, Gymnosporangiaceae, to accommodate the genus Gymnosporangium, and recognize 22 Gymnosporangium species parasitic on
Malus species, of which G. lachrymiforme, G. shennongjiaense, G. spinulosum, G. tiankengense and G. kanas are new. Typification of G. asiaticum, G. fenzelianum, G. juniperi-virginianae, G. libocedri, G. nelsonii,
G. nidus-avis and G. yamadae are proposed to stabilize the use of names. Morphological and molecular data from type materials of 14 Gymnosporangium species are provided. Finally, morphological characteristics, host alternation and geographical distribution data are provided
for each Gymnosporangium species on Malus.
Soutenir la parentalité, une entreprise non dénuée d’ambiguïté
Authors: Neyrand Gérard
Published: January 2020

Le texte rappelle le contexte de la montée du soutien de la parentalité, parti de la société civile, et auquel les institutions et l’État vont progressivement s’intéresser, en tentant de le formaliser. Cela dans une perspective assez contradictoire, puisque renvoyant à des présupposés multiples et pas forcément homogènes, sociaux, éducatifs, politiques, managériaux… alors même que l’idée de parentalité a essayé de rendre compte du basculement fondamental de l’ordre familial à partir des années 1970.
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.
Topiques institutionnelles, écoute groupale de la famille… et fonction centripète des cadres
Authors: Aubertel Françoise
Published: January 2020

Travailler avec les familles en institution suppose la prise en compte des différents niveaux d’une rencontre de groupe à groupe. Du fait des processus d’externalisation de familles déstabilisées, les cadres et les topiques institutionnelles deviennent des réceptacles de contenus archaïques familiaux, éventuellement combinés avec ceux de l’institution. L’élaboration de ces contenus passe notamment par leur réorientation vers les cadres adéquats, pourvu que ceux-ci soient suffisamment différenciés pour activer un mouvement centripète identifiable par les équipes. Ce travail d’élaboration par les professionnels suppose qu’ils puissent préserver leur position clinique, dans un co-étayage sur leurs collègues et sur leur institution, et qu’ils bénéficient d’espaces de retraitement où déposer des éprouvés complexes en instance de mentalisation.
Dispositif interculturel de soutien à la parentalité
Authors: Kadi Saduman
Published: January 2020

Depuis quelques années, j’accompagne des familles issues de l’immigration turque à penser leur rapport à leur parentalité. En s’adressant à moi, elles recherchent quelqu’un avec qui elles ont la possibilité de s’exprimer dans leur langue maternelle. L’évolution de ma clinique psychosociale et interculturelle m’aura fait comprendre qu’en fait la langue sert de parapluie à un processus bien plus complexe à l’œuvre dans le rapport à soi, à l’autre et aux institutions. Ces accompagnements m’ont amenée à ouvrir un espace clinique groupal où chacun peut déposer son vécu dans ses différentes inscriptions sociales et culturelles. La communauté turque a la spécificité qui lui est reconnue de vivre dans un entre-soi. Il fallait alors à ces familles trouver « le professionnel » qui serait issu du « même » et qui saurait traiter les questions liées à leur manière d’être parent en France. La dialectique du « même » et du « différent » prendra une place importante dans le dispositif comme rendant compte d’un profond clivage dans l’intériorisation des figures d’attachement et sa réactualisation dans son rapport à la parentalité et à ses liens institutionnels.
Les langages de l’appartenance. Miliciens de couleur et changements de souveraineté dans les îles du Vent (1763-1803)
Authors: Bonnefoy Baptiste
Published: January 2020

Depuis une vingtaine d’années, l’historiographie a démontré la pluralité des contextes normatifs et juridiques au sein des empires modernes. Cet article vise à montrer que ces variations locales concernent également les pratiques classificatoires et les langages d’appartenance des acteurs. Entre 1763 et 1803, plusieurs îles des Antilles connaissent des changements répétés de souveraineté. Tantôt françaises, tantôt britanniques, les petites îles de Sainte Lucie, de la Grenade et de la Dominique subissent de lourdes recompositions sociales et démographiques. Ces trois mondes mêlés, distincts mais connectés, traversés par deux empires, sont intégrés à un espace régional caraïbe structuré par des circulations trans-impériales denses. L’étude des miliciens de couleur permet d’examiner, dans chacun de ces contextes, l’articulation de divers mécanismes de la domination sociale : la richesse, la couleur, la sujétion, mais aussi la langue et la religion. Cet article montre ainsi que l’enchevêtrement de différentes grammaires impériales dans ces espaces renforce la capacité des acteurs à négocier localement leurs appartenances sociales, y compris la couleur
Pour un retour aux manuscrits de l’Arioste
Authors: Albonico Simone
Published: January 2020

Santorre Debenedetti publia en 1937 ce que l’on nomme les « fragments autographes » du Roland furieux, qui documentent l’élaboration des octaves ajoutées par Ludovico Ariosto à la troisième édition de son chef d’œuvre (1532). Dans sa recension opportune de l’édition Debenedetti, le jeune Gianfranco Contini livra une interprétation des variantes de l’Arioste qui lui permettait de valider le jugement critique de Benedetto Croce, ce dernier discernant dans le Roland furieux la mise en œuvre d’un principe d’harmonie. Pour parvenir à cette conclusion, Contini ne prit en considération qu’une portion restreinte de l’élaboration textuelle du poème qui rentrait dans le champ de l’esthétique crocienne. Il manifesta par ailleurs son adhésion à d’autres postulats du philosophe napolitain, désormais remis en question depuis de longues années. La naissance de la « critique des variantes » d’inspiration continienne, fondée sur ces présupposés, a reçu au fil du temps un accueil plus ou moins favorable, mais elle n’a jamais fait l’objet d’une analyse historico-critique destinée à en vérifier le bien-fondé philologique et interprétatif. Le présent article entend amorcer une réflexion en ce sens.
Genèses littéraires dans la correspondance de Pietro et Alessandro Verri
Authors: Musitelli Pierre
Published: January 2020

La correspondance des frères Verri permet de suivre pendant trente ans (1766-1797) l’élaboration des principales œuvres économiques et philosophiques de Pietro et le mûrissement des goûts littéraires d’Alessandro au gré de multiples expérimentations de styles et de genres. Le premier vit à Milan, le second réside à Rome : tous deux développent, à travers leur correspondance hebdomadaire, une pratique collaborative de l’écriture. Brouillons et manuscrits transitent par voie postale pour être discutés et annotés, le texte prenant forme au fil de ces échanges. Mais l’écriture épistolaire des frères Verri n’a pas, en matière de genèse littéraire, qu’une fonction productrice : les jugements exprimés ne témoignent pas toujours d’une capacité de l’interlocuteur à saisir et déchiffrer l’œuvre et ses enjeux. Avec le temps, s’usent l’amitié fraternelle et ses promesses initiales (stimuler l’autre, être son censeur impartial), à mesure que deux styles s’affirment et que se creuse le clivage idéologique dans les années de la Révolution.