bluuebunny/crossref_metadata_2025_split huggingface dataset:
New Turán Densities for 3-Graphs
Authors: Baber Rahil , Talbot John 
Published: January 2020

If $\mathcal{F}$ is a family of graphs then the Turán density of $\mathcal{F}$ is determined by the minimum chromatic number of the members of $\mathcal{F}$.The situation for Turán densities of 3-graphs is far more complex and still very unclear. Our aim in this paper is to present new exact Turán densities for individual and finite families of $3$-graphs, in many cases we are also able to give corresponding stability results. As well as providing new examples of individual $3$-graphs with Turán densities equal to $2/9,4/9,5/9$ and $3/4$ we also give examples of irrational Turán densities for finite families of 3-graphs, disproving a conjecture of Chung and Graham. (Pikhurko has independently disproved this conjecture by a very different method.)A central question in this area, known as Turán's problem, is to determine the Turán density of $K_4^{(3)}=\{123, 124, 134, 234\}$. Turán conjectured that this should be $5/9$. Razborov [On 3-hypergraphs with forbidden 4-vertex configurations in SIAM J. Disc. Math. 24 (2010), 946--963] showed that if we consider the induced Turán problem forbidding $K_4^{(3)}$ and $E_1$, the 3-graph with 4 vertices and a single edge, then the Turán density is indeed $5/9$. We give some new non-induced results of a similar nature, in particular we show that $\pi(K_4^{(3)},H)=5/9$ for a $3$-graph $H$ satisfying $\pi(H)=3/4$.We end with a number of open questions focusing mainly on the topic of which values can occur as Turán densities.Our work is mainly computational, making use of Razborov's flag algebra framework. However all proofs are exact in the sense that they can be verified without the use of any floating point operations. Indeed all verifying computations use only integer operations, working either over $\mathbb{Q}$ or in the case of irrational Turán densities over an appropriate quadratic extension of $\mathbb{Q}$.
A Survey of Forbidden Configuration Results
Authors: Anstee Richard 
Published: January 2020

Let $F$ be a $k\times \ell$ (0,1)-matrix. We say a (0,1)-matrix $A$ has $F$ as a configuration if there is a submatrix of $A$ which is a row and column permutation of $F$. In the language of sets, a configuration is a trace and in the language of hypergraphs a configuration is a subhypergraph.Let $F$ be a given $k\times \ell$ (0,1)-matrix. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. The matrix $F$ need not be simple. We define $\hbox{forb}(m,F)$ as the maximum number of columns of any simple $m$-rowed matrix $A$ which do not contain $F$ as a configuration. Thus if $A$ is an $m\times n$ simple matrix which has no submatrix which is a row and column permutation of $F$ then $n\le\hbox{forb}(m,F)$. Or alternatively if $A$ is an $m\times (\hbox{forb}(m,F)+1)$ simple matrix then $A$ has a submatrix which is a row and column permutation of $F$. We call $F$ a forbidden configuration. The fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. For $K_k$ denoting the $k\times 2^k$ submatrix of all (0,1)-columns on $k$ rows, then $\hbox{forb}(m,K_k)=\binom{m}{k-1}+\binom{m}{k-2}+\cdots \binom{m}{0}$. We seek asymptotic results for $\hbox{forb}(m,F)$ for a fixed $F$ and as $m$ tends to infinity . A conjecture of Anstee and Sali predicts the asymptotically best constructions from which to derive the asymptotics of $\hbox{forb}(m,F)$. The conjecture has helped guide the research and has been verified for $k\times \ell$ $F$ with $k=1,2,3$ and for simple $F$ with $k=4$ as well as other cases including $\ell=1,2$. We also seek exact values for $\hbox{forb}(m,F)$.
Extremal Graphs Having No Stable Cutset
Authors: Le Van Bang , Pfender Florian 
Published: January 2020

A stable cutset in a graph is a stable set whose deletion disconnects the graph. It was conjectured by Caro and proved by Chen and Yu that any graph with $n$ vertices and at most $2n-4$ edges contains a stable cutset. The bound is tight, as we will show that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. As a by-product, an algorithmic implication of our result will be pointed out.
Γ-Species and the Enumeration of $k$-Trees
Authors: Gainer-Dewar Andrew 
Published: January 2020

