bluuebunny/crossref_metadata_2025 huggingface dataset:
Some Spectral Properties of Uniform Hypergraphs
Authors: Zhou Jiang , Sun Lizhu , Wang Wenzhe , Bu Changjiang
Published: January 2020

For a $k$-uniform hypergraph $H$, we obtain some trace formulas for the Laplacian tensor of $H$, which imply that $\sum_{i=1}^nd_i^s$ ($s=1,\ldots,k$) is determined by the Laplacian spectrum of $H$, where $d_1,\ldots,d_n$ is the degree sequence of $H$. Using trace formulas for the Laplacian tensor, we obtain expressions for some coefficients of the Laplacian polynomial of a regular hypergraph. We give some spectral characterizations of odd-bipartite hypergraphs, and give a partial answer to a question posed by Shao et al (2014). We also give some spectral properties of power hypergraphs, and show that a conjecture posed by Hu et al (2013) holds under certain conditons.
Vertically Symmetric Alternating Sign Matrices and a Multivariate Laurent Polynomial Identity
Authors: Fischer Ilse , Riegler Lukas
Published: January 2020

In 2007, the first author gave an alternative proof of the refined alternating sign matrix theorem by introducing a linear equation system that determines the refined ASM numbers uniquely. Computer experiments suggest that the numbers appearing in a conjecture concerning the number of vertically symmetric alternating sign matrices with respect to the position of the first 1 in the second row of the matrix establish the solution of a linear equation system similar to the one for the ordinary refined ASM numbers. In this paper we show how our attempt to prove this fact naturally leads to a more general conjectural multivariate Laurent polynomial identity. Remarkably, in contrast to the ordinary refined ASM numbers, we need to extend the combinatorial interpretation of the numbers to parameters which are not contained in the combinatorial admissible domain. Some partial results towards proving the conjectured multivariate Laurent polynomial identity and additional motivation why to study it are presented as well.
Ascent Sequences Avoiding Pairs of Patterns
Authors: Baxter Andrew M. , Pudwell Lara K.
Published: January 2020

Ascent sequences were introduced by Bousquet-Melou et al. in connection with (2+2)-avoiding posets and their pattern avoidance properties were first considered by Duncan and Steingrímsson. In this paper, we consider ascent sequences of length $n$ avoiding two patterns of length 3, and we determine an exact enumeration for 16 different pairs of patterns. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erdős-Szekeres Theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.
A Paintability Version of the Combinatorial Nullstellensatz, and List Colorings of $k$-partite $k$-uniform Hypergraphs
Authors: Schauz Uwe
Published: January 2020

We study the list coloring number of $k$-uniform $k$-partite hypergraphs. Answering a question of Ramamurthi and West, we present a new upper bound which generalizes Alon and Tarsi's bound for bipartite graphs, the case $k=2$. Our results hold even for paintability (on" line list colorability). To prove this additional strengthening, we provide a new subject"=specific version of the Combinatorial Nullstellensatz.
Faces of Birkhoff Polytopes
Authors: Paffenholz Andreas
Published: January 2020

The Birkhoff polytope $B_n$ is the convex hull of all $(n\times n)$ permutation matrices, i.e., matrices where precisely one entry in each row and column is one, and zeros at all other places. This is a widely studied polytope with various applications throughout mathematics.In this paper we study combinatorial types $\mathcal L$ of faces of a Birkhoff polytope. The Birkhoff dimension $\mathrm{bd}(\mathcal L)$ of $\mathcal L$ is the smallest $n$ such that $B_n$ has a face with combinatorial type $\mathcal L$.By a result of Billera and Sarangarajan, a combinatorial type $\mathcal L$ of a $d$-dimensional face  appears in some $\mathcal B_k$ for $k\le 2d$, so $\mathrm{bd}(\mathcal L)\le 2d$. We will characterize those types with $\mathrm{bd}(\mathcal L)\ge 2d-3$, and we prove that any type with $\mathrm{bd}(\mathcal L)\ge d$ is either a product or a wedge over some lower dimensional face. Further, we computationally classify all $d$-dimensional combinatorial types for $2\le d\le 8$.
Linear Relations for a Generalized Tutte Polynomial
Authors: Gordon Gary
Published: January 2020

Brylawski proved the coefficients of the Tutte polynomial of a matroid satisfy a set of linear relations. We extend these relations to a generalization of the Tutte polynomial that includes greedoids and antimatroids. This leads to families of new identities for antimatroids, including trees, posets, chordal graphs and finite point sets in $\mathbb{R}^n$. It also gives a "new" linear relation for matroids that is implied by Brylawski's identities.
On Multiplicative Magic Squares
Authors: Cilleruelo Javier , Luca Florian
Published: January 2020

In this note, we give a lower bound for the distance between the maximal and minimal element in a multiplicative magic square of dimension $r$ whose entries are distinct positive integers.
Another Characterisation of Planar Graphs
Authors: Little C. H. C. , Sanjith G.
Published: January 2020

A new characterisation of planar graphs is presented. It concerns the structure of the cocycle space of a graph, and is motivated by consideration of the dual of an elementary property enjoyed by sets of circuits in any graph.
On the Strength of Connectedness of a Random Hypergraph
Authors: Poole Daniel
Published: January 2020

Bollobás and Thomason (1985) proved that for each $k=k(n) \in [1, n-1]$, with high probability, the random graph process, where edges are added to vertex set $V=[n]$ uniformly at random one after another, is such that the stopping time of having minimal degree $k$ is equal to the stopping time of becoming $k$-(vertex-)connected. We extend this result to the $d$-uniform random hypergraph process, where $k$ and $d$ are fixed. Consequently, for $m=\frac{n}{d}(\ln n +(k-1)\ln \ln n +c)$ and $p=(d-1)! \frac{\ln n + (k-1) \ln \ln n +c}{n^{d-1}}$, the probability that the random hypergraph models $H_d(n, m)$ and $H_d(n, p)$ are $k$-connected tends to $e^{-e^{-c}/(k-1)!}.$
Keeping Avoider's Graph Almost Acyclic
Authors: Clemens Dennis , Ehrenmüller Julia , Person Yury , Tran Tuan
Published: January 2020

