bluuebunny/crossref_metadata_2025_split huggingface dataset:
On Computation of Baker and Norine’s Rank on Complete Graphs
Authors: Cori Robert , Le Borgne Yvan 
Published: January 2020

The paper by M. Baker and S. Norine in 2007 introduced a new parameter on configurations of graphs and gave a new result in the theory of graphs which has an algebraic geometry flavor. This result was called Riemann-Roch formula for graphs since it defines a combinatorial version of divisors and their ranks in terms of configurations on graphs. The so called chip firing game on graphs and the sandpile model in physics play a central role in this theory. In this paper we present an algorithm for the determination of the rank of configurations for the complete graph $K_n$. This algorithm has linear arithmetic complexity. The analysis of number of iterations in a less optimized version of this algorithm leads to an apparently new parameter which we call the prerank. This parameter and the parameter dinv provide an alternative description to some well known $q,t$-Catalan numbers. Restricted to a natural subset of configurations, the two natural statistics degree and rank lead to a distribution which is described by a generating function which, up to a change of variables and a rescaling, is a symmetric fraction involving two copies of Carlitz $q$-analogue of the Catalan numbers. In annex, we give an alternative presentation of the theorem of Baker and Norine in purely combinatorial terms.
A Construction of Small $(q-1)$-Regular Graphs of Girth 8
Authors: Abreu M. , Araujo-Pardo G. , Balbuena C. , Labbate D. 
Published: January 2020

In this note we construct a new infinite family of $(q-1)$-regular graphs of girth 8 and order $2q(q-1)^2$ for all prime powers $q\geq 16$, which are the smallest known so far whenever $q-1$ is not a prime power or a prime power plus one itself.
On the Game Domination Number of Graphs with Given Minimum Degree
Authors: Bujtás Csilla 
Published: January 2020

In the domination game, introduced by Brešar, Klavžar, and Rall in 2010, Dominator and Staller alternately select a vertex of a graph $G$. A move is legal if the selected vertex $v$ dominates at least one new vertex – that is, if we have a $u\in N[v]$ for which no vertex from $N[u]$ was chosen up to this point of the game. The game ends when no more legal moves can be made, and its length equals the number of vertices selected. The goal of Dominator is to minimize whilst that of Staller is to maximize the length of the game. The game domination number $\gamma_g(G)$ of $G$ is the length of the domination game in which Dominator starts and both players play optimally. In this paper we establish an upper bound on $\gamma_g(G)$ in terms of the minimum degree $\delta$ and the order $n$ of $G$. Our main result states that for every $\delta \ge 4$,$$\gamma_g(G)\le \frac{15\delta^4-28\delta^3-129\delta^2+354\delta-216}{45\delta^4-195\delta^3+174\delta^2+174\delta-216}\; n.$$Particularly, $\gamma_g(G) < 0.5139\; n$ holds for every graph of minimum degree 4, and $\gamma_g(G) < 0.4803\; n$ if the minimum degree is greater than 4. Additionally, we prove that $\gamma_g(G) < 0.5574\; n$ if $\delta=3$.
On Edge-Transitive Graphs of Square-Free Order
Authors: Li Cai Heng , Lu Zai Ping , Wang Gai Xia 
Published: January 2020

We study the class of edge-transitive graphs of square-free order and valency at most $k$. It is shown that, except for a few special families of graphs, only finitely many members in this class are basic (namely, not a normal multicover of another member). Using this result, we determine the automorphism groups of locally primitive arc-transitive graphs with square-free order.
On Cylindrical Graph Construction and its Applications
Authors: Daneshgar Amir , Hejrati Mohsen , Madani Meysam 
Published: January 2020

In this article we introduce the cylindrical construction, as an edge-replacement procedure admitting twists on both ends of the hyperedges, generalizing the concepts of lifts and Pultr templates at the same time. We prove a tensor-hom duality for this construction and we show that not only a large number of well-known graph constructions are cylindrical but also the construction and its dual give rise to some new graph constructions, applications and results. To show the applicability of the main duality we introduce generalized Grötzsch, generalized Petersen-like and Coxeter-like graphs and we prove some coloring properties of these graphs.
Between 2- and 3-Colorability
Authors: Frieze Alan , Pegden Wesley 
Published: January 2020

