bluuebunny/crossref_metadata_2025_split huggingface dataset:
Vertex Isoperimetric Inequalities for a Family of Graphs on $\mathbb{Z}^k$
Authors: Veomett Ellen , Radcliffe Andrew John 
Published: January 2020

We consider the family of graphs whose vertex set is $\mathbb{Z}^k$ where two vertices are connected by an edge when their $\ell_\infty$-distance is 1. We prove the optimal vertex isoperimetric inequality for this family of graphs. That is, given a positive integer $n$, we find a set $A\subset \mathbb{Z}^k$ of size $n$ such that the number of vertices who share an edge with some vertex in $A$ is minimized. These sets of minimal boundary are nested, and the proof uses the technique of compression.We also show a method of calculating the vertex boundary for certain subsets in this family of graphs. This calculation and the isoperimetric inequality allow us to indirectly find the sets which minimize the function calculating the boundary.
Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points
Authors: Spivey Michael Z. 
Published: January 2020

We give bijective proofs that, when combined with one of the combinatorial proofs of the general ballot formula, constitute a combinatorial argument yielding the number of lattice paths from $(0,0)$ to $(n,rn)$ that touch or cross the diagonal $y = rx$ at exactly $k$ lattice points. This enumeration partitions all lattice paths from $(0,0)$ to $(n,rn)$. While the resulting formula can be derived using results from Niederhausen, the bijections and combinatorial proof are new.
On the Spanning Trees of the Hypercube and other Products of Graphs
Authors: Bernardi Olivier 
Published: January 2020

We give two combinatorial proofs of a product formula for the number of spanning trees of the $n$-dimensional hypercube. The first proof is based on the assertion that if one chooses a uniformly random rooted spanning tree of the hypercube and orient each edge from parent to child, then the parallel edges of the hypercube get orientations which are independent of one another. This independence property actually holds in a more general context and has intriguing consequences. The second proof uses some "killing involutions'' in order to identify the factors in the product formula. It leads to an enumerative formula for the spanning trees of the $n$-dimensional hypercube augmented with diagonals edges, counted according to the number of edges of each type. We also discuss more general formulas, obtained using a matrix-tree approach, for the number of spanning trees of the Cartesian product of complete graphs.
Viewing Determinants as Nonintersecting Lattice Paths yields Classical Determinantal Identities Bijectively
Authors: Fulmek Markus 
Published: January 2020

In this paper, we show how general determinants may be viewed as generating functions of nonintersecting lattice paths, using the Lindström-Gessel-Viennot-method and the Jacobi Trudi identity together with elementary observations.After some preparations, this point of view provides "graphical proofs'' for classical determinantal identities like the Cauchy-Binet formula, Dodgson's condensation formula, the Plücker relations, Laplace's expansion and Turnbull's identity. Also, a determinantal identity generalizing Dodgson's condensation formula is presented, which might be new.
On the Number of Partition Weights with Kostka Multiplicity One
Authors: Gates Zachary , Goldman Brian , Vinroot C. Ryan 
Published: January 2020

