bluuebunny/crossref_metadata_2025 huggingface dataset:
Semiarcs with Long Secants
Authors: Csajbók Bence
Published: January 2020

In a projective plane $\Pi_q$ of order $q$, a non-empty point set $\mathcal{S}_t$ is a $t$-semiarc if the number of tangent lines to $\mathcal{S}_t$ at each of its points is $t$. If $\mathcal{S}_t$ is a $t$-semiarc in $\Pi_q$, $t<q$, then each line intersects $\mathcal{S}_t$ in at most $q+1-t$ points. Dover proved that semiovals (semiarcs with $t=1$) containing $q$ collinear points exist in $\Pi_q$ only if $q\leq 3$. We show that if $t>1$, then $t$-semiarcs with $q+1-t$ collinear points exist only if $t\geq \sqrt{q-1}$. In $\mathrm{PG}(2,q)$ we prove the lower bound $t\geq(q-1)/2$, with equality only if $\mathcal{S}_t$ is a blocking set of Rédei type of size $3(q+1)/2$.We call the symmetric difference of two lines, with $t$ further points removed from each line, a $V_t$-configuration. We give conditions ensuring a $t$-semiarc to contain a $V_t$-configuration and give the complete characterization of such $t$-semiarcs in $\mathrm{PG}(2,q)$.
A Large Set of Torus Obstructions and How They Were Discovered
Authors: Myrvold Wendy , Woodcock Jennifer
Published: January 2020

We outline the progress made so far on the search for the complete set of torus obstructions and also consider practical algorithms for torus embedding and their implementations. We present the set of obstructions that are known to-date and give a brief history of how these graphs were found. We also describe a nice algorithm for embedding graphs on the torus which we used to verify previous results and add to the set of torus obstructions. Although it is still exponential in the order of the graph, the algorithm presented here is relatively simple to describe and implement and fast-in-practice for small graphs.It parallels the popular quadratic planar embedding algorithm of Demoucron, Malgrange, and Pertuiset.
The Largest Component in an Inhomogeneous Random Intersection Graph with Clustering
Authors: Bloznelis Mindaugas
Published: January 2020

Given integers $n$ and $m=\lfloor\beta n \rfloor$ and a probability measure $Q$ on $\{0, 1,\dots, m\}$, consider the random intersection graph on the vertex set $[n]=\{1,2,\dots, n\}$ where $i,j\in [n]$ are declared adjacent whenever $S(i)\cap S(j)\neq\emptyset$. Here $S(1),\dots, S(n)$ denote the iid random subsets of $[m]$ with the distribution $\bf{P}(S(i)=A)={{m}\choose{|A|}}^{-1}Q(|A|)$, $A\subset [m]$. For sparse random intersection graphs, we establish a first-order asymptotic as $n\to \infty$ for the order of the largest connected component $N_1=n(1-Q(0))\rho+o_P(n)$. Here $\rho$ is the average of nonextinction probabilities of a related multitype Poisson branching process.
Standard Character Condition for Table Algebras
Authors: Barghi Amir Rahnamai , Bagherian Javad
Published: January 2020

It is well known that the complex adjacency algebra $A$ of an association scheme has a specific module, namely the standard module, that contains the regular module of $A$ as a submodule. The character afforded by the standard module is called the standard character. In this paper we first define the concept of standard character for C-algebras and we say that a C-algebra has the standard character condition if it admits the standard character. Among other results we acquire a necessary and sufficient condition for a table algebra to originate from an association scheme. Finally, we prove that given a C-algebra admits the standard character and its all degrees are integers if and only if so its dual.
On Regular Hypergraphs of High Girth
Authors: Ellis David , Linial Nathan
Published: January 2020

We give lower bounds on the maximum possible girth of an $r$-uniform, $d$-regular hypergraph with at most $n$ vertices, using the definition of a hypergraph cycle due to Berge. These differ from the trivial upper bound by an absolute constant factor (viz., by a factor of between $3/2+o(1)$ and $2 +o(1)$). We also define a random $r$-uniform 'Cayley' hypergraph on the symmetric group $S_n$ which has girth $\Omega (\sqrt{\log |S_n|})$ with high probability, in contrast to random regular $r$-uniform hypergraphs, which have constant girth with positive probability.
On Sum of Powers of the Laplacian and Signless Laplacian Eigenvalues of Graphs
Authors: Akbari Saieed , Ghorbani Ebrahim , Koolen Jacobus H. , Oboudi Mohammad Reza
Published: January 2020

Let $G$ be a graph of order $n$ with signless Laplacian eigenvalues $q_1, \ldots,q_n$ and Laplacian eigenvalues $\mu_1,\ldots,\mu_n$. It is proved that for any real number $\alpha$ with $0 < \alpha\leq1$ or $2\leq\alpha < 3$, the inequality $q_1^\alpha+\cdots+ q_n^\alpha\geq \mu_1^\alpha+\cdots+\mu_n^\alpha$ holds, and for any real number $\beta$ with $1 < \beta < 2$, the inequality $q_1^\beta+\cdots+ q_n^\beta\le \mu_1^\beta+\cdots+\mu_n^\beta$ holds. In both inequalities, the equality is attained (for $\alpha \notin \{1,2\}$) if and only if $G$ is bipartite.
Generalized Line Graphs: Cartesian Products and Complexity of Recognition
Authors: Lakshmanan S. Aparna , Bujtás Csilla , Tuza Zsolt
Published: January 2020