We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$. By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non-$k$-colorability game, and the $K_t$-minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojaković, and Szabó. Moreover, we give a slight improvement for the lower bound in the non-planarity game.
Cyclic Sieving Phenomenon in Non-Crossing Connected Graphs
Authors: Guo Alan
Published: January 2020

A non-crossing connected graph is a connected graph on vertices arranged in a circle such that its edges do not cross. The count for such graphs can be made naturally into a q-binomial generating function. We prove that this generating function exhibits the cyclic sieving phenomenon, as conjectured by S.-P. Eu.
Colorful Paths in Vertex Coloring of Graphs
Authors: Akbari Saieed , Liaghat Vahid , Nikzad Afshin
Published: January 2020

A colorful path in a graph $G$ is a path with $\chi(G)$ vertices whose colors are different. A $v$-colorful path is such a path, starting from $v$. Let $G\neq C_7$ be a connected graph with maximum degree $\Delta(G)$. We show that there exists a $(\Delta(G)+1)$-coloring of $G$ with a $v$-colorful path for every $v\in V(G)$. We also prove that this result is true if one replaces $(\Delta(G)+1)$ colors with $2\chi(G)$ colors. If $\chi(G)=\omega(G)$, then the result still holds for $\chi(G)$ colors. For every graph $G$, we show that there exists a $\chi(G)$-coloring of $G$ with a rainbow path of length $\lfloor\chi(G)/2\rfloor$ starting from each $v \in V(G)$.
Distinguishing Maps
Authors: Tucker Thomas W.
Published: January 2020

The distinguishing number of a group $A$ acting faithfully on a set $X$, denoted $D(A,X)$, is the least number of colors needed to color the elements of $X$ so that no nonidentity element of $A$ preserves the coloring. Given a map $M$ (an embedding of a graph in a closed surface) with vertex set $V$ and without loops or multiples edges, let $D(M)=D({\rm Aut}(M),V)$, where ${\rm Aut(M)}$ is the automorphism group of $M$; if $M$ is orientable, define $D^+(M)$ similarly, using only orientation-preserving automorphisms. It is immediate that $D(M)\leq 4$ and $D^+(M)\leq 3$. We use Russell and Sundaram's Motion Lemma to show that there are only finitely many maps $M$ with $D(M)>2$. We show that if a group $A$ of automorphisms of a graph $G$ fixes no edges, then $D(A,V)=2$, with five exceptions. That result is used to find the four maps with $D^+(M)=3$. We also consider the distinguishing chromatic number $\chi_D(M)$, where adjacent vertices get different colors. We show $\chi_D(M)\leq \chi(M)+3$ with equality in only finitely many cases, where $\chi(M)$ is the chromatic number of the graph underlying $M$. We also show that $\chi_D(M)\leq 6$ for planar maps, answering a question of Collins and Trenk. Finally, we discuss the implications for general group actions and give numerous problems for further study.
Hybrid Proofs of the $q$-Binomial Theorem and Other Identities
Authors: Eichhorn Dennis , McLaughlin James , Sills Andrew V.
Published: January 2020

We give "hybrid" proofs of the $q$-binomial theorem and other identities. The proofs are "hybrid" in the sense that we use partition arguments to prove a restricted version of the theorem, and then use analytic methods (in the form of the Identity Theorem) to prove the full version. We prove three somewhat unusual summation formulae, and use these to give hybrid proofs of a number of identities due to Ramanujan. Finally, we use these new summation formulae to give new partition interpretations of the Rogers-Ramanujan identities and the Rogers-Selberg identities.
On Variants of Conway and Conolly's Meta-Fibonacci Recursions
Authors: Isgur Abraham , Rahman Mustazee
Published: January 2020

We study the recursions $A(n) = A(n-a-A^k(n-b)) + A(A^k(n-b))$ where $a \geq 0$, $b \geq 1$ are integers and the superscript $k$ denotes a $k$-fold composition, and also the recursion $C(n) = C(n-s-C(n-1)) + C(n-s-2-C(n-3))$ where $s \geq 0$ is an interger. We prove that under suitable initial conditions the sequences $A(n)$ and $C(n)$ will be defined for all positive integers, and be monotonic with their forward difference sequences consisting only of 0 and 1. We also show that the sequence generated by the recursion for $A(n)$ with parameters $(k,a,b) = (k,0,1)$, and initial conditions $A(1) = A(2) = 1$, satisfies $A(E_n) = E_{n-1}$ where $E_n$ is a generalized Fibonacci recursion defined by $E_n = E_{n-1} + E_{n-k}$ with $E_n = 1$ for $1 \leq n \leq k$.
Two Characterizations of Hypercubes
Authors: Nieminen Juhani , Peltola Matti , Ruotsalainen Pasi
Published: January 2020

Two characterizations of hypercubes are given: 1) A graph is a hypercube if and only if it is antipodal and bipartite $(0,2)$-graph. 2) A graph is an $n$-hypercube if and only if there are $n$ pairs of prime convexes, the graph is a prime convex intersection graph, and each intersection of $n$ prime convexes (no one of which is from the same pair) is a vertex.
Commuting Involution Graphs for $3$-Dimensional Unitary Groups
Authors: Everett Alistaire
Published: January 2020

For a group $G$ and $X$ a subset of $G$ the commuting graph of $G$ on $X$, denoted by $\cal{C}(G,X)$, is the graph whose vertex set is $X$ with $x,y\in X$ joined by an edge if $x\neq y$ and $x$ and $y$ commute. If the elements in $X$ are involutions, then $\cal{C}(G,X)$ is called a commuting involution graph. This paper studies $\cal{C}(G,X)$ when $G$ is a 3-dimensional projective special unitary group and $X$ a $G$-conjugacy class of involutions, determining the diameters and structure of the discs of these graphs.
A Note on the Critical Group of a Line Graph
Authors: Perkinson David , Salter Nick , Xu Tianyuan
Published: January 2020