We study the class of graphs known as $k$-trees through the lens of Joyal’s theory of combinatorial species (and a extension known as 'Γ-species' which incorporates data about 'structural' group actions). This culminates in a system of recursive functional equations giving the generating function for unlabeled $k$-trees which allows for fast, efficient computation of their numbers. Enumerations up to $k = 10$ and $n = 30$ (for a k-tree with $n + k − 1$ vertices) are included in tables, and Sage code for the general computation is included in an appendix.
The Graph Crossing Number and its Variants: A Survey
Authors: Schaefer Marcus 
Published: January 2020

The crossing number is a popular tool in graph drawing and visualization, but there is not really just one crossing number; there is a large family of crossing number notions of which the crossing number is the best known. We survey the rich variety of crossing number variants that have been introduced in the literature for purposes that range from studying the theoretical underpinnings of the crossing number to crossing minimization for visualization problems.
Unique Sequences Containing No $k$-Term Arithmetic Progressions
Authors: Ahmed Tanbir , Dybizbánski Janusz , Snevily Hunter 
Published: January 2020

In this paper, we are concerned with calculating $r(k, n)$, the length of the longest $k$-AP free subsequences in $1, 2, \ldots , n$. We prove the basic inequality $r(k, n) \le n − \lfloor m/2\rfloor$, where $n = m(k − 1) + r$ and $r < k − 1$. We also discuss a generalization of a famous conjecture of Szekeres (as appears in Erdős and Turán) and describe a simple greedy algorithm that appears to give an optimal $k$-AP free sequence infinitely often. We provide many exact values of $r(k, n)$ in the Appendix.
Bounding the Distinguishing Number of Infinite Graphs and Permutation Groups
Authors: Smith Simon M. , Watkins Mark E. 
Published: January 2020

A group of permutations $G$ of a set $V$ is $k$-distinguishable if there exists a partition of $V$ into $k$ cells such that only the identity permutation in $G$ fixes setwise all of the cells of the partition. The least cardinal number $k$ such that $(G,V)$ is $k$-distinguishable is its distinguishing number $D(G,V)$. In particular, a graph $\Gamma$ is $k$-distinguishable if its automorphism group $\rm{Aut}(\Gamma)$ satisfies $D(\rm{Aut}(\Gamma),V\Gamma)\leq k$.Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph $\Gamma$ is not $k$-distinguishable (for a given cardinal $k$), then it contains a ball of finite radius whose distinguishing number is at least $k$. Moreover, this lower bound cannot be sharpened, since for any integer $k \geq 3$ there exists an infinite, locally finite, connected graph $\Gamma$ that is not $k$-distinguishable but in which every ball of finite radius is $k$-distinguishable.In the second half of this paper we show that a large distinguishing number for an imprimitive group $G$ is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action by $G$ on the corresponding system of imprimitivity. An immediate application is to automorphism groups of infinite imprimitive graphs. These results are companion to the study of the distinguishing number of infinite primitive groups and graphs in a previous paper by the authors together with T. W. Tucker.
Beyond Alternating Permutations: Pattern Avoidance in Young Diagrams and Tableaux
Authors: Gowravaram Nihal , Jagadeesan Ravi 
Published: January 2020

We investigate pattern avoidance in alternating permutations and generalizations thereof. First, we study pattern avoidance in an alternating analogue of Young diagrams. In particular, we extend Babson-West's notion of shape-Wilf equivalence to apply to alternating permutations and so generalize results of Backelin-West-Xin and Ouchterlony to alternating permutations. Second, we study pattern avoidance in the more general context of permutations with restricted ascents and descents. We consider a question of Lewis regarding permutations that are the reading words of thickened staircase Young tableaux, that is, permutations that have $k-1$ ascents followed by a descent, followed by $k-1$ ascents, et cetera. We determine the relative sizes of the sets of pattern-avoiding $(k-1)$-ascent permutations in terms of the forbidden pattern. Furthermore, inequalities in the sizes of sets of pattern-avoiding permutations in this context arise from further extensions of shape-equivalence type enumerations. This paper is the first of a two-paper series presenting the work of Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux (arXiv:1301.6796v1). The second in the series is Ascent-descent Young diagrams and pattern avoidance in alternating permutations (by the second author, submitted).
A Generic Method for Bijections between Blossoming Trees and Planar Maps
Authors: Albenque Marie , Poulalhon Dominique 
Published: January 2020