We consider the question of the existence of homomorphisms between $G_{n,p}$ and odd cycles when $p=c/n$, $1<c\leq 4$. We show that for any positive integer $\ell$, there exists $\epsilon=\epsilon(\ell)$ such that if $c=1+\epsilon$ then w.h.p. $G_{n,p}$ has a homomorphism from $G_{n,p}$ to $C_{2\ell+1}$ so long as its odd-girth is at least $2\ell+1$. On the other hand, we show that if $c=4$ then w.h.p. there is no homomorphism from $G_{n,p}$ to $C_5$. Note that in our range of interest, $\chi(G_{n,p})=3$ w.h.p., implying that there is a homomorphism from $G_{n,p}$ to $C_3$. These results imply the existence of random graphs with circular chromatic numbers $\chi_c$ satisfying $2<\chi_c(G)<2+\delta$ for arbitrarily small $\delta$, and also that $2.5\leq \chi_c(G_{n,\frac 4 n})<3$ w.h.p.
4-Factor-Criticality of Vertex-Transitive Graphs
Authors: Sun Wuyang , Zhang Heping 
Published: January 2020

A graph of order $n$ is $p$-factor-critical, where $p$ is an integer of the same parity as $n$, if the removal of any set of $p$ vertices results in a graph with a perfect matching. 1-factor-critical graphs and 2-factor-critical graphs are well-known factor-critical graphs and bicritical graphs, respectively. It is known that if a connected vertex-transitive graph has odd order, then it is factor-critical, otherwise it is elementary bipartite or bicritical. In this paper, we show that a connected vertex-transitive non-bipartite graph of even order at least 6 is 4-factor-critical if and only if its degree is at least 5. This result implies that each connected non-bipartite Cayley graph of even order and degree at least 5 is 2-extendable.
Wreath Product Action on Generalized Boolean Algebras
Authors: Mishra Ashish , Srinivasan Murali K. 
Published: January 2020

Let $G$ be a finite group acting on the finite set $X$ such that the corresponding (complex) permutation representation is multiplicity free. There is a natural rank and order preserving action of the wreath product $G\sim S_n$ on the generalized Boolean algebra $B_X(n)$. We explicitly block diagonalize the commutant of this action.
Local Finiteness, Distinguishing Numbers, and Tucker's Conjecture
Authors: Lehner Florian , Möller Rögnvaldur G. 
Published: January 2020

A distinguishing colouring of a graph is a colouring of the vertex set such that no non-trivial automorphism preserves the colouring. Tucker conjectured that if every non-trivial automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We show that the requirement of local finiteness is necessary by giving a non-locally finite graph for which no finite number of colours suffices.
Interpreting the Truncated Pentagonal Number Theorem using Partition Pairs
Authors: Kolitsch Louis W. , Burnette Michael 
Published: January 2020

In 2012 Andrews and Merca gave a new expansion for partial sums of Euler's pentagonal number series and expressed \[\sum_{j=0}^{k-1}(-1)^j(p(n-j(3j+1)/2)-p(n-j(3j+5)/2-1))=(-1)^{k-1}M_k(n)\] where $M_k(n)$ is the number of partitions of $n$ where $k$ is the least integer that does not occur as a part and there are more parts greater than $k$ than there are less than $k$. We will show that $M_k(n)=C_k(n)$ where $C_k(n)$ is the number of partition pairs $(S, U)$ where $S$ is a partition with parts greater than $k$, $U$ is a partition with $k-1$ distinct parts all of which are greater than the smallest part in $S$, and the sum of the parts in $S \cup U$ is $n$. We use partition pairs to determine what is counted by three similar expressions involving linear combinations of pentagonal numbers. Most of the results will be presented analytically and combinatorially.
Evaluations of Hecke Algebra Traces at Kazhdan-Lusztig Basis Elements
Authors: Clearman Samuel , Hyatt Matthew , Shelton Brittany , Skandera Mark 
Published: January 2020