This note answers a question posed by Levine. The main result shows that under certain circumstances a critical group of a directed graph is the quotient of a critical group of its directed line graph.
Double-Dimer Pairings and Skew Young Diagrams
Authors: Kenyon Richard W. , Wilson David B.
Published: January 2020

We study the number of tilings of skew Young diagrams by ribbon tiles shaped like Dyck paths, in which the tiles are "vertically decreasing". We use these quantities to compute pairing probabilities in the double-dimer model: Given a planar bipartite graph $G$ with special vertices, called nodes, on the outer face, the double-dimer model is formed by the superposition of a uniformly random dimer configuration (perfect matching) of $G$ together with a random dimer configuration of the graph formed from $G$ by deleting the nodes. The double-dimer configuration consists of loops, doubled edges, and chains that start and end at the boundary nodes. We are interested in how the chains connect the nodes. An interesting special case is when the graph is $\varepsilon(\mathbb Z\times\mathbb N)$ and the nodes are at evenly spaced locations on the boundary $\mathbb R$ as the grid spacing $\varepsilon\to0$.
Winning Strong Games through Fast Strategies for Weak Games
Authors: Ferber Asaf , Hefetz Dan
Published: January 2020

We prove that, for sufficiently large $n$, the first player can win the strong perfect matching and Hamilton cycle games. For both games, explicit winning strategies of the first player are given. In devising these strategies we make use of the fact that explicit fast winning strategies are known for the corresponding weak games.
No Dense Subgraphs Appear in the Triangle-free Graph Process
Authors: Gerke Stefanie , Makai Tamás
Published: January 2020

Consider the triangle-free graph process, which starts from the empty graph on $n$ vertices and in every step an edge is added that is chosen uniformly at random from all non-edges that do not form a triangle with the existing edges. We will show that there exists a constant $c$ such that asymptotically almost surely no copy of any fixed finite triangle-free graph on $k$ vertices with at least $ck$ edges appears in the triangle-free graph process.
Limit Theorems for the Number of Parts in a Random Weighted Partition
Authors: Mutafchiev Ljuben
Published: January 2020

Let $c_{m,n}$ be the number of weighted partitions of the positive integer $n$ with exactly $m$ parts, $1\le m\le n$. For a given sequence $b_k, k\ge 1,$ of part type counts (weights), the bivariate generating function of the numbers $c_{m,n}$ is given by the infinite product $\prod_{k=1}^\infty(1-uz^k)^{-b_k}$. Let $D(s)=\sum_{k=1}^\infty b_k k^{-s}, s=\sigma+iy,$ be the Dirichlet generating series of the weights $b_k$. In this present paper we consider the random variable $\xi_n$ whose distribution is given by $P(\xi_n=m)=c_{m,n}/(\sum_{m=1}^nc_{m,n}), 1\le m\le n$. We find an appropriate normalization for $\xi_n$ and show that its limiting distribution, as $n\to\infty$, depends on properties of the series $D(s)$. In particular, we identify five different limiting distributions depending on different locations of the complex half-plane in which $D(s)$ converges.
On Points Drawn from a Circle
Authors: Vatter Vincent , Waton Steve
Published: January 2020

Any finite generic set of points on the unit circle corresponds to a permutation in a canonical way. We characterise and enumerate the permutations that arise from this correspondence.
The Fundamental Group of Balanced Simplicial Complexes and Posets
Authors: Klee Steven
Published: January 2020

We establish an upper bound on the cardinality of a minimal generating set for the fundamental group of a large family of connected, balanced simplicial complexes and, more generally, simplicial posets.
Algebraically Solvable Problems: Describing Polynomials as Equivalent to Explicit Solutions
Authors: Schauz Uwe
Published: January 2020

The main result of this paper is a coefficient formula that sharpens and generalizes Alon and Tarsi's Combinatorial Nullstellensatz. On its own, it is a result about polynomials, providing some information about the polynomial map $P|_{\mathfrak{X}_1\times\cdots\times\mathfrak{X}_n}$ when only incomplete information about the polynomial $P(X_1,\dots,X_n)$ is given.In a very general working frame, the grid points $x\in \mathfrak{X}_1\times\cdots\times\mathfrak{X}_n$ which do not vanish under an algebraic solution – a certain describing polynomial $P(X_1,\dots,X_n)$ – correspond to the explicit solutions of a problem. As a consequence of the coefficient formula, we prove that the existence of an algebraic solution is equivalent to the existence of a nontrivial solution to a problem. By a problem, we mean everything that "owns" both, a set ${\cal S}$, which may be called the set of solutions; and a subset ${\cal S}_{\rm triv}\subseteq{\cal S}$, the set of trivial solutions.We give several examples of how to find algebraic solutions, and how to apply our coefficient formula. These examples are mainly from graph theory and combinatorial number theory, but we also prove several versions of Chevalley and Warning's Theorem, including a generalization of Olson's Theorem, as examples and useful corollaries.We obtain a permanent formula by applying our coefficient formula to the matrix polynomial, which is a generalization of the graph polynomial. This formula is an integrative generalization and sharpening of:1. Ryser's permanent formula.2. Alon's Permanent Lemma.3. Alon and Tarsi's Theorem about orientations and colorings of graphs.Furthermore, in combination with the Vigneron-Ellingham-Goddyn property of planar $n$-regular graphs, the formula contains as very special cases:4. Scheim's formula for the number of edge $n$-colorings of such graphs.5. Ellingham and Goddyn's partial answer to the list coloring conjecture.
Extremal Problems for $t$-Partite and $t$-Colorable Hypergraphs
Authors: Mubayi Dhruv , Talbot John
Published: January 2020