Putting the concept of line graph in a more general setting, for a positive integer $k$, the $k$-line graph $L_k(G)$ of a graph $G$ has the $K_k$-subgraphs of $G$ as its vertices, and two vertices of $L_k(G)$ are adjacent if the corresponding copies of $K_k$ in $G$ share $k-1$ vertices. Then, 2-line graph is just the line graph in usual sense, whilst 3-line graph is also known as triangle graph. The $k$-anti-Gallai graph $\triangle_k(G)$ of $G$ is a specified subgraph of $L_k(G)$ in which two vertices are adjacent if the corresponding two $K_k$-subgraphs are contained in a common $K_{k+1}$-subgraph in $G$.We give a unified characterization for nontrivial connected graphs $G$ and $F$ such that the Cartesian product $G\Box F$ is a $k$-line graph. In particular for $k=3$, this answers the question of Bagga (2004), yielding the necessary and sufficient condition that $G$ is the line graph of a triangle-free graph and $F$ is a complete graph (or vice versa). We show that for any $k\ge 3$, the $k$-line graph of a connected graph $G$ is isomorphic to the line graph of $G$ if and only if $G=K_{k+2}$. Furthermore, we prove that the recognition problem of $k$-line graphs and that of $k$-anti-Gallai graphs are NP-complete for each $k\ge 3$.
On the Structure of Sets with Few Three-Term Arithmetic Progressions
Authors: Croot Ernie
Published: January 2020

Fix a prime $p \geq 3$, and a real number $0 < \alpha \leq 1$. Let $S \subset {\mathbb F}_p^n$ be any set with the least number of solutions to $x + y = 2z$ (note that this means that $x,z,y$ is an arithmetic progression), subject to the constraint that $|S| \geq \alpha p^n$. What can one say about the structure of such sets $S$? In this paper we show that they are "essentially" the union of a small number of cosets of some large-dimensional subspace of ${\mathbb F}_p^n$.
Enumeration of Restricted Permutation Triples
Authors: Chen Xiaojing , Chu Wenchang
Published: January 2020

The counting problem is investigated for the permutation triples of the first $n$ natural numbers with exactly $k$ occurrences of simultaneous "rises". Their recurrence relations and bivariate generating functions are established.
On Floors and Ceilings of the $k$-Catalan Arrangement
Authors: Thiel Marko
Published: January 2020

The set of dominant regions of the $k$-Catalan arrangement of a crystallographic root system $\Phi$ is a well-studied object enumerated by the Fuß-Catalan number $Cat^{(k)}(\Phi)$. It is natural to refine this enumeration by considering floors and ceilings of dominant regions. A conjecture of Armstrong states that counting dominant regions by their number of floors of a certain height gives the same distribution as counting dominant regions by their number of ceilings of the same height. We prove this conjecture using a bijection that provides even more refined enumerative information.
Small Regular Graphs of Girth 7
Authors: Abreu M. , Araujo-Pardo G. , Balbuena C. , Labbate D. , Salas J.
Published: January 2020

In this paper, we construct new infinite families of regular graphs of girth 7 of smallest order known so far. Our constructions are based on combinatorial and geometric properties of $(q+1,8)$-cages, for $q$ a prime power. We remove vertices from such cages and add matchings among the vertices of minimum degree to achieve regularity in the new graphs. We obtain $(q+1)$-regular graphs of girth 7 and order $2q^3+q^2+2q$ for each even prime power $q \ge 4$, and of order $2q^3+2q^2-q+1$ for each odd prime power $q\ge 5$. A corrigendum was added to this paper on 21 June 2016.
The Enumeration of Sequences with Restrictions on their Partial Sums
Authors: Suen Stephen , Wagner Kevin P.
Published: January 2020

We examine sequences containing $p$ "$-t$"s and $pt+r$ "$+1$"s, where $p$, $t$, and $r$ are integers satisfying $p\ge0$, $t\ge 1$ and $pt+r\ge0$. We develop a rotation method to enumerate the number of sequences meeting additional requirements related to their partial sums. We also define downcrossings about $\ell$ and their downcrossing numbers, and obtain formulas for the number of sequences for which the sum of the downcrossing numbers equals $k$, for $\ell \le r+1$. We finish with an investigation of the first downcrossing number about $\ell$, for any $\ell$.
Resolving a Conjecture on Degree of Regularity of Linear Homogeneous Equations
Authors: Golowich Noah
Published: January 2020

A linear equation is $r$-regular, if, for every $r$-coloring of the positive integers, there exist positive integers of the same color which satisfy the equation. In 2005, Fox and Radoićič conjectured that the equation $x_1 + 2x_2 + \cdots + 2^{n-2}x_{n-1} - 2^{n-1}x_n = 0$, for any $n \geq 2$, has a degree of regularity of $n-1$, which would verify a conjecture of Rado from 1933. Rado's conjecture has since been verified with a different family of equations. In this paper, we show that Fox and Radoićič's family of equations indeed have a degree of regularity of $n-1$. We also prove a few extensions of this result.
The Generating Function for Total Displacement
Authors: Guay-Paquet Mathieu , Petersen Kyle
Published: January 2020

In a 1977 paper, Diaconis and Graham studied what Knuth calls the total displacement of a permutation $w$, which is the sum of the distances $|w(i)-i|$. In recent work of the first author and Tenner, this statistic appears as twice the type $A_{n-1}$ version of a statistic for Coxeter groups called the  depth of $w$. There are various enumerative results for this statistic in the work of Diaconis and Graham, codified as exercises in Knuth's textbook, and some other results in the work of Petersen and Tenner. However, no formula for the generating function of this statistic appears in the literature. Knuth comments that "the generating function for total displacement does not appear to have a simple form." In this paper, we translate the problem of computing the distribution of total displacement into a problem of counting weighted Motzkin paths. In this way, standard techniques allow us to express the generating function for total displacement as a continued fraction.
Contractible Edges in 2-Connected Locally Finite Graphs
Authors: Chan Tsz Lung
Published: January 2020