This article presents a unified bijective scheme between planar maps and blossoming trees, where a blossoming tree is defined as a spanning tree of the map decorated with some dangling half-edges that enable to reconstruct its faces. Our method generalizes a previous construction of Bernardi by loosening its conditions of application so as to include annular maps, that is maps embedded in the plane with a root face different from the outer face.The bijective construction presented here relies deeply on the theory of $\alpha$-orientations introduced by Felsner, and in particular on the existence of minimal and accessible orientations. Since most of the families of maps can be characterized by such orientations, our generic bijective method is proved to capture as special cases many previously known bijections involving blossoming trees: for example Eulerian maps, $m$-Eulerian maps, non-separable maps and simple triangulations and quadrangulations of a $k$-gon. Moreover, it also permits to obtain new bijective constructions for bipolar orientations and $d$-angulations of girth $d$ of a $k$-gon.As for applications, each specialization of the construction translates into enumerative by-products, either via a closed formula or via a recursive computational scheme. Besides, for every family of maps described in the paper, the construction can be implemented in linear time. It yields thus an effective way to encode or sample planar maps.In a recent work, Bernardi and Fusy introduced another unified bijective scheme; we adopt here a different strategy which allows us to capture different bijections. These two approaches should be seen as two complementary ways of unifying bijections between planar maps and decorated trees.
Forcing $k$-Repetitions in Degree Sequences
Authors: Caro Yair , Shapira Asaf , Yuster Raphael 
Published: January 2020

One of the most basic results in graph theory states that every graph with at least two vertices has two vertices with the same degree. Since there are graphs without $3$ vertices of the same degree, it is natural to ask if for any fixed $k$, every graph $G$ is "close" to a graph $G'$ with $k$ vertices of the same degree. Our main result in this paper is that this is indeed the case. Specifically, we show that for any positive integer $k$, there is a constant $C=C(k)$, so that given any graph $G$, one can remove from $G$ at most $C$ vertices and thus obtain a new graph $G'$ that contains at least $\min\{k,|G|-C\}$ vertices of the same degree.Our main tool is a multidimensional zero-sum theorem for integer sequences, which we prove using an old geometric approach of Alon and Berman.
Face-Width of Pfaffian Braces and Polyhex Graphs on Surfaces
Authors: Ye Dong , Zhang Heping 
Published: January 2020

A graph $G$ with a perfect matching is Pfaffian if it admits an orientation $D$ such that every central cycle $C$ (i.e. $C$ is of even size and $G-V(C)$ has a perfect matching) has an odd number of edges oriented in either direction of the cycle. It is known that the number of perfect matchings of a Pfaffian graph can be computed in polynomial time. In this paper, we show that every embedding of a Pfaffian brace (i.e. 2-extendable bipartite graph) on a surface with a positive genus has face-width at most 3. Further, we study Pfaffian cubic braces and obtain a characterization of Pfaffian polyhex graphs: a polyhex graph is Pfaffian if and only if it is either non-bipartite or isomorphic to the cube, or the Heawood graph, or the Cartesian product $C_k\times K_2$ for even integers $k\ge 6$.
Homomesy in Products of Two Chains
Authors: Propp James , Roby Tom 
Published: January 2020

Many invertible actions $\tau$ on a set $\mathcal{S}$ of combinatorial objects, along with a natural statistic $f$ on $\mathcal{S}$, exhibit the following property which we dub homomesy: the average of $f$ over each $\tau$-orbit in $\mathcal{S}$ is the same as the average of $f$ over the whole set $\mathcal{S}$. This phenomenon was first noticed by Panyushev in 2007 in the context of the rowmotion action on the set of antichains of a root poset; Armstrong, Stump, and Thomas proved Panyushev's conjecture in 2011. We describe a theoretical framework for results of this kind that applies more broadly, giving examples in a variety of contexts. These include linear actions on vector spaces, sandpile dynamics, Suter's action on certain subposets of Young's Lattice, Lyness 5-cycles, promotion of rectangular semi-standard Young tableaux, and the rowmotion and promotion actions on certain posets. We give a detailed description of the latter situation for products of two chains.
Switching in One-Factorisations of Complete Graphs
Authors: Kaski Petteri , Medeiros André de Souza , Östergård Patric R.J. , Wanless Ian M. 
Published: January 2020