Fix integers $t \ge r \ge 2$ and an $r$-uniform hypergraph $F$. We prove that the maximum number of edges in a $t$-partite $r$-uniform hypergraph on $n$ vertices that contains no copy of $F$ is $c_{t, F}{n \choose r} +o(n^r)$, where $c_{t, F}$ can be determined by a finite computation. We explicitly define a sequence $F_1, F_2, \ldots$ of $r$-uniform hypergraphs, and prove that the maximum number of edges in a $t$-chromatic $r$-uniform hypergraph on $n$ vertices containing no copy of $F_i$ is $\alpha_{t,r,i}{n \choose r} +o(n^r)$, where $\alpha_{t,r,i}$ can be determined by a finite computation for each $i\ge 1$. In several cases, $\alpha_{t,r,i}$ is irrational. The main tool used in the proofs is the Lagrangian of a hypergraph.
On the Resilience of Long Cycles in Random Graphs
Authors: Dellamonica Jr Domingos , Kohayakawa Yoshiharu , Marciniszyn Martin , Steger Angelika
Published: January 2020

In this paper we determine the local and global resilience of random graphs $G_{n, p}$ ($p \gg n^{-1}$) with respect to the property of containing a cycle of length at least $(1-\alpha)n$. Roughly speaking, given $\alpha > 0$, we determine the smallest $r_g(G, \alpha)$ with the property that almost surely every subgraph of $G = G_{n, p}$ having more than $r_g(G, \alpha) |E(G)|$ edges contains a cycle of length at least $(1 - \alpha) n$ (global resilience). We also obtain, for $\alpha < 1/2$, the smallest $r_l(G, \alpha)$ such that any $H \subseteq G$ having $\deg_H(v)$ larger than $r_l(G, \alpha) \deg_G(v)$ for all $v \in V(G)$ contains a cycle of length at least $(1 - \alpha) n$ (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.
Spanning Trees with Many Leaves and Average Distance
Authors: DeLaViña Ermelinda , Waller Bill
Published: January 2020

In this paper we prove several new lower bounds on the maximum number of leaves of a spanning tree of a graph related to its order, independence number, local independence number, and the maximum order of a bipartite subgraph. These new lower bounds were conjectured by the program Graffiti.pc, a variant of the program Graffiti. We use two of these results to give two partial resolutions of conjecture 747 of Graffiti (circa 1992), which states that the average distance of a graph is not more than half the maximum order of an induced bipartite subgraph. If correct, this conjecture would generalize conjecture number 2 of Graffiti, which states that the average distance is not more than the independence number. Conjecture number 2 was first proved by F. Chung. In particular, we show that the average distance is less than half the maximum order of a bipartite subgraph, plus one-half; we also show that if the local independence number is at least five, then the average distance is less than half the maximum order of a bipartite subgraph. In conclusion, we give some open problems related to average distance or the maximum number of leaves of a spanning tree.
Two Coefficients of the Dyson Product
Authors: Lv Lun , Xin Guoce , Zhou Yue
Published: January 2020

In this paper, the closed-form expressions for the coefficients of ${x_r^2\over x_s^2}$ and ${x_r^2\over x_sx_t}$ in the Dyson product are found by applying an extension of Good's idea. As consequences, we find several interesting Dyson style constant term identities.
Area Distribution and Scaling Function for Punctured Polygons
Authors: Richard Christoph , Jensen Iwan , Guttmann Anthony J.
Published: January 2020

Punctured polygons are polygons with internal holes which are also polygons. The external and internal polygons are of the same type, and they are mutually as well as self-avoiding. Based on an assumption about the limiting area distribution for unpunctured polygons, we rigorously analyse the effect of a finite number of punctures on the limiting area distribution in a uniform ensemble, where punctured polygons with equal perimeter have the same probability of occurrence. Our analysis leads to conjectures about the scaling behaviour of the models. We also analyse exact enumeration data. For staircase polygons with punctures of fixed size, this yields explicit expressions for the generating functions of the first few area moments. For staircase polygons with punctures of arbitrary size, a careful numerical analysis yields very accurate estimates for the area moments. Interestingly, we find that the leading correction term for each area moment is proportional to the corresponding area moment with one less puncture. We finally analyse corresponding quantities for punctured self-avoiding polygons and find agreement with the conjectured formulas to at least 3–4 significant digits.
The MacNeille Completion of the Poset of Partial Injective Functions
Authors: Fortin Marc
Published: January 2020

Renner has defined an order on the set of partial injective functions from $[n]=\{1,\ldots,n\}$ to $[n]$. This order extends the Bruhat order on the symmetric group. The poset $P_{n}$ obtained is isomorphic to a set of square matrices of size $n$ with its natural order. We give the smallest lattice that contains $P_{n}$. This lattice is in bijection with the set of alternating matrices. These matrices generalize the classical alternating sign matrices. The set of join-irreducible elements of $P_{n}$ are increasing functions for which the domain and the image are intervals.
A Cluster Expansion Formula ($A_n$ case)
Authors: Schiffler Ralf
Published: January 2020

We consider the Ptolemy cluster algebras, which are cluster algebras of finite type $A$ (with non-trivial coefficients) that have been described by Fomin and Zelevinsky using triangulations of a regular polygon. Given any seed $\Sigma$ in a Ptolemy cluster algebra, we present a formula for the expansion of an arbitrary cluster variable in terms of the cluster variables of the seed $\Sigma$. Our formula is given in a combinatorial way, using paths on a triangulation of the polygon that corresponds to the seed $\Sigma$.
Generating Random Elements in Finite Groups
Authors: Dixon John D.
Published: January 2020

Let $G$ be a finite group of order $g$. A probability distribution $Z$ on $G\ $is called $\varepsilon$-uniform if $\left\vert Z(x)-1/g\right\vert \leq\varepsilon/g$ for each $x\in G$. If $x_{1},x_{2},\dots,x_{m}$ is a list of elements of $G$, then the random cube $Z_{m}:=Cube(x_{1},\dots,x_{m}) $ is the probability distribution where $Z_{m}(y)$ is proportional to the number of ways in which $y$ can be written as a product $x_{1}^{\varepsilon_{1}}x_{2}^{\varepsilon_{2}}\cdots x_{m}^{\varepsilon_{m}}$ with each $\varepsilon _{i}=0$ or $1$. Let $x_{1},\dots,x_{d} $ be a list of generators for $G$ and consider a sequence of cubes $W_{k}:=Cube(x_{k}^{-1},\dots,x_{1}^{-1},x_{1},\dots,x_{k})$ where, for $k>d$, $x_{k}$ is chosen at random from $W_{k-1}$. Then we prove that for each $\delta>0$ there is a constant $K_{\delta}>0$ independent of $G$ such that, with probability at least $1-\delta$, the distribution $W_{m}$ is $1/4$-uniform when $m\geq d+K_{\delta }\lg\left\vert G\right\vert $. This justifies a proposed algorithm of Gene Cooperman for constructing random generators for groups. We also consider modifications of this algorithm which may be more suitable in practice.
Subsums of a Zero-sum Free Subset of an Abelian Group
Authors: Gao Weidong , Li Yuanlin , Peng Jiangtao , Sun Fang
Published: January 2020

Let $G$ be an additive finite abelian group and $S \subset G$ a subset. Let f$(S)$ denote the number of nonzero group elements which can be expressed as a sum of a nonempty subset of $S$. It is proved that if $|S|=6$ and there are no subsets of $S$ with sum zero, then f$(S)\geq 19$. Obviously, this lower bound is best possible, and thus this result gives a positive answer to an open problem proposed by R.B. Eggleton and P. Erdős in 1972. As a consequence, we prove that any zero-sum free sequence $S$ over a cyclic group $G$ of length $|S| \ge {6|G|+28\over19}$ contains some element with multiplicity at least ${6|S|-|G|+1\over17}$.
More Constructions for Turán's (3,4)-Conjecture
Authors: Frohmader Andrew
Published: January 2020

For Turán's (3, 4)-conjecture, in the case of $n = 3k+1$ vertices, ${1 \over 2}6^{k-1}$ non-isomorphic hypergraphs are constructed that attain the conjecture. In the case of $n = 3k+2$ vertices, $6^{k-1}$ non-isomorphic hypergraphs are constructed that attain the conjecture.
On the Dispersions of the Polynomial Maps over Finite Fields
Authors: Schauz Uwe
Published: January 2020

We investigate the distributions of the different possible values of polynomial maps ${\Bbb F}_q^n\longrightarrow{\Bbb F}_q$, $x\longmapsto P(x)$. In particular, we are interested in the distribution of their zeros, which are somehow dispersed over the whole domain ${\Bbb F}_q^n$. We show that if $U$ is a "not too small" subspace of ${\Bbb F}_q^n$ (as a vector space over the prime field ${\Bbb F}_p$), then the derived maps ${\Bbb F}_q^n/U\longrightarrow{\Bbb F}_q$, $x+U\longmapsto\sum_{\tilde x\in x+U}P(\tilde x)$ are constant and, in certain cases, not zero. Such observations lead to a refinement of Warning's classical result about the number of simultaneous zeros $x\in{\Bbb F}_q^n$ of systems $P_1,\dots,P_m\in{\Bbb F}_q[X_1,\dots,X_n]$ of polynomials over finite fields ${\Bbb F}_q$. The simultaneous zeros are distributed over all elements of certain partitions (factor spaces) ${\Bbb F}_q^n/U$ of ${\Bbb F}_q^n$. $|\,{\Bbb F}_q^n/U|$ is then Warning's well known lower bound for the number of these zeros.
Random $k$-SAT: The Limiting Probability for Satisfiability for Moderately Growing $k$
Authors: Coja-Oghlan Amin , Frieze Alan
Published: January 2020

We consider a random instance $I_m=I_{m,n,k}$ of $k$-SAT with $n$ variables and $m$ clauses, where $k=k(n)$ satisfies $k-\log_2 n\to\infty$. Let $m=2^k(n\ln 2+c)$ for an absolute constant $c$. We prove that $$\lim_{n\to\infty}\Pr(I_m\hbox{ is satisfiable})=e^{-e^{-c}}.$$
Identifying Codes of Cartesian Product of Two Cliques of the Same Size
Authors: Gravier S. , Moncel J. , Semri A.
Published: January 2020

We determine the minimum cardinality of an identifying code of $K_n\square K_n$, the Cartesian product of two cliques of same size. Moreover we show that this code is unique, up to row and column permutations, when $n\geq 5$ is odd. If $n\geq 4$ is even, we exhibit two distinct optimal identifying codes.
Rationality, Irrationality, and Wilf Equivalence in Generalized Factor Order
Authors: Kitaev Sergey , Liese Jeffrey , Remmel Jeffrey , Sagan Bruce E.
Published: January 2020

Let $P$ be a partially ordered set and consider the free monoid $P^*$ of all words over $P$. If $w,w'\in P^*$ then $w'$ is a factor of $w$ if there are words $u,v$ with $w=uw'v$. Define generalized factor order on $P^*$ by letting $u\le w$ if there is a factor $w'$ of $w$ having the same length as $u$ such that $u\le w'$, where the comparison of $u$ and $w'$ is done componentwise using the partial order in $P$. One obtains ordinary factor order by insisting that $u=w'$ or, equivalently, by taking $P$ to be an antichain. Given $u\in P^*$, we prove that the language ${\cal F}(u)=\{w\ :\ w\ge u\}$ is accepted by a finite state automaton. If $P$ is finite then it follows that the generating function $F(u)=\sum_{w\ge u} w$ is rational. This is an analogue of a theorem of Björner and Sagan for generalized subword order. We also consider $P={\Bbb P}$, the positive integers with the usual total order, so that $P^*$ is the set of compositions. In this case one obtains a weight generating function $F(u;t,x)$ by substituting $tx^n$ each time $n\in{\Bbb P}$ appears in $F(u)$. We show that this generating function is also rational by using the transfer-matrix method. Words $u,v$ are said to be Wilf equivalent if $F(u;t,x)=F(v;t,x)$ and we prove various Wilf equivalences combinatorially. Björner found a recursive formula for the Möbius function of ordinary factor order on $P^*$. It follows that one always has $\mu(u,w)=0,\pm1$. Using the Pumping Lemma we show that the generating function $M(u)=\sum_{w\ge u} |\mu(u,w)| w$ can be irrational.
Partitions and Edge Colourings of Multigraphs
Authors: Kostochka Alexandr V. , Stiebitz Michael
Published: January 2020

Erdős and Lovász conjectured in 1968 that for every graph $G$ with $\chi(G)>\omega(G)$ and any two integers $s,t\geq 2$ with $s+t=\chi(G)+1$, there is a partition $(S,T)$ of the vertex set $V(G)$ such that $\chi(G[S])\geq s$ and $\chi(G[T])\geq t$. Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for line graphs of multigraphs.
A New Method to Construct Lower Bounds for Van der Waerden Numbers
Authors: Herwig P. R. , Heule M.J.H. , Van Lambalgen P. M. , Van Maaren H.
Published: January 2020

We present the Cyclic Zipper Method, a procedure to construct lower bounds for Van der Waerden numbers. Using this method we improved seven lower bounds. For natural numbers $r$, $k$ and $n$ a Van der Waerden certificate $W(r,k,n)$ is a partition of $\{1, \ldots, n\}$ into $r$ subsets, such that none of them contains an arithmetic progression of length $k$ (or larger). Van der Waerden showed that given $r$ and $k$, a smallest $n$ exists - the Van der Waerden number $W(r,k)$ - for which no certificate $W(r,k,n)$ exists. In this paper we investigate Van der Waerden certificates which have certain symmetrical and repetitive properties. Surprisingly, it shows that many Van der Waerden certificates, which must avoid repetitions in terms of arithmetic progressions, reveal strong regularities with respect to several other criteria. The Cyclic Zipper Method exploits these regularities. To illustrate these regularities, two techniques are introduced to visualize certificates.
Longest Alternating Subsequences in Pattern-Restricted Permutations
Authors: Firro Ghassan , Mansour Toufik , Wilson Mark C.
Published: January 2020

Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.
Wreath Products of Permutation Classes
Authors: Brignall Robert
Published: January 2020

A permutation class which is closed under pattern involvement may be described in terms of its basis. The wreath product construction $X\wr Y$ of two permutation classes $X$ and $Y$ is also closed, and we exhibit a family of classes $Y$ with the property that, for any finitely based class $X$, the wreath product $X\wr Y$ is also finitely based. Additionally, we indicate a general construction for basis elements in the case where $X\wr Y$ is not finitely based.
A Closed Formula for the Number of Convex Permutominoes
Authors: Disanto Filippo , Frosini Andrea , Pinzani Renzo , Rinaldi Simone
Published: January 2020

In this paper we determine a closed formula for the number of convex permutominoes of size $n$. We reach this goal by providing a recursive generation of all convex permutominoes of size $n+1$ from the objects of size $n$, according to the ECO method, and then translating this construction into a system of functional equations satisfied by the generating function of convex permutominoes. As a consequence we easily obtain also the enumeration of some classes of convex polyominoes, including stack and directed convex permutominoes.
Small Forbidden Configurations III
Authors: Anstee R. P. , Kamoosi N.
Published: January 2020

The present paper continues the work begun by Anstee, Ferguson, Griggs and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let $F$ be a $k\times l$ (0,1)-matrix (the forbidden configuration). Assume $A$ is an $m\times n$ simple matrix which has no submatrix which is a row and column permutation of $F$. We define ${\hbox{forb}}(m,F)$ as the largest $n$, which would depend on $m$ and $F$, so that such an $A$ exists. 'Small' refers to the size of $k$ and in this paper $k=2$. For $p\le q$, we set $F_{pq}$ to be the $2\times (p+q)$ matrix with $p$ $\bigl[{1\atop0}\bigr]$'s and $q$ $\bigl[{0\atop1}\bigr]$'s. We give new exact values: ${\hbox{forb}}(m,F_{0,4})=\lfloor {5m\over2}\rfloor +2$, ${\hbox{forb}}(m,F_{1,4})=\lfloor {11m\over4}\rfloor +1$, ${\hbox{forb}}(m,F_{1,5})=\lfloor {15m\over4}\rfloor +1$, ${\hbox{forb}}(m,F_{2,4})=\lfloor {10m\over3}-{4\over3}\rfloor$ and ${\hbox{forb}}(m,F_{2,5})=4m$ (For ${\hbox{forb}}(m,F_{1,4})$, ${\hbox{forb}}(m,F_{1,5})$ we obtain equality only for certain classes modulo 4). In addition we provide a surprising construction which shows ${\hbox{forb}}(m,F_{pq})\ge \bigl({p+q\over2}+O(1)\bigr)m$.
KARAKTER LANSKAP UNTUK EKOWISATA PADA AREA PASCA TAMBANG BATUBARA DUSUN RANTAU PANDAN, MUARA BUNGO, PROVINSI JAMBI
Authors: Kusumoarto Andrianto
Published: January 2020

Area Pasca Tambang di Dusun Rantau Pandan, Muara Bungo, Provinsi Jambi memiliki karakter lanskap yang sangat potensial untuk pengembangan ekowisata. Selain itu lokasi dimana area pasca tambang ini berada memiliki keanekaragaman hayati. Penelitian ini bertujuan untuk mengidentifikasi karakter lanskap dan tipe landform di area pasca tambang Dusun Rantau Pandan untuk ekowisata. Penelitian ini menggunakan metode pendekatan deskriptif kualitatif melalui survai dan wawancara, dimana dilakukan serangkaian tahap, yakni : 1) identifikasi landform dan 2) identifikasi karakter lanskap. Hasil penelitian memperlihatkan tersebar beberapa tipe landform seperti landform datar, landform cembung, landform cekung, punggung bukit, lembah. Selain itu juga tersebar beberapa karakter lanskap pada lingkungan alam dan lingkungan buatan. Kategori karakter lanskap di lingkungan alami yang tersebar di area tersebut adalah area vegetasi, sungai, lahan bukit, area semak, area belukar, padang rumput, tebing, permukaan datar, sedangkan yang tersebar di lingkungan buatan adalah kolam eks. tambang serta jalur jalan kendaraan bermotor. Karakter lanskap yang tersebar di area ini seharusnya dilindungi dan dimodifikasi untuk tujuan ekowisata. Beberapa cara yang dilakukan seperti penghapusan elemen yang tidak sesuai, akesentuasi bentuk alami, alterasi bentuk alami, intensifikasi dan peningkatan kualitas visual secara intensif.
STRATEGI SUMBER DAYA MANUSIA: STUDI EKSPLORASI DI MADRASAH TSANAWIYAH SWASTA JAGAT RAYA, DESA KEDONGDONG, KABUPATEN CIREBON-INDONESIA
Authors: Maula Nurkholifatul
Published: January 2020