In this paper, we prove that every contraction-critical 2-connected infinite graph has no vertex of finite degree and contains uncountably many ends. Then, by investigating the distribution of contractible edges in a 2-connected locally finite infinite graph $G$, we show that the closure of the subgraph induced by all the contractible edges in the Freudenthal compactification of $G$ is 2-arc-connected. Finally, we characterize all 2-connected locally finite outerplanar graphs nonisomorphic to $K_3$ as precisely those graphs such that every vertex is incident to exactly two contractible edges as well as those graphs such that every finite bond contains exactly two contractible edges.
Honeycomb Arrays
Authors: Blackburn Simon R. , Panoui Anastasia , Paterson Maura B. , Stinson Douglas R.
Published: January 2020

A honeycomb array is an analogue of a Costas array in the hexagonal grid; they were first studied by Golomb and Taylor in 1984. A recent result of Blackburn, Etzion, Martin and Paterson has shown that (in contrast to the situation for Costas arrays) there are only finitely many examples of honeycomb arrays, though their bound on the maximal size of a honeycomb array is too large to permit an exhaustive search over all possibilities. The present paper contains a theorem that significantly limits the number of possibilities for a honeycomb array (in particular, the theorem implies that the number of dots in a honeycomb array must be odd). Computer searches for honeycomb arrays are summarised, and two new examples of honeycomb arrays with 15 dots are given.
Linear Programming and the Worst-Case Analysis of Greedy Algorithms on Cubic Graphs
Authors: Duckworth W. , Wormald N.
Published: January 2020

We introduce a technique using linear programming that may be used to analyse the worst-case performance of a class of greedy heuristics for certain optimisation problems on regular graphs. We demonstrate the use of this technique on heuristics for bounding the size of a minimum maximal matching (MMM), a minimum connected dominating set (MCDS) and a minimum independent dominating set (MIDS) in cubic graphs. We show that for $n$-vertex connected cubic graphs, the size of an MMM is at most $9n/20+O(1)$, which is a new result. We also show that the size of an MCDS is at most $3n/4+O(1)$ and the size of a MIDS is at most $29n/70+O(1)$. These results are not new, but earlier proofs involved rather long ad-hoc arguments. By contrast, our method is to a large extent automatic and can apply to other problems as well. We also consider $n$-vertex connected cubic graphs of girth at least 5 and for such graphs we show that the size of an MMM is at most $3n/7+O(1)$, the size of an MCDS is at most $2n/3+O(1)$ and the size of a MIDS is at most $3n/8+O(1)$.
A Generalization of the $k$-Bonacci Sequence from Riordan Arrays
Authors: Ramírez José L. , Sirvent Víctor F.
Published: January 2020

In this article, we introduce  a family of weighted lattice paths, whose step set is $\{H=(1,0), V=(0,1), D_1=(1,1), \dots, D_{m-1}=(1,m-1)\}$. Using these lattice paths, we define a family of Riordan arrays whose sum on the rising diagonal is the $k$-bonacci sequence. This construction generalizes the Pascal and Delannoy Riordan arrays, whose sum on the rising diagonal is the Fibonacci and tribonacci sequence, respectively.  From this family of Riordan arrays we introduce a generalized $k$-bonacci polynomial sequence, and we give a lattice path combinatorial interpretation of these polynomials. In particular, we find a combinatorial interpretation of tribonacci and tribonacci-Lucas polynomials.
Elementary Proofs for Convolution Identities of Abel and Hagen–Rothe
Authors: Chu Wenchang
Published: January 2020

By means of series–rearrangements and finite differences, elementary proofs are presented for the well–known convolution identities of Abel and Hagen–Rothe.
Uniform Mixing and Association Schemes
Authors: Godsil Chris , Mullin Natalie , Roy Aidan
Published: January 2020

We consider continuous-time quantum walks on distance-regular graphs. Using results about the existence of complex Hadamard matrices in association schemes, we determine which of these graphs have quantum walks that admit uniform mixing.First we apply a result due to Chan to show that the only strongly regular graphs that admit instantaneous uniform mixing are the Paley graph of order nine and certain graphs corresponding to regular symmetric Hadamard matrices with constant diagonal. Next we prove that if uniform mixing occurs on a bipartite graph $X$ with $n$ vertices, then $n$ is divisible by four. We also prove that if $X$ is bipartite and regular, then $n$ is the sum of two integer squares. Our work on bipartite graphs implies that uniform mixing does not occur on $C_{2m}$ for $m \geq 3$. Using a result of Haagerup, we show that uniform mixing does not occur on $C_p$ for any prime $p$ such that $p \geq 5$. In contrast to this result, we see that $\epsilon$-uniform mixing occurs on $C_p$ for all primes $p$.
Local Probabilities for Random Permutations Without Long Cycles
Authors: Manstavičius Eugenijus , Petuchovas Robertas
Published: January 2020

We explore the probability $\nu(n,r)$ that a permutation sampled from the symmetric group of order $n!$ uniformly at random has no cycles of length exceeding $r$, where  $1\leq r\leq n$ and $n\to\infty$. Asymptotic formulas valid in specified regions for the ratio $n/r$ are obtained using the saddle-point method combined with ideas originated in analytic number theory.
On a Conjecture of Thomassen
Authors: Delcourt Michelle , Ferber Asaf
Published: January 2020