We define two types of switchings between one-factorisations of complete graphs, called factor-switching and vertex-switching. For each switching operation and for each $n\le 12$, we build a switching graph that records the transformations between isomorphism classes of one-factorisations of $K_{n}$. We establish various parameters of our switching graphs, including order, size, degree sequence, clique number and the radius of each component.As well as computing data for $n\le12$, we demonstrate several properties that hold for one-factorisations of $K_{n}$ for general $n$. We show that such factorisations have a parity which is not changed by factor-switching, and this leads to disconnected switching graphs. We also characterise the isolated vertices that arise from an absence of switchings. For factor-switching the isolated vertices are perfect one-factorisations, while for vertex-switching the isolated vertices are closely related to atomic Latin squares.
On Fractional Realizations of Graph Degree Sequences
Authors: Barrus Michael D. 
Published: January 2020

We introduce fractional realizations of a graph degree sequence and a closely associated convex polytope. Simple graph realizations correspond to a subset of the vertices of this polytope; we characterize degree sequences for which each polytope vertex corresponds to a simple graph realization. These include the degree sequences of threshold and pseudo-split graphs, and we characterize their realizations both in terms of forbidden subgraphs and graph structure.
Extending Cycles Locally to Hamilton Cycles
Authors: Hamann Matthias , Lehner Florian , Pott Julian 
Published: January 2020

A Hamilton circle in an infinite graph is a homeomorphic copy of the unit circle $S^1$ that contains all vertices and all ends precisely once. We prove that every connected, locally connected, locally finite, claw-free graph has such a Hamilton circle, extending a result of Oberly and Sumner to infinite graphs. Furthermore, we show that such graphs are Hamilton-connected if and only if they are $3$-connected, extending a result of Asratian. Hamilton-connected means that between any two vertices there is a Hamilton arc, a homeomorphic copy of the unit interval $[0,1]$ that contains all vertices and all ends precisely once.
Modular Statistics for Subgraph Counts in Sparse Random Graphs
Authors: DeMarco Bobby , Kahn Jeff , Redlich Amanda 
Published: January 2020

Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1,\dots, G_k$, if $p=p(n) $ is such that $\Pr(G_{n,p}\supseteq G_i)\rightarrow 1$ $\forall i$, then, with $\xi_i$ the number of copies of $G_i$ in $G_{n,p}$, $(\xi_1,\dots, \xi_k)$ is asymptotically uniformly distributed on ${\bf Z}_q^k$.
Graph Homomorphisms between Trees
Authors: Csikvári Péter , Lin Zhicong 
Published: January 2020

In this paper we study several problems concerning the number of homomorphisms of trees. We begin with an algorithm for the number of homomorphisms from a tree to any graph. By using this algorithm and some transformations on trees, we study various extremal problems about the number of homomorphisms of trees. These applications include a far reaching generalization and a dual of Bollobás and Tyomkyn's result concerning the number of walks in trees.Some other main results of the paper are the following. Denote by $\hom(H,G)$ the number of homomorphisms from a graph $H$ to a graph $G$. For any tree $T_m$ on $m$ vertices we give a general lower bound for $\hom(T_m,G)$ by certain entropies of Markov chains defined on the graph $G$. As a particular case, we show that for any graph $G$, $$\exp(H_{\lambda}(G))\lambda^{m-1}\leq\hom(T_m,G),$$ where $\lambda$ is the largest eigenvalue of the adjacency matrix of $G$ and $H_{\lambda}(G)$ is a certain constant depending only on $G$ which we call the spectral entropy of $G$. We also show that if $T_m$ is any fixed tree and$$\hom(T_m,P_n)>\hom(T_m,T_n),$$for some tree $T_n$ on $n$ vertices, then $T_n$ must be the tree obtained from a path $P_{n-1}$ by attaching a pendant vertex to the second vertex of $P_{n-1}$.All the results together enable us to show that among all trees with fixed number of vertices, the path graph has the fewest number of endomorphisms while the star graph has the most.
Nordhaus-Gaddum Type Inequalities for Laplacian and Signless Laplacian Eigenvalues
Authors: Ashraf F. , Tayfeh-Rezaie B. 
Published: January 2020

Let $G$ be a graph with $n$ vertices. We denote the largest signless Laplacian eigenvalue of $G$ by $q_1(G)$ and Laplacian eigenvalues of $G$ by $\mu_1(G)\ge\cdots\ge\mu_{n-1}(G)\ge\mu_n(G)=0$. It is a conjecture on Laplacian spread of graphs that $\mu_1(G)-\mu_{n-1}(G)\le n-1$ or equivalently $\mu_1(G)+\mu_1(\overline G)\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph $G$, $\mu_1(G)\mu_1(\overline G)\le n(n-1)$. Aouchiche and Hansen [Discrete Appl. Math. 2013] conjectured that $q_1(G)+q_1(\overline G)\le3n-4$ and $q_1(G)q_1(\overline G)\le2n(n-2)$. We prove the former and disprove the latter by constructing a family of graphs $H_n$ where $q_1(H_n)q_1(\overline{H_n})$ is about $2.15n^2+O(n)$.
Thin Edges in Braces
Authors: Lucchesi Cláudio L. , De Carvalho Marcelo H. , Murty U. S. R. 
Published: January 2020