Given a positive integer $n$, and partitions $\lambda$ and $\mu$ of $n$, let $K_{\lambda \mu}$ denote the Kostka number, which is the number of semistandard Young tableaux of shape $\lambda$ and weight $\mu$. Let $J(\lambda)$ denote the number of $\mu$ such that $K_{\lambda \mu} = 1$. By applying a result of Berenshtein and Zelevinskii, we obtain a formula for $J(\lambda)$ in terms of restricted partition functions, which is recursive in the number of distinct part sizes of $\lambda$. We use this to classify all partitions $\lambda$ such that $J(\lambda) = 1$ and all $\lambda$ such that $J(\lambda) = 2$. We then consider signed tableaux, where a semistandard signed tableau of shape $\lambda$ has entries from the ordered set $\{0 < \bar{1} < 1 < \bar{2} < 2 < \cdots \}$, and such that $i$ and $\bar{i}$ contribute equally to the weight. For a weight $(w_0, \mu)$ with $\mu$ a partition, the signed Kostka number $K^{\pm}_{\lambda,(w_0, \mu)}$ is defined as the number of semistandard signed tableaux of shape $\lambda$ and weight $(w_0, \mu)$, and $J^{\pm}(\lambda)$ is then defined to be the number of weights $(w_0, \mu)$ such that $K^{\pm}_{\lambda, (w_0, \mu)} = 1$. Using different methods than in the unsigned case, we find that the only nonzero value which $J^{\pm}(\lambda)$ can take is $1$, and we find all sequences of partitions with this property. We conclude with an application of these results on signed tableaux to the character theory of finite unitary groups.
Resolving Sets and Semi-Resolving Sets in Finite Projective Planes
Authors: Héger Tamás , Takáts Marcella 
Published: January 2020

In a graph $\Gamma=(V,E)$ a vertex $v$ is resolved by a vertex-set $S=\{v_1,\ldots,v_n\}$ if its (ordered) distance list with respect to $S$, $(d(v,v_1),\ldots,d(v,v_n))$, is unique. A set $A\subset V$ is resolved by $S$ if all its elements are resolved by $S$. $S$ is a resolving set in $\Gamma$ if it resolves $V$. The metric dimension of $\Gamma$ is the size of the smallest resolving set in it. In a bipartite graph a semi-resolving set is a set of vertices in one of the vertex classes that resolves the other class.We show that the metric dimension of the incidence graph of a finite projective plane of order $q\geq 23$ is $4q-4$, and describe all resolving sets of that size. Let $\tau_2$ denote the size of the smallest double blocking set in PG$(2,q)$, the Desarguesian projective plane of order $q$. We prove that for a semi-resolving set $S$ in the incidence graph of PG$(2,q)$, $|S|\geq \min \{2q+q/4-3, \tau_2-2\}$ holds. In particular, if $q\geq9$ is a square, then the smallest semi-resolving set in PG$(2,q)$ has size $2q+2\sqrt{q}$. As a corollary, we get that a blocking semioval in PG$(2, q)$, $q\geq 4$, has at least $9q/4-3$ points. A corrigendum was added to this paper on March 3, 2017.
A Note on Coloring Line Arrangements
Authors: Ackerman Eyal , Pach János , Pinchasi Rom , Radoičić Radoš , Tóth Géza 
Published: January 2020

We show that the lines of every arrangement of $n$ lines in the plane can be colored with $O(\sqrt{n/ \log n})$ colors such that no face of the arrangement is monochromatic. This improves a bound of Bose et al. by a $\Theta(\sqrt{\log n})$ factor. Any further improvement on this bound would also improve the best known lower bound on the following problem of Erdős: estimate the maximum number of points in general position within a set of $n$ points containing no four collinear points.
Partitions and Compositions over Finite Fields
Authors: Muratovic-Ribic Amela , Wang Qiang 
Published: January 2020

In this paper we find an exact formula for the number of partitions of an element $z$ into $m$ parts over a finite field, i.e. we find the number of nonzero solutions of the equation $x_1+x_2+\cdots +x_m=z$ over a finite field when the order of terms does not matter. This is equivalent to counting the number of $m$-multi-subsets whose sum is $z$. When the order of the terms in a solution does matter, such a solution is called a composition of $z$. The number of compositions is useful in the study of zeta functions of toric hypersurfaces over finite fields. We also give an application in the study of polynomials of prescribed ranges over finite fields.
Generalized Pattern Frequency in Large Permutations
Authors: Cooper Joshua , Lundberg Erik , Nagle Brendan 
Published: January 2020