In 1989, Thomassen asked whether there is an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph. In this paper we take a first, humble approach, showing the conjecture is true up to a $\log n$ factor.
Exact Forbidden Subposet Results using Chain Decompositions of the Cycle
Authors: Methuku Abhishek , Tompkins Casey
Published: January 2020

We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of $[n]$ not containing one or more given posets as a subposet.   De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.
On Shuffling of Infinite Square-Free Words
Authors: Müller Mike , Puzynina Svetlana , Rao Michaël
Published: January 2020

In this paper we answer two recent questions from Charlier et al. (2014) and Harju (2013) about self-shuffling words. An infinite word $w$ is called self-shuffling, if $w=\prod_{i=0}^\infty U_iV_i=\prod_{i=0}^\infty U_i=\prod_{i=0}^\infty V_i$ for some finite words $U_i$, $V_i$. Harju recently asked whether square-free self-shuffling words exist. We answer this question affirmatively. Besides that, we build an infinite word such that no word in its shift orbit closure is self-shuffling, answering positively a question of E. Charlier et al.
Generalized Small Schröder Numbers
Authors: Huh JiSun , Park SeungKyung
Published: January 2020

We study generalized small Schröder paths in the sense of arbitrary sizes of steps. A generalized small Schröder path is a generalized lattice path from $(0,0)$ to $(2n,0)$ with the step set of  $\{(k,k), (l,-l), (2r,0)\, |\, k,l,r \in {\bf P}\}$, where ${\bf P}$ is the set of positive integers, which never goes below the $x$-axis, and with no horizontal steps at level 0.  We find a bijection between 5-colored Dyck paths and generalized small Schröder paths, proving that the number of generalized small Schröder paths is equal to $\sum_{k=1}^{n} N(n,k)5^{n-k}$ for $n\geq 1$.
The Minimum Size of Signed Sumsets
Authors: Bajnok Béla , Matzke Ryan
Published: January 2020

For a finite abelian group $G$ and positive integers $m$ and $h$, we let $$\rho(G, m, h) = \min \{ |hA| \; : \; A \subseteq G, |A|=m\}$$ and$$\rho_{\pm} (G, m, h) = \min \{ |h_{\pm} A| \; : \; A \subseteq G, |A|=m\},$$ where $hA$ and $h_{\pm} A$ denote the $h$-fold sumset and the $h$-fold signed sumset of $A$, respectively. The study of $\rho(G, m, h)$ has a 200-year-old history and is now known for all $G$, $m$, and $h$. Here we prove that $\rho_{\pm}(G, m, h)$ equals $\rho (G, m, h)$ when $G$ is cyclic, and establish an upper bound for $\rho_{\pm} (G, m, h)$ that we believe gives the exact value for all $G$, $m$, and $h$.
Simplicial Complexes of Whisker Type
Authors: Bigdeli Mina , Herzog Jürgen , Hibi Takayuki , Macchia Antonio
Published: January 2020

Let $I\subset K[x_1,\ldots,x_n]$ be  a zero-dimensional monomial ideal, and $\Delta(I)$ be the simplicial complex whose Stanley--Reisner ideal is the polarization of $I$. It follows from a result of Soleyman Jahan that $\Delta(I)$ is shellable. We give a new short proof of this fact by providing an explicit shelling. Moreover, we show that  $\Delta(I)$ is even vertex decomposable. The ideal $L(I)$, which is defined to be the Stanley--Reisner ideal of the Alexander dual of $\Delta(I)$, has a linear resolution which is cellular and supported on a regular CW-complex. All powers of $L(I)$ have a linear resolution. We compute $\mathrm{depth}\ L(I)^k$ and show that $\mathrm{depth}\ L(I)^k=n$ for all $k\geq n$.
On the Number of Matroids Compared to the Number of Sparse Paving Matroids
Authors: Pendavingh Rudi , Van der Pol Jorn
Published: January 2020

It has been conjectured that sparse paving matroids will eventually predominate in any asymptotic enumeration of matroids, i.e. that $\lim_{n\rightarrow\infty} s_n/m_n = 1$, where $m_n$ denotes the number of matroids on $n$ elements, and $s_n$ the number of sparse paving matroids. In this paper, we show that $$\lim_{n\rightarrow \infty}\frac{\log s_n}{\log m_n}=1.$$ We prove this by arguing that each matroid on $n$ elements has a faithful description consisting of a stable set of a Johnson graph together with a (by comparison) vanishing amount of other information, and using that stable sets in these Johnson graphs correspond one-to-one to sparse paving matroids on $n$ elements.As a consequence of our result, we find that for all $\beta > \displaystyle{\sqrt{\frac{\ln 2}{2}}} = 0.5887\cdots$, asymptotically almost all matroids on $n$ elements have rank in the range $n/2 \pm \beta\sqrt{n}$.
Dimensions of the Irreducible Representations of the Symmetric and Alternating Group
Authors: Debaene Korneel
Published: January 2020

We establish the existence of an irreducible representation of $A_n$ whose dimension does not occur as the dimension of an irreducible representation of $S_n$, and vice versa. This proves a conjecture by Tong-Viet. The main ingredient in the proof is a result on large prime factors in short intervals.
A Bijection between Atomic Partitions and Unsplitable Partitions
Authors: Chen William Y. C. , Li Teresa X. S. , Wang David G. L.
Published: January 2020