The bicontraction of a vertex $v$ of degree two in a graph, with precisely two neighbours $v_1$ and $v_2$, consists of shrinking the set $\{v_1,v,v_2\}$ to a single vertex. The retract of a matching covered graph $G$, denoted by $\widehat{G}$, is the graph obtained from $G$ by repeatedly bicontracting vertices of degree two. Up to isomorphism, the retract of a matching covered graph $G$ is unique. If $G$ is a brace on six or more vertices, an edge $e$ of $G$ is thin if $\widehat{G-e}$ is a brace. A thin edge $e$ in a simple brace $G$ is strictly thin if $\widehat{G-e}$ is a simple brace. Theorems concerning the existence of strictly thin edges have been used (implicitly by McCuaig (Pólya's Permanent Problem, Electron. J. of Combin., 11, 2004) and explicitly by the authors (On the Number of Perfect Matchings in a Bipartite Graph, SIAM J. Discrete Math., 27, 940-958, 2013)) as inductive tools for establishing properties of braces.Let $G$ and $J$ be two distinct braces, where $G$ is of order six or more and $J$ is a simple matching minor of $G$. It follows from a theorem of McCuaig (Brace Generation, J. Graph Theory, 38, 124-169, 2001) that $G$ has a thin edge $e$ such that $J$ is a matching minor of $G-e$. In Section 2, we give an alternative, and simpler proof, of this assertion. Our method of proof lends itself to proving stronger results concerning thin edges.Let ${\cal G}^+$ denote the family of braces consisting of all prisms, all Möbius ladders, all biwheels, and all extended biwheels. Strengthening another result of McCuaig on brace generation, we show that every simple brace of order six or more which is not a member of ${\cal G}^+$ has at least two strictly thin edges. We also give examples to show that this result is best possible.
Multiple Coverings with Closed Polygons
Authors: Kovács István , Tóth Géza 
Published: January 2020

A planar set $P$ is said to be cover-decomposable if there is a constant $k=k(P)$ such that every $k$-fold covering of the plane with translates of $P$ can be decomposed into two coverings. It is known that open convex polygons are cover-decomposable. Here we show that closed, centrally symmetric convex polygons are also cover-decomposable. We also show that an infinite-fold covering of the plane with translates of $P$ can be decomposed into two infinite-fold coverings. Both results hold for coverings of any subset of the plane.
On Obstacle Numbers
Authors: Dujmović Vida , Morin Pat 
Published: January 2020

The obstacle number is a new graph parameter introduced by Alpert, Koch, and Laison (2010). Mukkamala et al. (2012) show that there exist graphs with $n$ vertices having obstacle number in $\Omega(n/\log n)$. In this note, we up this lower bound to $\Omega(n/(\log\log n)^2)$. Our proof makes use of an upper bound of Mukkamala et al. on the number of graphs having obstacle number at most $h$ in such a way that any subsequent improvements to their upper bound will improve our lower bound.
Flows in Signed Graphs with Two Negative Edges
Authors: Rollová Edita , Schubert Michael , Steffen Eckhard 
Published: January 2020

The presented paper studies the flow number $F(G,\sigma)$ of flow-admissible signed graphs $(G,\sigma)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,\sigma)$ there is a set of cubic graphs obtained from $(G,\sigma)$ such that the flow number of $(G,\sigma)$ does not exceed the flow number of any of the cubic graphs. We prove that $F(G,\sigma) \leq 6$ if $(G,\sigma)$ contains a bridge, and $F(G,\sigma) \leq 7$ in general. We prove better bounds, if there is a cubic graph $(H,\sigma_H)$ obtained from $(G,\sigma)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,\sigma) \leq 4$ and the bound is tight. If $H$ is $3$-edge-colorable or critical or if it has a sufficient cyclic edge-connectivity, then $F(G,\sigma) \leq 6$. Furthermore, if Tutte's $5$-Flow Conjecture is true, then $(G,\sigma)$ admits a nowhere-zero $6$-flow endowed with some strong properties.