In the study of permutations, generalized patterns extend classical patterns by adding the requirement that certain adjacent integers in a pattern must be adjacent in the permutation.For any generalized pattern $\pi_0^*$ of length $k$ with $1 \leq b \leq k$ blocks, we prove that for all $\mu > 0$, there exists $0 < c =c(k, \mu) < 1$ so that whenever $n \geq n_0(k, \mu, c)$, all but $c^n n!$ many $\pi \in S_n$ admit $(1 \pm \mu) \tfrac{1}{k!}\tbinom{n}{b}$ occurrences of $\pi_0^*$. Up to the choice of $c$, this result is best possible for all $\pi_0^*$ with $k \geq 2$.We also give a lower bound on avoidance of the generalized pattern $12$-$34$, which answers a question of S. Elizalde (2006).
New Results in t-Tone Coloring of Graphs
Authors: Cranston Daniel , Kim Jaehoon , Kinnersley William 
Published: January 2020

A $t$-tone $k$-coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,\dots,k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The $t$-tone chromatic number of $G$, denoted $t(G)$, is the minimum $k$ such that $G$ has a $t$-tone $k$-coloring. Bickle and Phillips showed that always $\tau_2(G) \leq [\Delta(G)]^2 +\Delta(G)$, but conjectured that in fact $\tau_2(G) \leq 2\Delta(G) + 2$; we confirm this conjecture when $\Delta(G) \leq 3$ and also show that always $\tau_2(G) \leq \lceil (2 +\sqrt{2}) \Delta(G) \rceil$. For general $t$ we prove that $\tau_t(G) \leq (t^2+t) \Delta(G)$. Finally, for each $t \geq 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{\Delta(T)} \leq \tau_t(T) \leq c_2\sqrt{\Delta(T)}$.
Generalized Balanced Tournament Designs with Block Size Four
Authors: Chee Yeow Meng , Kiah Han Mao , Wang Chengmin 
Published: January 2020

In this paper, we remove the outstanding values $m$ for which the existence of a GBTD$(4,m)$ has not been decided previously. This leads to a complete solution to the existence problem regarding GBTD$(4,m)$s.
Independent Sets in Graphs with Given Minimum Degree
Authors: Alexander James , Cutler Jonathan , Mink Tim 
Published: January 2020

The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late. Let $i(G)$ be the number of independent sets in a graph $G$ and let $i_t(G)$ be the number of independent sets in $G$ of size $t$. Kahn used entropy to show that if $G$ is an $r$-regular bipartite graph with $n$ vertices, then $i(G)\leq i(K_{r,r})^{n/2r}$. Zhao used bipartite double covers to extend this bound to general $r$-regular graphs. Galvin proved that if $G$ is a graph with $\delta(G)\geq \delta$ and $n$ large enough, then $i(G)\leq i(K_{\delta,n-\delta})$. In this paper, we prove that if $G$ is a bipartite graph on $n$ vertices with $\delta(G)\geq\delta$ where $n\geq 2\delta$, then $i_t(G)\leq i_t(K_{\delta,n-\delta})$ when $t\geq 3$. We note that this result cannot be extended to $t=2$ (and is trivial for $t=0,1$). Also, we use Kahn's entropy argument and Zhao's extension to prove that if $G$ is a graph with $n$ vertices, $\delta(G)\geq\delta$, and $\Delta(G)\leq \Delta$, then $i(G)\leq i(K_{\delta,\Delta})^{n/2\delta}$.
Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs
Authors: Beck Matthias , Bogart Tristram , Pham Tu 
Published: January 2020