Polemik sekolah swasta selama ini cukup menjadi perdebatan di Indonesia.Cukup banyak sekolah swasta yang memiliki kualitas bagus di Indonesia, hingga eksistensinya pun mengalahkan sekolah negeri. Akan tetapi, hal itu berbanding terbalik dengan sekolah swasta di desa. Sekolah swasta di desa cukup memprihatinkan.Penelitian ini bertujuan untuk mndeskripsikan mengenai startegi sumberdaya manusia di MTs Jagat Raya dan dampak dari strategi sumberdaya manusia terhadap perkembangan sekolah. Pada hal ini, metode eksploratori digunakan dengan metode wawancara, observasi, dan kajian-kajian dokumen.Tujuan pertama ini, dengan melakukan wawancara dan observasi langsung.Tujuan kedua penelitian ini dilakukan dengan menggunakan kajian dokumen. Adapun hasil dari penelitian ini adalah dalam hal organization, pada perencanaan visi dan misi, dilakukan dengan musyawarah bersama dengan guru-guru di sekolah.Adapun dampak dari strategi sumber daya manusia tersebut, dari segi kualitas siswa nya selama lima tahun terakhir cukup meningkat, dan nilai ujian nasionalnya cukup membaik dari tahun ke tahun. Akan tetapi, hal ini berbanding terbalik dengan jumlah siswa yang masuk setiap tahunnya mengalami penurunan. Hal ini cukup kritis untuk keberlanjutan sekolah tersebut.
PERAN DUKUN DAN TUO TENGGANAI SEBAGAI MEDIATOR PESAN IMUNISASI MELALUI TRADISI “NGERAWI” DI KECAMATAN BATANG ASAI, SAROLANGUN JAMBI
Authors: Kalsum Ummi , Halim Raden , M.Ridwan
Published: January 2020