For irreducible characters $\{ \chi_q^\lambda \,|\, \lambda \vdash n \}$, induced sign characters $\{ \epsilon_q^\lambda \,|\, \lambda \vdash n \}$, and induced trivial characters $\{ \eta_q^\lambda \,|\, \lambda \vdash n \}$ of the Hecke algebra $H_n(q)$, and Kazhdan-Lusztig basis elements $C'_w(q)$ with $w$ avoiding the patterns 3412 and 4231, we combinatorially interpret the polynomials $\smash{\chi_q^\lambda(q^{\ell(w)/2} C'_w(q))}$, $\smash{\epsilon_q^\lambda(q^{\ell(w)/2} C'_w(q))}$, and $\smash{\eta_q^\lambda(q^{\ell(w)/2} C'_w(q))}$. This gives a new algebraic interpretation of chromatic quasisymmetric functions of Shareshian and Wachs, and a new combinatorial interpretation of special cases of results of Haiman. We prove similar results for other $H_n(q)$-traces, and confirm a formula conjectured by Haiman.
Brick Manifolds and Toric Varieties of Brick Polytopes
Authors: Escobar Laura 
Published: January 2020

Bott-Samelson varieties are a twisted product of $\mathbb{C}\mathbb{P}^1$'s with a map into $G/B$. These varieties are mostly studied in the case in which the map into $G/B$ is birational to the image; however in this paper we study a fiber of this map when it is not birational. We prove that in some cases the general fiber, which we christen a brick manifold, is a toric variety. In order to do so we use the moment map of a Bott-Samelson variety to translate this problem into one in terms of the "subword complexes" of Knutson and Miller. Pilaud and Stump realized certain subword complexes as the dual of the boundary of a polytope which generalizes the brick polytope defined by Pilaud and Santos. For a nice family of words, the brick polytope is the generalized associahedron realized by Hohlweg, Lange and Thomas. These stories connect in a nice way: we show that the moment polytope of the brick manifold is the brick polytope. In particular, we give a nice description of the toric variety of the associahedron. We give each brick manifold a stratification dual to the subword complex. In addition, we relate brick manifolds to Brion's resolutions of Richardon varieties.
Covering Partial Cubes with Zones
Authors: Cardinal Jean , Felsner Stefan 
Published: January 2020

A partial cube is a graph having an isometric embedding in a hypercube. Partial cubes are characterized by a natural equivalence relation on the edges, whose classes are called zones. The number of zones determines the minimal dimension of a hypercube in which the graph can be embedded. We consider the problem of covering the vertices of a partial cube with the minimum number of zones. The problem admits several special cases, among which are the following:cover the cells of a line arrangement with a minimum number of lines,select a smallest subset of edges in a graph such that for every acyclic orientation, there exists a selected edge that can be flipped without creating a cycle,find a smallest set of incomparable pairs of elements in a poset such that in every linear extension, at least one such pair is consecutive,find a minimum-size fibre in a bipartite poset.We give upper and lower bounds on the worst-case minimum size of a covering by zones in several of those cases. We also consider the computational complexity of those problems, and establish some hardness results.
On the Matchings-Jack Conjecture for Jack Connection Coefficients Indexed by Two Single Part Partitions
Authors: Kanunnikov Andrei L. , Vassilieva Ekaterina A. 
Published: January 2020