In the study of the algebra $\mathrm{NCSym}$ of symmetric functions in noncommutative variables, Bergeron and Zabrocki found a free generating set consisting of power sum symmetric functions indexed by atomic partitions. On the other hand, Bergeron, Reutenauer, Rosas, and Zabrocki studied another free generating set of $\mathrm{NCSym}$ consisting of monomial symmetric functions indexed by unsplitable partitions. Can and Sagan raised the question of finding a bijection between atomic partitions and unsplitable partitions. In this paper, we provide such a bijection.
A Class of Infinite Convex Geometries
Authors: Adaricheva Kira , Nation J. B.
Published: January 2020

Various characterizations of finite convex geometries are well known. This note provides similar characterizations for possibly infinite convex geometries whose lattice of closed sets is strongly coatomic and lower continuous. Some classes of examples of such convex geometries are given.
The Topology of the External Activity Complex of a Matroid
Authors: Ardila Federico , Castillo Federico , Samper José Alejandro
Published: January 2020

We prove that the external activity complex $\textrm{Act}_<(M)$ of a matroid is shellable. In fact, we show that every linear extension of LasVergnas's external/internal order $<_{ext/int}$ on $M$ provides a shelling of $\textrm{Act}_<(M)$. We also show that every linear extension of LasVergnas's internal order $<_{int}$ on $M$ provides a shelling of the independence complex $IN(M)$. As a corollary, $\textrm{Act}_<(M)$ and $M$ have the same $h$-vector. We prove that, after removing its cone points, the external activity complex is contractible if $M$ contains $U_{1,3}$ as a minor, and a sphere otherwise.
An Improved Bound on the Sizes of Matchings Guaranteeing a Rainbow Matching
Authors: Clemens Dennis , Ehrenmüller Julia
Published: January 2020

A conjecture by Aharoni and Berger states that every family of $n$ matchings of size $n+1$ in a bipartite multigraph contains a rainbow matching of size $n$. In this paper we prove that matching sizes of $\left(\frac 3 2 + o(1)\right) n$ suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size $n-1$. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.
A Disproof of Tsallis' Bond Percolation Threshold Conjecture for the Kagome Lattice
Authors: Wierman John C. , Yu Gaoran , Huang Theodore
Published: January 2020

In 1982, Tsallis derived a formula which proposed an exact value of 0.522372078... for the bond percolation threshold of the kagome lattice. We use the substitution method, which is based on stochastic ordering, to compare the probability distribution of connections in the homogeneous bond percolation model on the kagome lattice to those of an exactly-solved inhomogeneous bond percolation model on the martini lattice. The bounds obtained are $0.522394<p_c(\mbox{kagome}) < 0.526750$, where the lower bound shows that the value conjectured by Tsallis is incorrect.
Isotropic Matroids I: Multimatroids and Neighborhoods
Authors: Brijder Robert , Traldi Lorenzo
Published: January 2020

Several properties of the isotropic matroid of a looped simple graph are presented. Results include a characterization of the multimatroids that are associated with isotropic matroids and several ways in which the isotropic matroid of $G$ incorporates information about graphs locally equivalent to $G$. Specific results of the latter type include a characterization of graphs that are locally equivalent to bipartite graphs, a direct proof that two forests are isomorphic if and only if their isotropic matroids are isomorphic, and a way to express local equivalence indirectly, using only edge pivots.
Posets of Finite Functions
Authors: Pióro Konrad
Published: January 2020

The symmetric group $ S(n) $ is partially ordered by Bruhat order. This order is extended by L. Renner to the set of partial injective functions of $ \{ 1, 2, \ldots, n \} $ (see, Linear Algebraic Monoids, Springer, 2005). This poset is investigated by M. Fortin in his paper The MacNeille Completion of the Poset of Partial Injective Functions [Electron. J. Combin., 15, R62, 2008]. In this paper we show that Renner order can be also defined for sets of all functions, partial functions, injective and partial injective functions from $ \{ 1, 2, \ldots, n \} $ to $ \{ 1, 2, \ldots, m \} $. Next, we generalize Fortin's results on these posets, and also, using simple facts and methods of linear algebra, we give simpler and shorter proofs of some fundamental Fortin's results. We first show that these four posets can be order embedded in the set of $ n \times m $-matrices with non-negative integer entries and with the natural componentwise order. Second, matrix representations of the Dedekind-MacNeille completions of our posets are given. Third, we find join- and meet-irreducible elements for every finite sublattice of the lattice of all $ n \times m $-matrices with integer entries. In particular, we obtain join- and meet-irreducible elements of these Dedekind-MacNeille completions. Hence and by general results concerning Dedekind-MacNeille completions, join- and meet-irreducible elements of our four posets of functions are also found. Moreover, subposets induced by these irreducible elements are precisely described.
Chordality Properties and Hyperbolicity on Graphs
Authors: Martínez-Pérez Álvaro
Published: January 2020

Let $G$ be a graph with the usual shortest-path metric. A graph is $\delta$-hyperbolic if for every geodesic triangle $T$, any side of $T$ is contained in a $\delta$-neighborhood of the union of the other two sides. A graph is chordal if every induced cycle has at most three edges. In this paper we study the relation between the hyperbolicity of the graph and some chordality properties which are natural generalizations of being chordal. We find chordality properties that are weaker and stronger than being $\delta$-hyperbolic. Moreover, we obtain a characterization of being hyperbolic on terms of a chordality property on the triangles.
Average Degree Conditions Forcing a Minor
Authors: Harvey Daniel J. , Wood David R.
Published: January 2020