A Golomb ruler is a sequence of distinct integers (the markings of the ruler) whose pairwise differences are distinct. Golomb rulers, also known as Sidon sets and $B_2$ sets, can be traced back to additive number theory in the 1930s and have attracted recent research activities on existence problems, such as the search for optimal Golomb rulers (those of minimal length given a fixed number of markings). Our goal is to enumerate Golomb rulers in a systematic way: we study$$g_m(t) := \# \left\{ {\bf x} \in {\bf Z}^{m+1} : \, 0 = x_0 < x_1 < \dots < x_m = t , \text{ all } x_j - x_k \text{ distinct} \right\} ,$$the number of Golomb rulers with $m+1$ markings and length $t$.Our main result is that $g_m(t)$ is a quasipolynomial in $t$ which satisfies a combinatorial reciprocity theorem: $(-1)^{m-1} g_m(-t)$ equals the number of rulers ${\bf x}$ of length $t$ with $m+1$ markings, each counted with its Golomb multiplicity, which measures how many combinatorially different Golomb rulers are in a small neighborhood of ${\bf x}$. Our reciprocity theorem can be interpreted in terms of certain mixed graphs associated to Golomb rulers; in this language, it is reminiscent of Stanley's reciprocity theorem for chromatic polynomials. Thus in the second part of the paper we develop an analogue of Stanley's theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations.
Extremal Graphs for Blow-Ups of Cycles and Trees
Authors: Liu Hong 
Published: January 2020

The blow-up of a graph H is the graph obtained from replacing each edge in H by a clique of the same size where the new vertices of the cliques are all different. Erdős et al. and Chen et al. determined the extremal number of blow-ups of stars. Glebov determined the extremal number and found all extremal graphs for blow-ups of paths. We determined the extremal number and found the extremal graphs for the blow-ups of cycles and a large class of trees, when n is sufficiently large. This generalizes their results. The additional aim of our note is to draw attention to a powerful tool, a classical decomposition theorem of Simonovits.
Irreducible Cycles and Points in Special Position in Moduli Spaces for Tropical Curves
Authors: Gathmann Andreas , Schroeter Franziska 
Published: January 2020

In the first part of this paper, we discuss the notion of irreducibility of cycles in the moduli spaces of $n$-marked rational tropical curves. We prove that Psi-classes and vital divisors are irreducible, and that locally irreducible divisors are also globally irreducible for $ n \le 6 $. In the second part of the paper, we show that the locus of point configurations in $({\mathbb R}^2)^n $ in special position for counting rational plane curves (defined in two different ways) can be given the structure a tropical cycle of codimension $1$. In addition, we compute explicitly the weights of this cycle.
The Combinatorics of Interval Vector Polytopes
Authors: Beck Matthias , De Silva Jessica , Dorfsman-Hopkins Gabriel , Pruitt Joseph , Ruiz Amanda 
Published: January 2020

An interval vector is a $(0,1)$-vector in $\mathbb{R}^n$ for which all the $1$'s appear consecutively, and an interval vector polytope is the convex hull of a set of interval vectors in $\mathbb{R}^n$. We study three particular classes of interval vector polytopes which exhibit interesting geometric-combinatorial structures; e.g., one class has volumes equal to the Catalan numbers, whereas another class has face numbers given by the Pascal 3-triangle.
Near Packings of Graphs
Authors: Zak Andrzej 
Published: January 2020

A packing of a graph $G$ is a set $\{G_1,G_2\}$ such that $G_1\cong G$, $G_2\cong G$, and $G_1$ and $G_2$ are edge disjoint subgraphs of $K_n$. Let $\mathcal{F}$ be a family of graphs. A near packing admitting $\mathcal{F}$ of a graph $G$ is a generalization of a packing. In a near packing admitting $\mathcal{F}$, the two copies of $G$ may overlap so the subgraph defined by the edges common to both copies is a member of $\mathcal{F}$. In the paper we study three families of graphs (1) $\mathcal{E}_k$ -- the family of all graphs with at most $k$ edges, (2) $\mathcal{D}_k$ -- the family of all graphs with maximum degree at most $k$, and (3) $\mathcal{C}_k$ -- the family of all graphs that do not contain a subgraph of connectivity greater than or equal to $k+1$. By $m(n,\mathcal{F})$ we denote the maximum number $m$ such that each graph of order $n$ and size less than or equal to $m$ has a near-packing admitting $\mathcal{F}$. It is well known that $m(n,\mathcal{C}_0)=m(n,\mathcal{D}_0)=m(n,\mathcal{E}_0)=n-2$ because a near packing admitting $\mathcal{C}_0$, $\mathcal{D}_0$ or $\mathcal{E}_0$ is just a packing. We prove some generalization of this result, namely we prove that $ m(n,\mathcal{C}_k)\approx (k+1)n$, $ m(n,\mathcal{D}_1)\approx \frac{3}{2}n$, $ m(n,\mathcal{D}_2)\approx 2n$. We also present bounds on $m(n,\mathcal{E}_k)$. Finally, we prove that each graph of girth at least five has a near packing admitting $\mathcal{C}_1$ (i.e. a near packing admitting the family of the acyclic graphs).
Cross-Intersecting Families of Labeled Sets
Authors: Zhang Huajun 
Published: January 2020