Peran Dukun bayi dan Tuo Tengganai yang mempunyai kedudukan yang dihormati dan didengar dapat dijadikan mediator penyampai pesan yang sangat baik khususnya untuk meningkatkan partisipasi masyarakat terutama ibu dalam melaksanakan imunisasi dasar lengkap bagi bayinya. Pelatihan untuk meningkatkan pengetahuan dukun dan tuo tengganai penting sebagai langkah awal untuk pemberdayaan. Tujuan studi ini untuk menilai perubahan pengetahuan, sikap dan komitmen Dukun dan Tuo Tengganai sebagai mediator pesan imunisasi kepada ibu hamil dan suami sebelum dan setelah diberi pelatihan serta penyebab rendahnya cakupan imunisasi. Metode penelitian adalah intervensi dengan disain quasi eksperiment menggunakan one group pre-post test design terhadap 5 orang dukun dan 29 orang Tuo Tengganai. Lokasi penelitian di Desa Kasiro, Bukit Sulah dan Datuk Nan Duo Kecamatan Batang Asai Kabupaten Sarolangun Jambi. Ada peningkatan pengetahuan yang bermakna setelah diberikan intervensi berupa pelatihan tentang imunisasi kepada Dukun dan Tuo Tengganai, meskipun sikap dan komitmen (dukungan) tidak ada perbedaan yang bermakna setelah diberi intervensi karena sikap dan komitmen mereka relatif sudah baik terhadap program imunisasi. Perlu peningkatan pengetahuan dengan pemberian pelatihan atau penyuluhan tentang imunisasi untuk lebih meningkatkan peran dukun dan tuo tengganai sebagai mediator penyampai pesan imunisasi melalui tradisi “ngerawi”agar cakupan imunisasi bayi dan balita meningkat.
STRATEGI PENGHIDUPAN MASYARAKAT DALAM MENGHADAPI BONUS DEMOGRAFI DI PROVINSI JAMBI
Authors: Islakhiyah Islakhiyah , Yanti Lily
Published: January 2020