Mader first proved that high average degree forces a given graph as a minor. Often motivated by Hadwiger's Conjecture, much research has focused on the average degree required to force a complete graph as a minor. Subsequently, various authors have considered the average degree required to force an arbitrary graph $H$ as a minor. Here, we strengthen (under certain conditions) a recent result by Reed and Wood, giving better bounds on the average degree required to force an $H$-minor when $H$ is a sparse graph with many high degree vertices. This solves an open problem of Reed and Wood, and also generalises (to within a constant factor) known results when $H$ is an unbalanced complete bipartite graph.
A Note on Maxima in Random Walks
Authors: Helfer Joseph , Wise Daniel T.
Published: January 2020

We give a combinatorial proof that a random walk attains a unique maximum with probability at least $1/2$. For closed random walks with uniform step size, we recover Dwass's count of the number of length $\ell$ walks attaining the maximum exactly $k$ times. We also show that the probability that there is both a unique maximum and a unique minimum is asymptotically equal to $\frac14$ and that the probability that a Dyck word has a unique minimum is asymptotically $\frac12$.
Reconstructing Permutations from Identification Minors
Authors: Lehtonen Erkko
Published: January 2020

We consider the problem whether a permutation of a finite set is uniquely determined by its identification minors. While there exist non-reconstructible permutations of every set with two, three, or four elements, we show that every permutation of a finite set with at least five elements is reconstructible from its identification minors. Moreover, we provide an algorithm for recovering a permutation from its deck. We also discuss a generalization of this reconstruction problem, as well as the related set-reconstruction problem.
The Complexity of Obtaining a Distance-Balanced Graph
Authors: Cabello Sergio , Lukšič Primož
Published: January 2020

An unweighted, connected graph is distance-balanced (also called self-median) if there exists a number $d$ such that, for any vertex $v$, the sum of the distances from $v$ to all other vertices is $d$. An unweighted connected graph is strongly distance-balanced (also called distance-degree regular) if there exist numbers $d_1,d_2,d_3,\dots$ such that, for any vertex $v$, there are precisely $d_k$ vertices at distance $k$ from $v$. We consider the following optimization problem: given a graph, add the minimum possible number of edges to obtain a (strongly) distance-balanced graph. We show that the problem is NP-hard for graphs of diameter three, thus answering the question posed by Jerebic et al. [Distance-balanced graphs; Ann. Comb. 2008]. In contrast, we show that the problem can be solved in polynomial time for graphs of diameter 2.
Lattices Related to Extensions of Presentations of Transversal Matroids
Authors: Bonin Joseph E.
Published: January 2020

For a presentation $\mathcal{A}$ of a transversal matroid $M$, we study the ordered set $T_{\mathcal{A}}$ of single-element transversal extensions of $M$ that have presentations that extend $\mathcal{A}$; extensions are ordered by the weak order.  We show that $T_{\mathcal{A}}$ is a distributive lattice, and that each finite distributive lattice is isomorphic to $T_{\mathcal{A}}$ for some presentation $\mathcal{A}$ of some transversal matroid $M$. We show that $T_{\mathcal{A}}\cap T_{\mathcal{B}}$, for any two presentations $\mathcal{A}$ and $\mathcal{B}$ of $M$, is a sublattice of both $T_{\mathcal{A}}$ and $T_{\mathcal{B}}$. We prove sharp upper bounds on $|T_{\mathcal{A}}|$ for presentations $\mathcal{A}$ of rank less than $r(M)$ in the order on presentations; we also give a sharp upper bound on $|T_{\mathcal{A}}\cap T_{\mathcal{B}}|$. The main tool we introduce to study $T_{\mathcal{A}}$ is the lattice $L_{\mathcal{A}}$ of closed sets of a certain closure operator on the lattice of subsets of $\{1,2,\ldots,r(M)\}$.
Extended Formulation for CSP that is Compact for Instances of Bounded Treewidth
Authors: Kolman Petr , Koutecký Martin
Published: January 2020

In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.
A New Lower Bound for the Towers of Hanoi Problem
Authors: Grosu Codruƫ
Published: January 2020

More than a century after its proposal, the Towers of Hanoi puzzle with 4 pegs was solved by Thierry Bousch in a breakthrough paper in 2014. The general problem with $p$ pegs is still open, with the best lower bound on the minimum number of moves due to Chen and Shen. We use some of Bousch's new ideas to obtain an asymptotic improvement on this bound for all $p \geq 5$.
A Chip-Firing Game on the Product of Two Graphs and the Tropical Picard Group
Authors: Lazar Alexander
Published: January 2020

Cartwright (2015) introduced the notion of a weak tropical complex in order to generalize the theory of divisors on graphs from Baker and Norine (2007). A weak tropical complex $\Gamma$ is a $\Delta$-complex equipped with algebraic data that allows it to be viewed as the dual complex to a certain kind of degeneration over a discrete valuation ring. Every graph has a unique tropical complex structure (which is the same structure studied by Baker and Norine) in which divisors correspond to states in the chip-firing game on that graph. Let $G$ and $H$ be graphs, and let $\Gamma$ be a triangulation of $G\times H$ obtained by adding in one diagonal of each resulting square. There is a particular weak tropical complex structure on $\Gamma$ that Cartwright conjectured was closely related to the weak tropical complex structures on $G$ and $H$. The main result of this paper is a proof of Cartwright's conjecture. In preparation, we discuss some basic properties of tropical complexes, along with some properties specific to the product-of-graphs case.
Flag Statistics from the Ehrhart $h^∗$-Polynomial of Multi-Hypersimplices
Authors: Han Guo-Niu , Josuat-Vergès Matthieu
Published: January 2020