For two positive integers $n$ and $p$, let $\mathcal{L}_{p}$ be the family of labeled $n$-sets given by $$\mathcal{L}_{p}=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}: \ell_i\in[p], i=1,2\ldots,n\big\}.$$ Families $\mathcal{A}$ and $\mathcal{B}$ are said to be cross-intersecting if $A\cap B\neq\emptyset$ for all $A\in \mathcal{A}$ and $B\in\mathcal{B}$. In this paper, we will prove that for $p\geq 4$, if $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting subfamilies of $\mathcal{L}_{\mathfrak{p}}$, then $|\mathcal{A}||\mathcal{B}|\leq p^{2n-2}$, and equality holds if and only if $\mathcal{A}$ and $\mathcal{B}$ are an identical largest intersecting subfamily of $\mathcal{L}_{p}$.
Separability of Density Matrices of Graphs for Multipartite Systems
Authors: Xie Chen , Zhao Hui , Wang Zhixi 
Published: January 2020

We investigate separability of Laplacian matrices of graphs when seen as density matrices. This is a family of quantum states with many combinatorial properties. We firstly show that the well-known matrix realignment criterion can be used to test separability of this type of quantum states. The criterion can be interpreted as novel graph-theoretic idea. Then, we prove that the density matrix of the tensor product of N graphs is N-separable. However, the converse is not necessarily true. Additionally, we derive a sufficient condition for N-partite entanglement in star graphs and propose a necessary and sufficient condition for separability of nearest point graphs.
Greedy Trees, Subtrees and Antichains
Authors: Andriantiana Eric Ould Dadah , Wagner Stephan , Wang Hua 
Published: January 2020

Greedy trees are constructed from a given degree sequence by a simple greedy algorithm that assigns the highest degree to the root, the second-, third-, ... highest degrees to the root's neighbors, and so on. They have been shown to maximize or minimize a number of different graph invariants among trees with a given degree sequence. In particular, the total number of subtrees of a tree is maximized by the greedy tree. In this work, we show that in fact a much stronger statement holds true: greedy trees maximize the number of subtrees of any given order. This parallels recent results on distance-based graph invariants. We obtain a number of corollaries from this fact and also prove analogous results for related invariants, most notably the number of antichains of given cardinality in a rooted tree.
Ramsey Properties of Countably Infinite Partial Orderings
Authors: Groszek Marcia J. 
Published: January 2020

A partial ordering $\mathbb P$ is chain-Ramsey if, for every natural number $n$ and every coloring of the $n$-element chains from $\mathbb P$ in finitely many colors, there is a monochromatic subordering $\mathbb Q$ isomorphic to $\mathbb P$. Chain-Ramsey partial orderings stratify naturally into levels. We show that a countably infinite partial ordering with finite levels is chain-Ramsey if and only if it is biembeddable with one of a canonical collection of examples constructed from certain edge-Ramsey families of finite bipartite graphs. A similar analysis applies to a large class of countably infinite partial orderings with infinite levels.
New Aspects of Regions whose Tilings are Enumerated by Perfect Powers
Authors: Lai Tri 
Published: January 2020