Penelitian ini bertujuan untuk menganalisis penghidupan masyarakat menghadapi peluang/bonus demografi di Provinsi Jambi. Penelitian ini menggunakan Teori penghidupan berkelanjutan dalam menganalisis permasalahan yang ditemui. Teori ini memberikan gambaran realitas kondisi masyarakat tidak hanya dari aspek permasalahan atau kebutuhan, tetapi juga secara konfrehensif dari berbagai aspek modal yang dimiliki oleh masyarakat, seperti bagaimana masyarakat beradaptasi dan mempertahankan kehidupannya dari kondisi sosial, finansial, lingkungan serta pemanfaatan sumberdaya yang ada di sekitar. Dalam menentukan permasalahan, analisis deskriptif kualitatif dan analisis faktor digunakan untuk menjabarkan hasil penelitian.Hasil penelitian menunjukkan bahwa, sebagian besar masyarakat tidak siap untuk meningkatkan taraf hidupnya.Terlihat dari kemampuan mereka dalam menabung serta memanfaatkan potensi yang ada disekitar. Faktor finansial berpotensi besar mempengaruhi penghidupan masyarakat.
Analisis Aplikasi Desain Street Signage pada Fasilitas Publik di Kota Bandung
Authors: Setiawan Budi
Published: January 2020