This article is devoted to the study of Jack connection coefficients, a generalization of the connection coefficients of the classical commutative subalgebras of the group algebra of the symmetric group closely related to the theory of Jack symmetric functions. First introduced by Goulden and Jackson (1996) these numbers indexed by three partitions of a given integer $n$ and the Jack parameter $\alpha$ are defined as the coefficients in the power sum expansion of some Cauchy sum for Jack symmetric functions. Goulden and Jackson conjectured that they are polynomials in $\beta = \alpha-1$ with non negative integer coefficients of combinatorial significance, the Matchings-Jack conjecture.In this paper we look at the case when two of the integer partitions are equal to the single part $(n)$. We use an algebraic framework of Lasalle (2008) for Jack symmetric functions and a bijective construction in order to show that the coefficients satisfy a simple recurrence formula and prove the Matchings-Jack conjecture in this case. Furthermore we exhibit the polynomial properties of more general coefficients where the two single part partitions are replaced by an arbitrary number of integer partitions either equal to $(n)$ or $[1^{n-2}2]$.
Finding Domatic Partitions in Infinite Graphs
Authors: Jura Matthew , Levin Oscar , Markkanen Tyler 
Published: January 2020

We investigate the apparent difficulty of finding domatic partitions in graphs using tools from computability theory. We consider nicely presented (i.e., computable) infinite graphs and show that even if the domatic number is known, there might not be any algorithm for producing a domatic partition of optimal size. However, we prove that smaller domatic partitions can be constructed if we restrict to regular graphs. Additionally, we establish similar results for total domatic partitions.
On the Existence of Certain Optimal Self-Dual Codes with Lengths Between 74 and 116
Authors: Zhang Tao , Michel Jerod , Feng Tao , Ge Gennian 
Published: January 2020

The existence of optimal binary self-dual codes is a long-standing research problem. In this paper, we present some results concerning the decomposition of binary self-dual codes with a dihedral automorphism group $D_{2p}$, where $p$ is a prime. These results are applied to construct new self-dual codes with length $78$ or $116$. We obtain $16$ inequivalent self-dual $[78,39,14]$ codes, four of which have new weight enumerators. We also show that there are at least $141$ inequivalent self-dual $[116,58,18]$ codes, most of which are new up to equivalence. Meanwhile, we give some restrictions on the weight enumerators of singly even self-dual codes. We use these restrictions to exclude some possible weight enumerators of self-dual codes with lengths $74$, $76$, $82$, $98$ and $100$.
Upper Bounds on the Minimum Size of Hamilton Saturated Hypergraphs
Authors: Ruciński Andrzej , Żak Andrzej 
Published: January 2020

For $1\leqslant \ell< k$, an $\ell$-overlapping $k$-cycle is a $k$-uniform hypergraph in which, for some cyclic vertex ordering, every edge consists of $k$ consecutive vertices and every two consecutive edges share exactly $\ell$ vertices.A $k$-uniform hypergraph $H$ is $\ell$-Hamiltonian saturated if $H$ does not contain an $\ell$-overlapping Hamiltonian $k$-cycle but every hypergraph obtained from $H$ by adding one edge does contain such a cycle. Let $\mathrm{sat}(n,k,\ell)$ be the smallest number of edges in an $\ell$-Hamiltonian saturated $k$-uniform hypergraph on $n$ vertices. In the case of graphs Clark and Entringer showed in 1983 that $\mathrm{sat}(n,2,1)=\lceil \tfrac{3n}2\rceil$. The present authors proved that for $k\geqslant 3$ and $\ell=1$, as well as for all $0.8k\leqslant \ell\leq k-1$, $\mathrm{sat}(n,k,\ell)=\Theta(n^{\ell})$. In this paper we prove two upper bounds which cover the remaining range of $\ell$. The first, quite technical one, restricted to $\ell\geqslant\frac{k+1}2$, implies in particular that for $\ell=\tfrac23k$ and $\ell=\tfrac34k$ we have $\mathrm{sat}(n,k,\ell)=O(n^{\ell+1})$. Our main result provides an upper bound $\mathrm{sat}(n,k,\ell)=O(n^{\frac{k+\ell}2})$ valid for all $k$ and $\ell$. In the smallest open case we improve it further to $\mathrm{sat}(n,4,2)=O(n^{\frac{14}5})$.
Turán Numbers for 3-Uniform Linear Paths of Length 3
Authors: Jackowska Eliza , Polcyn Joanna , Ruciński Andrzej 
Published: January 2020