In 2003, Ciucu presented a unified way to enumerate tilings of lattice regions by using a certain Reduction Theorem (J. Algebraic Combin., 2003). In this paper we continue this line of work by investigating new families of lattice regions whose tilings are enumerated by perfect powers or products of several perfect powers. We prove a multi-parameter generalization of Bo-Yin Yang's theorem on fortresses (Ph.D. thesis, MIT, 1991). On the square lattice with zigzag paths, we consider two particular families of regions whose numbers of tilings are always a power of 3 or twice a power of 3. The latter result provides a new proof for a conjecture of Matt Blum first proved by Ciucu. We also consider several new lattices obtained by periodically applying two simple subgraph replacement rules to the square lattice. On some of those lattices, we get new families of regions whose numbers of tilings are given by products of several perfect powers. In addition, we prove a simple product formula for the number of tilings of a certain family of regions on a variant of the triangular lattice.
A New Statistic on the Hyperoctahedral Groups
Authors: Stasinski Alexander , Voll Christopher 
Published: January 2020

We introduce a new statistic on the hyperoctahedral groups (Coxeter groups of type B), and give a conjectural formula for its signed distributions over arbitrary descent classes. The statistic is analogous to the classical Coxeter length function, and features a parity condition. For descent classes which are singletons the conjectured formula gives the Poincaré polynomials of the varieties of symmetric matrices of fixed rank.For several descent classes we prove the conjectural formula. For this we construct suitable supporting sets for the relevant generating functions. We prove cancellations on the complements of these supporting sets using suitably defined sign reversinginvolutions.
Remarks on a Conjecture of Barát and Tóth
Authors: Luiz Atílio G. , Richter R. Bruce 
Published: January 2020

In 2010, Barát and Tóth verified that any $r$-critical graph with at most $r+4$ vertices has a subdivision of $K_r$. Based in this result, the authors conjectured that, for every positive integer $c$, there exists a bound $r(c)$ such that for any $r$, where $r \geq r(c)$, any $r$-critical graph on $r+c$ vertices has a subdivision of $K_r$. In this note, we verify the validity of this conjecture for $c=5$, and show counterexamples for all $c \geq 6$.
Distinguishing Maps II: General Case
Authors: Tucker Thomas W. 
Published: January 2020

A group $A$ acting faithfully on a set $X$ has distinguishing number $k$, written $D(A,X)=k$, if there is a coloring of the elements of $X$ with $k$ colors such that no nonidentity element of $A$ is color-preserving, and no such coloring with fewer than $k$ colors exists. Given a map $M$ with vertex set $V$ and automorphism group $Aut(M)$, let $D(M)=D(Aut(M),V)$. If $M$ is orientable, let $D^+(M)=D(Aut^+(M),V)$, where $Aut^+(M)$ is the group of orientation-preserving automorphisms. In a previous paper, the author showed there are four maps $M$ with $D^+(M)>2$. In this paper, a complete classification is given for the graphs underlying maps with $D(M)>2$. There are $31$ such graphs, $22$ having no vertices of valence $1$ or $2$, and all have at most $10$ vertices.
Bell Numbers Modulo a Prime Number, Traces and Trinomials
Authors: Gallardo Luis H. , Rahavandrainy Olivier 
Published: January 2020

Given a prime number $p$, we deduce from a formula of Barsky and Benzaghou and from a result of Coulter and Henderson on trinomials over finite fields, a simple necessary and sufficient condition $\beta(n) =k\beta(0)$ in $\mathbb{F}_{p^p}$ in order to resolve the congruence $B(n) \equiv k \pmod{p}$, where $B(n)$ is the $n$-th Bell number, and $k$ is any fixed integer. Several applications of the formula and of the condition are included, in particular we give equivalent forms of the conjecture of Kurepa that $B(p-1)$ is $\neq 1$ modulo $p$.