It is known that the normalized volume of standard hypersimplices (defined as some slices of the unit hypercube) are the Eulerian numbers. More generally, a recent conjecture of Stanley relates the Ehrhart series of hypersimplices with descents and excedences in permutations. This conjecture was proved by Nan Li, who also gave a generalization to colored permutations. In this article, we give another generalization to colored permutations, using the flag statistics introduced by Foata and Han. We obtain in particular a new proof of Stanley’s conjecture, and some combinatorial identities relating pairs of Eulerian statistics on colored permutations.
Szemerédi's Regularity Lemma via Martingales
Authors: Dodos Pandelis , Kanellopoulos Vassilis , Karageorgos Thodoris
Published: January 2020

We prove a variant of the abstract probabilistic version of Szemerédi's regularity lemma, due to Tao, which applies to a number of structures (including graphs, hypergraphs, hypercubes, graphons, and many more) and works for random variables in $L_p$ for any $p>1$. Our approach is based on martingale difference sequences.
Relative Difference Sets Partitioned by Cosets
Authors: Dukes Peter J. , Ling Alan C.H.
Published: January 2020

We explore classical (relative) difference sets intersected with the cosets of a subgroup of small index. The intersection sizes are governed by quadratic Diophantine equations. Developing the intersections in the subgroup yields an interesting class of group divisible designs. From this and the Bose-Shrikhande-Parker construction, we obtain some new sets of mutually orthogonal latin squares. We also briefly consider optical orthogonal codes and difference triangle systems.
On Mixed Almost Moore Graphs of Diameter Two
Authors: López Nacho , Miret Josep M.
Published: January 2020

Mixed almost Moore graphs appear in the context of the Degree/Diameter problem as a class of extremal mixed graphs, in the sense that their order is one less than the Moore bound for mixed graphs. The problem of their existence has been considered before for directed graphs and undirected ones, but not for the mixed case, which is a kind of generalization. In this paper we give some necessary conditions for the existence of mixed almost Moore graphs of diameter two derived from the factorization in $\mathbb{Q}[x]$ of their characteristic polynomial. In this context, we deal with the irreducibility of $\Phi_i(x^2+x-(r-1))$, where $\Phi_i(x)$ denotes the i-th cyclotomic polynomial.
On Generalizations of Separating and Splitting Families
Authors: Condon Daniel , Coskey Samuel , Serafin Luke , Stockdale Cody
Published: January 2020

Starting from the well-established notion of a separating family (or separating system) and the refinement known as a splitting family, we define and study generalizations called $n$-separating and $n$-splitting families, obtaining lower and upper bounds on their minimum sizes. For $n$-separating families our bounds are asymptotically tight within a linear factor, while for $n$-splitting families we provide partial results and open questions.
Cyclic Sieving and Rational Catalan Theory
Authors: Bodnar Michelle , Rhoades Brendon
Published: January 2020