In this paper we confirm a special, remaining case of a conjecture of Füredi, Jiang, and Seiver, and determine an exact formula for the Turán number $\mathrm{ex}_3(n; P_3^3)$ of the 3-uniform linear path $P^3_3$ of length 3, valid for all $n$. It coincides with the analogous formula for the 3-uniform triangle $C^3_3$, obtained earlier by Frankl and Füredi for $n\ge 75$ and Csákány and Kahn for all $n$. In view of this coincidence, we also determine a `conditional' Turán number, defined as the maximum number of edges in a $P^3_3$-free 3-uniform hypergraph on $n$ vertices which is not $C^3_3$-free.
Internally Fair Factorizations and Internally Fair Holey Factorizations with Prescribed Regularity
Authors: Erzurumluoğlu Aras , Rodger Chris A. 
Published: January 2020

Let $G$ be a multipartite multigraph without loops. Then $G$ is said to be internally fair if its edges are shared as evenly as possible among all pairs of its partite sets. An internally fair factorization of $G$ is an edge-decomposition of $G$ into internally fair regular spanning subgraphs. A holey factor of $G$ is a regular subgraph spanning all vertices but one partite set. An internally fair holey factorization is an edge-decomposition of $G$ into internally fair holey factors. In this paper, we settle the existence of internally fair (respectively, internally fair holey) factorizations of the complete equipartite multigraph into factors (respectively, holey factors) with prescribed regularity.
All Ramsey Numbers for Brooms in Graphs
Authors: Yu Pei , Li Yusheng 
Published: January 2020

For $k,\ell\ge 1$, a broom $B_{k,\ell}$ is a tree on $n=k+\ell$ vertices obtained by connecting the central vertex of a star $K_{1,k}$ with an end-vertex of a path on $\ell-1$ vertices. As $B_{n-2,2}$ is a star and $B_{1,n-1}$ is a path, their Ramsey number have been determined among rarely known $R(T_n)$ of trees $T_n$ of order $n$. Erdős, Faudree, Rousseau and Schelp determined the value of $R(B_{k,\ell})$ for $\ell\ge 2k\geq2$. We shall determine all other $R(B_{k,\ell})$ in this paper, which says that, for fixed $n$, $R(B_{n-\ell,\ell})$ decreases first on $1\le\ell \le 2n/3$ from $2n-2$ or $2n-3$ to $\lceil\frac{4n}{3}\rceil-1$, and then it increases on $2n/3 < \ell\leq n$ from $\lceil\frac{4n}{3}\rceil-1$ to $\lfloor\frac{3n}{2}\rfloor -1$. Hence $R(B_{n-\ell,\ell})$ may attain the maximum and minimum values of $R(T_n)$ as $\ell$ varies.
New Eulerian Numbers of Type $D$
Authors: Borowiec Anna , Młotkowski Wojciech 
Published: January 2020

We introduce a new array of type $D$ Eulerian numbers, different from that studied by Brenti, Chow and Hyatt. We find in particular the recurrence relation, Worpitzky formula and the generating function. We also find the probability distributions whose moments are Eulerian polynomials of type $A$, $B$ and $D$.
Every Triangulated 3-Polytope of Minimum Degree 4 has a 4-Path of Weight at Most 27
Authors: Borodin O.V. , Ivanova A.O. 
Published: January 2020

By $\delta$ and $w_k$ denote the minimum degree and minimum degree-sum (weight) of a $k$-vertex path in a given graph, respectively. For every 3-polytope, $w_2\le13$ (Kotzig, 1955) and $w_3\le21$ (Ando, Iwasaki, Kaneko, 1993), where both bounds are sharp. For every 3-polytope with $\delta\ge4$, we have sharp bounds $w_2\le11$ (Lebesgue, 1940) and $w_3\le17$ (Borodin, 1997).Madaras (2000) proved that every triangulated 3-polytope with $\delta\ge4$ satisfies $w_4\le31$ and constructed such a 3-polytope with $w_4=27$.We improve the Madaras bound $w_4\le31$ to the sharp bound $w_4\le27$.
The Černý Conjecture and 1-Contracting Automata
Authors: Don Henk 
Published: January 2020

A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. Černý conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. We introduce the notion of aperiodically 1-contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the Černý conjecture holds for aperiodically 1-contracting automata. As a special case, we prove some results for circular automata.
On the Multi-Colored Ramsey Numbers of Paths and Even Cycles
Authors: Sárközy Gábor N. 
Published: January 2020

In this paper we improve the upper bound on the multi-color Ramsey numbers of paths and even cycles. More precisely, we prove the following. For every $r\geq 2$ there exists an $n_0=n_0(r)$ such that for $n\geq n_0$ we have $$R_r(P_n) \leq \left( r - \frac{r}{16r^3+1} \right) n.$$ For every $r\geq 2$ and even $n$ we have $$R_r(C_n) \leq \left( r - \frac{r}{16r^3+1} \right) n + o(n) \text{ as }n\rightarrow \infty.$$ The main tool is a stability version of the Erdős-Gallai theorem that may be of independent interest.
Orphans in Forests of Linear Fractional Transformations
Authors: Han Sandie , Masuda Ariane M. , Singh Satyanand , Thiel Johann 
Published: January 2020

A positive linear fractional transformation (PLFT) is a function of the form $f(z)=\frac{az+b}{cz+d}$ where $a,b,c$ and $d$ are nonnegative integers with determinant $ad-bc\neq 0$. Nathanson generalized the notion of the Calkin-Wilf tree to PLFTs and used it to partition the set of PLFTs into an infinite forest of rooted trees. The roots of these PLFT Calkin-Wilf trees are called orphans. In this paper, we provide a combinatorial formula for the number of orphans with fixed determinant $D$. In addition, we derive a method for determining the orphan ancestor of a given PLFT. Lastly, taking $z$ to be a complex number, we show that every positive complex number has finitely many ancestors in the forest of complex $(u,v)$-Calkin-Wilf trees.
Chip Games and Paintability
Authors: Duraj Lech , Gutowski Grzegorz , Kozik Jakub 
Published: January 2020

We prove that the paint number of the complete bipartite graph $K_{N,N}$ is $\log N + O(1)$. As a consequence, we get that the difference between the paint number and the choice number of $K_{N,N}$ is $\Theta(\log \log N)$. This answers in the negative the question of Zhu (2009) whether this difference, for all graphs, can be bounded by a common constant. By a classical correspondence, our result translates to the framework of on-line coloring of uniform hypergraphs. This way we obtain that for every on-line two coloring algorithm there exists a $k$-uniform hypergraph with $\Theta(2^k)$ edges on which the strategy fails. The results are derived through an analysis of a natural family of chip games.
New Results on $k$-Independence of Graphs
Authors: Kogan Shimon 
Published: January 2020

Let $G = (V, E)$ be a graph and $k \geq 0$ an integer. A $k$-independent set $S \subseteq G$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. Denote by $\alpha_{k}(G)$ the maximum cardinality of a $k$-independent set of $G$. For a graph $G$ on $n$ vertices and average degree $d$, Turán's theorem asserts that $\alpha_{0}(G) \geq \frac{n}{d+1}$, where the equality holds if and only if $G$ is a union of cliques of equal size. For general $k$ we prove that $\alpha_{k}(G) \geq \dfrac{(k+1)n}{d+k+1}$, improving on the previous best bound $\alpha_{k}(G) \geq \dfrac{(k+1)n}{ \lceil d \rceil+k+1}$ of Caro and Hansberg [E-JC, 2013]. For $1$-independence we prove that equality holds if and only if $G$ is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a $1$-factor). For $2$-independence, we prove that equality holds if and only if $G$ is an independent set. Furthermore when $d>0$ is an integer divisible by 3 we prove that $\alpha_2(G) \geq \dfrac{3n}{d+3} \left( 1 + \dfrac{12}{5d^2 + 25d + 18} \right)$.