Sebagai salah satu Kota Desain UNESCO, Bandung berkomitmen untuk mengembangkan fasilitas-fasilitas publiknya yang berbasis desain dan kreativitas. Selain penyelenggaraan acara-acara yang berhubungan dengan ekonomi dan wirausaha kreatif, pembangunan fasilitas sosial dan fasilitas umum berupa pembenahan taman-taman kota, penataan trotoar dan fasilitas lainnya juga berkembang pesat. Tema street signage diambil sebagai bahan penelitian didasarkan keberadaan sebagai salah satu perangkat utama ruang publik dan fasilitas kota yang menjadi faktor indikator penting akan kualitas ruang publik kotanya. Oleh karena itu perlu adanya analisa mengenai aplikasi street signage yang tepat dan terpadu sesuai dengan kapasitas kota sebagai kota desain dunia. Penelitian ini akan membahas keberadaan street signage di titik-titik strategis Bandung yang menjadi pusat pengembangan kreativitas kota Bandung dalam konteksnya sebagai City of Design. Metode penelitian yang diambil adalah Visual Environment Research dengan melakukan studi lapangan, observasi, dan studi literatur. Diharapkan penelitian ini memberikan kontribusi terhadap strategi desain maupun inovasi sosial terhadap kota-kota lain di Indonesia.
Bermain dan Berkreasi untuk Melatih Perkembangan Anak Usia Dini Menggunakan Puzzle Edukatif dari Bahan Bambu
Authors: Purwanto Purwanto -
Published: January 2020

Perkembangan  kognitif  merupakan  dasar  bagi  kemampuan anak  untuk berpikir, berkreativitas   dan   berkarya. Dalam pemenuhnan kebutuhan akan perkembangan anak dapat dilakukan dengan bermain sambil berkreasi, karena dengan bermain anak akan menerima pengalaman baru, berimajinasi ide, berinteraksi dengan orang lain, lingkungan dan mulai merasakan dunia mereka. Salah satu permasalahan yang ada di kelompok bermain Amongsiwi di Bantul adalah kurang optimalnya perkembangan kognitif anak-anak dan kurang tersedianya sarana alat peraga edukatif seperti permainan puzzle. Untuk itu dalam penelitian ini bertujuan untuk mengajak anak bermain dan berkreasi untuk mengembangkan kognitis anak menggunakan puzzle edukatif dari bahan bambu yang layak dan ramah lingkungan, apalagi di sekolah ini ada program khusus bermain dan berkreasi setiap hari Jum’at. Dalam  penelitian ini digunakan metode penelitian pengembangan (research and development) dengan melakukan kegiatan meliputi analisis potensi dan masalah, pengumpulan data, membuat desain produk, ujicoba produk, uji pemakaian. Dalam pengumpulan data dilakukan observasi, wawancara, dan dokumentasi kemudian data dianalisis secara deskriptif kuantitatif. Hasil penelitian menunjukkan bahwa puzzle edukatif yang dirancang secara materi layak untuk diujicobakan, sedangkan hasil  respon anak terhadap penggunaan media puzzle edukatif mencapai 85 % yang ini menunjukkan kategori layak. Selanjutnya berdasarkan hasil pengamatan dan wawancara selama kegiatan bermain dan berkreasi anak-anak dapat menghasilkan karya produk yang sudah berbentuk bangun misalnya robot-robotan atau mobil-mobilan. Berdasarkan hasil penelitian yang telah dilakukan dapat disimpulkan bahwa media puzzle edukatif dari bahan bambu dapat membantu anak bermain dan berkreasi sebagai salah satu unsur dalam pengembangan kognitif anak dan menghasilkan sebuah alat peraga edukatif yang layak untuk digunakan.
Ratio effect slope can sometimes be an appropriate metric of the approximate number system sensitivity
Authors: Krajcsi Attila
Published: January 2020

The approximate number system (ANS) is believed to be an essential component of numerical understanding. The sensitivity of the ANS has been found to be correlating with various mathematical abilities. Recently, Chesney (2018, Attention, Perception, & Psychophysics, 80[5], 1057–1063) demonstrated that if the ANS sensitivity is measured with the ratio effect slope, the slope may measure the sensitivity imprecisely. The present work extends her findings by demonstrating that mathematically the usability of the ratio effect slope depends on the Weber fraction range of the sample and the ratios of the numbers in the used test. Various indexes presented here can specify whether the use of the ratio effect slope as a replacement for the sigmoid fit is recommended or not. Detailed recommendations and a publicly available script help the researchers to plan or evaluate the use of the ratio effect slope as an ANS sensitivity index.
The Pitch-angle Distributions of Suprathermal Ions near an Interplanetary Shock
Authors: Yang Liu , Berger Lars , Wimmer-Schweingruber Robert F. , Wang Linghua , Yu Jia , Galvin Antoinette B. , Möbius Eberhard
Published: January 2020

We present a case study of the pitch-angle distributions (PADs) of suprathermal H+, He2+ at ∼10–40 keV/nuc and He+ at ∼8–20 keV/nuc near a reverse shock of a stream interaction region observed by the Plasma and Suprathermal Ion Composition instrument on board the Solar Terrestrial Relations Observatory Ahead spacecraft on 2008 March 9. We find that in both the downstream and upstream region close to the shock, the shocked particles of all three species appear to have a power-law-like spectrum at these suprathermal energies. The PADs of these three species show very similar behavior: in the downstream region, the phase space density appears to be significantly higher in the direction perpendicular to the interplanetary magnetic field (IMF) than in the parallel direction, along which particles accelerated at the shock front are supposed to escape into the downstream region. In the upstream region, the PADs of all three species show a clear beam in the direction antiparallel to the IMF due to the escaping particles from the shock into the upstream region. In addition, we find that suprathermal He+ shows a signature of bidirectional beams in the upstream region very close to the shock. These results suggest that H+, He2+ at ∼10–40 keV/nuc and He+ at ∼8–20 keV/nuc could be accelerated similarly at interplanetary shocks and that shock drift acceleration likely plays an important role in the in situ acceleration of low-energy suprathermal ions.