Let $a < b$ be coprime positive integers. Armstrong, Rhoades, and Williams (2013) defined a set NC(a,b) of `rational noncrossing partitions', which form a subset of the ordinary noncrossing partitions of $\{1, 2, \dots, b-1\}$.  Confirming a conjecture of Armstrong et. al., we prove that NC(a,b) is closed under rotation and prove an instance of the cyclic sieving phenomenon for this rotational action.  We also define a rational generalization of the $\mathfrak{S}_a$-noncrossing parking functions of Armstrong, Reiner, and Rhoades.
New Conjectures for Union-Closed Families
Authors: Pulaj Jonad , Raymond Annie , Theis Dirk
Published: January 2020

The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets. From an optimization point of view, one could instead prove that $2a$ is an upper bound to the number of sets in a union-closed family on a ground set of $n$ elements where each element is in at most $a$ sets for all $a,n\in \mathbb{N}^+$. Similarly, one could prove that the minimum number of sets containing the most frequent element in a (non-empty) union-closed family with $m$ sets and $n$ elements is at least $\frac{m}{2}$ for any $m,n\in \mathbb{N}^+$. Formulating these problems as integer programs, we observe that the optimal values we computed do not vary with $n$. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we prove special cases of the new conjectures and discuss possible approaches to solve them completely.
Pruned Double Hurwitz Numbers
Authors: Hahn Marvin Anas
Published: January 2020

Hurwitz numbers count ramified genus $g$, degree $d$ coverings of the projective line with fixed branch locus and fixed ramification data. Double Hurwitz numbers count such covers, where we fix two special profiles over $0$ and $\infty$ and only simple ramification else. These objects feature interesting structural behaviour and connections to geometry. In this paper, we introduce the notion of pruned double Hurwitz numbers, generalizing the notion of pruned simple Hurwitz numbers in Do and Norbury. We show that pruned double Hurwitz numbers, similar to usual double Hurwitz numbers, satisfy a cut-and-join recursion and are piecewise polynomial with respect to the entries of the two special ramification profiles. Furthermore, double Hurwitz numbers can be computed from pruned double Hurwitz numbers. To sum up, it can be said that pruned double Hurwitz numbers count a relevant subset of covers, leading to considerably smaller numbers and computations, but still featuring the important properties we can observe for double Hurwitz numbers.
Proof of Gessel's $\gamma$-Positivity Conjecture
Authors: Lin Zhicong
Published: January 2020

We prove a conjecture of Gessel, which asserts that the joint distribution of descents and inverse descents on permutations has a fascinating refined $\gamma$-positivity.
Directed Rooted Forests in Higher Dimension
Authors: Bernardi Olivier , Klivans Caroline J.
Published: January 2020

For a graph $G$, the generating function of rooted forests, counted by the number of connected components, can be expressed in terms of the eigenvalues of the graph Laplacian. We generalize this result from graphs to cell complexes of arbitrary dimension. This requires generalizing the notion of rooted forest to higher dimension. We also introduce orientations of higher dimensional rooted trees and forests. These orientations are discrete vector fields which lead to open questions concerning expressing homological quantities combinatorially.
On Almost-Regular Edge Colourings of Hypergraphs
Authors: Bryant Darryn
Published: January 2020

We prove that if ${\cal{H}}=(V({\cal{H}}),{\cal{E}}({\cal{H}}))$ is a hypergraph, $\gamma$ is an edge colouring of ${\cal{H}}$, and $S\subseteq V({\cal{H}})$ such that any permutation of $S$ is an automorphism of ${\cal{H}}$, then there exists a permutation $\pi$ of ${\cal{E}}({\cal{H}})$ such that $|\pi(E)|=|E|$ and $\pi(E)\setminus S=E\setminus S$ for each $E\in{\cal{H}}({\cal{H}})$, and such that the edge colouring $\gamma'$ of ${\cal{H}}$ given by $\gamma'(E)=\gamma(\pi^{-1}(E))$ for each $E\in{\cal{E}}({\cal{H}})$ is almost regular on $S$. The proof is short and elementary. We show that a number of known results, such as Baranyai's Theorem on almost-regular edge colourings of complete $k$-uniform hypergraphs, are easy corollaries of this theorem.
Incidences with Curves in $\mathbb{R}^d$
Authors: Sharir Micha , Sheffer Adam , Solomon Noam
Published: January 2020

We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in ${\mathbb R}^d$ is\[ O\left(m^{\frac{k}{dk-d+1}+\varepsilon}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\varepsilon}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}} q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right),\]for any $\varepsilon>0$, where the constant of proportionality depends on $k, \varepsilon$ and $d$, provided that no $j$-dimensional surface of degree $\le c_j(k,d,\varepsilon)$, a constant parameter depending on $k$, $d$, $j$, and $\varepsilon$, contains more than $q_j$ input curves, and that the $q_j$'s satisfy certain mild conditions. This bound generalizes the well-known planar incidence bound of Pach and Sharir to $\mathbb{R}^d$. It generalizes a recent result of Sharir and Solomon concerning point-line incidences in four dimensions (where d=4 and k=2), and partly generalizes a recent result of Guth (as well as the earlier bound of Guth and Katz) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$). It also improves a recent d-dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in high-dimensional spaces. Our bound is not known to be tight in most cases.
Minimal Obstructions for Partial Representations of Interval Graphs
Authors: Klavik Pavel , Saumell Maria
Published: January 2020

Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals.  We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.
Variations on a theme of Kasteleyn, with Application to the Totally Nonnegative Grassmannian
Authors: Speyer David E
Published: January 2020

We provide a short proof of a classical result of Kasteleyn, and prove several variants thereof. One of these results has become key in the parametrization of positroid varieties, and thus deserves the short direct proof which we provide.
Recurrence Relations for the Linear Transformation Preserving the Strong $q$-Log-Convexity
Authors: Liu Lily Li , Li Ya-Nan
Published: January 2020

Let $[T(n,k)]_{n,k\geqslant0}$ be a triangle of positive numbers satisfying the three-term recurrence relation\[T(n,k)=(a_1n+a_2k+a_3)T(n-1,k)+(b_1n+b_2k+b_3)T(n-1,k-1).\]In this paper, we give a new sufficient condition for linear transformations\[Z_n(q)=\sum_{k=0}^{n}T(n,k)X_k(q)\]that preserves the strong $q$-log-convexity of polynomials sequences. As applications, we show linear transformations, given by matrices of the binomial coefficients, the Stirling numbers of the first kind and second kind, the Whitney numbers of the first kind and second kind, preserving the strong $q$-log-convexity in a unified manner.
Unimodality via Alternating Gamma Vectors
Authors: Brittenham Charles , Carroll Andrew T. , Petersen T. Kyle , Thomas Connor
Published: January 2020

For a polynomial with palindromic coefficients, unimodality is equivalent to having a nonnegative $g$-vector. A sufficient condition for unimodality is having a nonnegative $\gamma$-vector, though one can have negative entries in the $\gamma$-vector and still have a nonnegative $g$-vector.In this paper we provide combinatorial models for three families of $\gamma$-vectors that alternate in sign. In each case, the $\gamma$-vectors come from unimodal polynomials with straightforward combinatorial descriptions, but for which there is no straightforward combinatorial proof of unimodality. By using the transformation from $\gamma$-vector to $g$-vector, we express the entries of the $g$-vector combinatorially, but as an alternating sum. In the case of the $q$-analogue of $n!$, we use a sign-reversing involution to interpret the alternating sum, resulting in a manifestly positive formula for the $g$-vector. In other words, we give a combinatorial proof of unimodality. We consider this a "proof of concept" result that we hope can inspire a similar result for the other two cases, $\prod_{j=1}^n (1+q^j)$ and the $q$-binomial coefficient ${n\brack k}$.
Treelike Snarks
Authors: Abreu Marién , Kaiser Tomáš , Labbate Domenico , Mazzuoccolo Giuseppe
Published: January 2020

We study snarks whose edges cannot be covered by fewer than five perfect matchings. Esperet and Mazzuoccolo found an infinite family  of such snarks, generalising an example provided by Hägglund. We  construct another infinite family, arising from a generalisation in a different direction. The proof that this family has the requested property is computer-assisted. In addition, we prove that the snarks from this family (we call them treelike snarks) have circular flow number $\phi_C (G)\ge5$ and admit a 5-cycle double cover.