bluuebunny/crossref_metadata_2025_split huggingface dataset:
Modeling Limits in Hereditary Classes: Reduction and Application to Trees
Authors: Nešetřil Jaroslav , Ossona de Mendez Patrice 
Published: January 2020

The study of limits of graphs led to elegant limit structures for sparse and dense graphs. This has been unified and generalized by the authors in a more general setting combining analytic tools and model theory to ${\rm FO}$-limits (and $X$-limits) and to the notion of modeling. The existence of modeling limits was established for sequences in a bounded degree class and, in addition, to the case of classes of trees with bounded height and of graphs with bounded tree depth. The natural obstacle for the existence of modeling limit for a monotone class of graphs is the nowhere dense property and it has been conjectured that this is a sufficient condition. Extending earlier results here we derive several general results which present a realistic approach to this conjecture. As an example we then prove that the class of all finite trees admits modeling limits.
Symmetric Graphs with Respect to Graph Entropy
Authors: Changiz Rezaei Seyed Saeed , Chiniforooshan Ehsan 
Published: January 2020

Let $F_G(P)$ be a functional defined on the set of all the probability distributions on the vertex set of a graph $G$. We say that $G$ is symmetric with respect to $F_G(P)$ if the uniform distribution on $V(G)$ maximizes $F_G(P)$. Using the combinatorial definition of the entropy of a graph in terms of its vertex packing polytope and the relationship between the graph entropy and fractional chromatic number, we characterize all graphs which are symmetric with respect to graph entropy. We show that a graph is symmetric with respect to graph entropy if and only if its vertex set can be uniformly covered by its maximum size independent sets. This is also equivalent to saying that the fractional chromatic number of $G$, $\chi_f(G)$, is equal to $\frac{n}{\alpha(G)}$, where $n = |V(G)|$ and $\alpha(G)$ is the independence number of $G$. Furthermore, given any strictly positive probability distribution $P$ on the vertex set of a graph $G$, we show that $P$ is a maximizer of the entropy of graph $G$ if and only if its vertex set can be uniformly covered by its maximum weighted independent sets. We also show that the problem of deciding if a graph is symmetric with respect to graph entropy, where the weight of the vertices is given by probability distribution $P$, is co-NP-hard.
Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs
Authors: Bennett Patrick , Dudek Andrzej , Frieze Alan , Helenius Laars 
Published: January 2020

Given an $r$-uniform hypergraph $H=(V,E)$ and a weight function $\omega:E\to\{1,\dots,w\}$, a coloring of vertices of~$H$, induced by~$\omega$, is defined by $c(v) = \sum_{e\ni v} w(e)$ for all $v\in V$. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that $H$ is strongly $w$-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that $H$ is weakly $w$-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all $5$-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for $r\ge 6$ we show that almost all $r$-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for $r\ge 4$ almost all $r$-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are $r$-uniform hypergraphs which are not strongly $(r^2-r)$-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.
A Generalization of Sperner's Theorem on Compressed Ideals
Authors: Mu Lili , Wang Yi 
Published: January 2020

Let $[n]=\{1,2,\ldots,n\}$ and $\mathscr{B}_n=\{A: A\subseteq [n]\}$. A family $\mathscr{A}\subseteq \mathscr{B}_n$ is a Sperner family if $A\nsubseteq B$ and $B\nsubseteq A$ for distinct $A,B\in\mathscr{A}$. Sperner's theorem states that the density of the largest Sperner family in $\mathscr{B}_n$ is $\binom{n}{\left\lceil{n/2}\right\rceil}/2^n$. The objective of this note is to show that the same holds if $\mathscr{B}_n$ is replaced by compressed ideals over $[n]$.
A Sharp Bound for the Product of Weights of Cross-Intersecting Families
Authors: Borg Peter 
Published: January 2020

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$. For any two integers $n$ and $k$ with $1 \leq k \leq n$, let ${[n] \choose \leq k}$ denote the family of subsets of $\{1, \dots, n\}$ of size at most $k$, and let $\mathcal{S}_{n,k}$ denote the family of sets in ${[n] \choose \leq k}$ that contain $1$. The author recently showed that if $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $|\mathcal{A}||\mathcal{B}| \leq \mathcal{S}_{m,r}||\mathcal{S}_{n,s}|$. We prove a version of this result for the more general setting of \emph{weighted} sets. We show that if $g : {[m] \choose \leq r} \rightarrow \mathbb{R}^+$ and $h : {[n] \choose \leq s} \rightarrow \mathbb{R}^+$ are functions that obey certain conditions, $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $$\sum_{A \in \mathcal{A}} g(A) \sum_{B \in \mathcal{B}} h(B) \leq \sum_{C \in \mathcal{S}_{m,r}} g(C) \sum_{D \in \mathcal{S}_{n,s}} h(D).$$The bound is attained by taking $\mathcal{A} = \mathcal{S}_{m,r}$ and $\mathcal{B} = \mathcal{S}_{n,s}$. We also show that this result yields new sharp bounds for the product of sizes of cross-intersecting families of integer sequences and of cross-intersecting families of multisets.
Increasing the Minimum Distance of Codes by Twisting
Authors: Akbari Marzieh , Gillespie Neil I. , Praeger Cheryl E. 
Published: January 2020

Twisted permutation codes, introduced recently by the second and third authors, belong to the family of frequency permutation arrays. Like some other codes in this family, such as the repetition permutation codes, they are obtained by a repetition construction applied to a smaller code (but with a "twist" allowed). The minimum distance of a twisted permutation code is known to be at least the minimum distance of a corresponding repetition permutation code, but in some instances can be larger. We construct two new infinite families of twisted permutation codes with minimum distances strictly greater than those for the corresponding repetition permutation codes. These constructions are based on two infinite families of finite groups and their representations. The first is a family of $p$-groups, for an odd prime $p$, while the second family consists of the $4$-dimensional symplectic groups over a finite field of even order. In the latter construction, properties of the graph automorphism of these symplectic groups play an important role.
On a Permutation Problem for Finite Abelian Groups
Authors: Ge Fan , Sun Zhi-Wei 
Published: January 2020

Let $G$ be a finite additive abelian group with exponent $n>1$, and let $a_1,\ldots,a_{n-1}$ be elements of $G$. We show that there is a permutation $\sigma\in S_{n-1}$ such that all the elements $sa_{\sigma(s)}\ (s=1,\ldots,n-1)$ are nonzero if and only if$$\left|\left\{1\leqslant s<n:\ \frac{n}da_s\not=0\right\}\right|\geqslant d-1\ \ \mbox{for any positive divisor}\ d\ \mbox{of}\ n.$$When $G$ is the cyclic group $\mathbb Z/n\mathbb Z$, this confirms a conjecture of Z.-W. Sun.
Cubic Graphs and Related Triangulations on Orientable Surfaces
Authors: Fang Wenjie , Kang Mihyun , Moßhammer Michael , Sprüssel Philipp 
Published: January 2020

Let $\mathbb{S}_g$ be the orientable surface of genus $g$ for a fixed non-negative integer $g$. We show that the number of vertex-labelled cubic multigraphs embeddable on $\mathbb{S}_g$ with $2n$ vertices is asymptotically $c_g n^{5/2(g-1)-1}\gamma^{2n}(2n)!$, where $\gamma$ is an algebraic constant and $c_g$ is a constant depending only on the genus $g$. We also derive an analogous result for simple cubic graphs and weighted cubic multigraphs. Additionally, for $g\ge1$, we prove that a typical cubic multigraph embeddable on $\mathbb{S}_g$ has exactly one non-planar component.
Sidorenko's Conjecture, Colorings and Independent Sets
Authors: Csikvári Péter , Lin Zhicong 
Published: January 2020

Let $\hom(H,G)$ denote the number of homomorphisms from a graph $H$ to a graph $G$. Sidorenko's conjecture asserts that for any bipartite graph $H$, and a graph $G$ we have$$\hom(H,G)\geq v(G)^{v(H)}\left(\frac{\hom(K_2,G)}{v(G)^2}\right)^{e(H)},$$where $v(H),v(G)$ and $e(H),e(G)$ denote the number of vertices and edges of the graph $H$ and $G$, respectively. In this paper we prove Sidorenko's conjecture for certain special graphs $G$: for the complete graph $K_q$ on $q$ vertices, for a $K_2$ with a loop added at one of the end vertices, and for a path on $3$ vertices with a loop added at each vertex. These cases correspond to counting colorings, independent sets and Widom-Rowlinson colorings of a graph $H$. For instance, for a bipartite graph $H$ the number of $q$-colorings $\mathrm{ch}(H,q)$ satisfies$$\mathrm{ch}(H,q)\geq q^{v(H)}\left(\frac{q-1}{q}\right)^{e(H)}.$$In fact, we will prove that in the last two cases (independent sets and Widom-Rowlinson colorings) the graph $H$ does not need to be bipartite. In all cases, we first prove a certain correlation inequality which implies Sidorenko's conjecture in a stronger form.
Transversals and Independence in Linear Hypergraphs with Maximum Degree Two
Authors: Henning Michael A. , Yeo Anders 
Published: January 2020

For $k \ge 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices and $m$ edges. Let $S$ be a set of vertices in a hypergraph $H$. The set $S$ is a transversal if $S$ intersects every edge of $H$, while the set $S$ is strongly independent if no two vertices in $S$ belong to a common edge. The transversal number, $\tau(H)$, of $H$ is the minimum cardinality of a transversal in $H$, and the strong independence number of $H$, $\alpha(H)$, is the maximum cardinality of a strongly independent set in $H$. The hypergraph $H$ is linear if every two distinct edges of $H$ intersect in at most one vertex. Let $\mathcal{H}_k$ be the class of all connected, linear, $k$-uniform hypergraphs with maximum degree $2$. It is known [European J. Combin. 36 (2014), 231–236] that if $H \in \mathcal{H}_k$, then $(k+1)\tau(H) \le n+m$, and there are only two hypergraphs that achieve equality in the bound. In this paper, we prove a much more powerful result, and establish tight upper bounds on $\tau(H)$ and tight lower bounds on $\alpha(H)$ that are achieved for infinite families of hypergraphs. More precisely, if $k \ge 3$ is odd and $H \in \mathcal{H}_k$ has $n$ vertices and $m$ edges, then we prove that $k(k^2 - 3)\tau(H) \le (k-2)(k+1)n + (k - 1)^2m + k-1$ and $k(k^2 - 3)\alpha(H) \ge (k^2 + k - 4)n - (k-1)^2 m - (k-1)$. Similar bounds are proven in the case when $k \ge 2$ is even.
Beyond Degree Choosability
Authors: Cranston Daniel W. , Rabern Landon 
Published: January 2020

Let $G$ be a connected graph with maximum degree $\Delta$. Brooks' theorem states that $G$ has a $\Delta$-coloring unless $G$ is a complete graph or an odd cycle. A graph $G$ is degree-choosable if $G$ can be properly colored from its lists whenever each vertex $v$ gets a list of $d(v)$ colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph $G$ is degree-choosable unless each block of $G$ is a complete graph or an odd cycle; such a graph $G$ is a Gallai tree. This degree-choosability result was further strengthened to Alon—Tarsi orientations; these are orientations of $G$ in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph $G$ is degree-AT if $G$ has an Alon—Tarsi orientation in which each vertex has indegree at least 1. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladký, Král', and Schauz showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs $(G,x)$ where $G$ is a connected graph and $x$ is some specified vertex in $V(G)$. We characterize pairs such that $G$ has no Alon—Tarsi orientation in which each vertex has indegree at least 1 and $x$ has indegree at least 2. When $G$ is 2-connected, the characterization is simple to state.
Reflexive Graphs with Near Unanimity but no Semilattice Polymorphisms
Authors: Siggers Mark 
Published: January 2020

We show that every generator, in a certain set of generators for the variety of reflexive near unanimity graphs, admits a semilattice polymorphism. We then find a retract of a product of such graphs (paths, in fact) that has no semilattice polymorphism. This verifies for reflexive graphs that the variety of graphs with semilattice polymorpisms does not contain the variety of graphs with near-unanimity, or even $3$-ary near-unanimity polymorphisms.
Grasshopper Avoidance of Patterns
Authors: Dębski Michał , Pastwa Urszula , Węsek Krzysztof 
Published: January 2020

Motivated by a geometrical Thue-type problem, we introduce a new variant of the classical pattern avoidance in words, where jumping over a letter in the pattern occurrence is allowed. We say that pattern $p\in E^+$ occurs with jumps in a word $w=a_1a_2\ldots a_k \in A^+$, if there exist a non-erasing morphism $f$ from $E^*$ to $A^*$ and a sequence $(i_1, i_2, \ldots , i_l)$ satisfying $i_{j+1}\in\{ i_j+1, i_j+2 \}$ for $j=1, 2, \ldots, l-1$, such that $f(p) = a_{i_1}a_{i_2}\ldots a_{i_l}.$ For example, a pattern $xx$ occurs with jumps in a word $abdcadbc$ (for $x \mapsto abc$). A pattern $p$ is grasshopper $k$-avoidable if there exists an alphabet $A$ of $k$ elements, such that there exist arbitrarily long words over $A$ in which $p$ does not occur with jumps. The minimal such $k$ is the grasshopper avoidability index of $p$. It appears that this notion is related to two other problems: pattern avoidance on graphs and pattern-free colorings of the Euclidean plane. In particular, we show that a sequence avoiding a pattern $p$ with jumps can be a tool to construct a line $p$-free coloring of $\mathbb{R}^2$. In our work, we determine the grasshopper avoidability index of patterns $\alpha^n$ for all $n$ except $n=5$. We also show that every doubled pattern is grasshopper $(2^7+1)$-avoidable, every pattern on $k$ variables of length at least $2^k$ is grasshopper $37$-avoidable, and there exists a constant $c$ such that every pattern of length at least $c$ on $2$ variables is grasshopper $3$-avoidable (those results are proved using the entropy compression method).
Large Deviations for Permutations Avoiding Monotone Patterns
Authors: Madras Neal , Pehlivan Lerna 
Published: January 2020

For a given permutation $\tau$, let $P_N^{\tau}$ be the uniform probability distribution on the set of $N$-element permutations $\sigma$ that avoid the pattern $\tau$. For $\tau=\mu_k:=123\ldots k$, we consider $P_N^{\mu_k}(\sigma_I=J)$ where $I\sim \gamma N$ and $J\sim \delta N$ for $\gamma, \delta \in (0,1)$. If $\gamma+ \delta \neq 1$, then we are in the large deviations regime with the probability decaying exponentially, and we calculate the limiting value of $P_N^{\mu_k}(\sigma_I=J)^{1/N}$. We also observe that for $\tau = \lambda_{k,\ell} := 12\ldots\ell k(k-1)\ldots(\ell+1)$ and $\gamma+\delta<1$, the limit of $P_N^{\tau}(\sigma_I=J)^{1/N}$ is the same as for $\tau=\mu_k$.
Large Cliques in Sparse Random Intersection Graphs
Authors: Bloznelis Mindaugas , Kurauskas Valentas 
Published: January 2020

An intersection graph defines an adjacency relation between subsets $S_1,\dots, S_n$ of a finite set $W=\{w_1,\dots, w_m\}$: the subsets $S_i$ and $S_j$ are adjacent if they intersect. Assuming that the subsets are drawn independently at random according to the probability distribution $\mathbb{P}(S_i=A)=P(|A|){\binom{m}{|A|}}^{-1}$, $A\subseteq W$, where $P$ is a probability on $\{0, 1, \dots, m\}$, we obtain the random intersection graph $G=G(n,m,P)$. We establish the asymptotic order of the clique number $\omega(G)$ of a sparse random intersection graph as $n,m\to+\infty$. For $m = \Theta(n)$ we show that the maximum clique is of size $(1-\alpha/2)^{-\alpha/2}n^{1-\alpha/2}(\ln n)^{-\alpha/2}(1+o_P(1))$ in the case where the asymptotic degree distribution of $G$ is a power-law with exponent $\alpha \in (1,2)$. It is of size $\frac {\ln n} {\ln \ln n}(1+o_P(1))$ if the degree distribution has bounded variance, i.e., $\alpha>2$. We construct a simple polynomial-time algorithm which finds a clique of the optimal order $\omega(G) (1-o_P(1))$.
Counting Outerplanar Maps
Authors: Geffner Ivan , Noy Marc 
Published: January 2020

A map is outerplanar if all its vertices lie in the outer face. We enumerate various classes of rooted outerplanar maps with respect to the number of edges and vertices. The proofs involve several bijections with lattice paths. As a consequence of our results, we obtain an efficient scheme for encoding simple outerplanar maps.
Three Interactions of Holes in Two Dimensional Dimer Systems
Authors: Gilmore Tomack 
Published: January 2020

Consider the unit triangular lattice in the plane with origin $O$, drawn so that one of the sets of lattice lines is vertical. Let $l$ and $l'$ denote respectively the vertical and horizontal lines that intersect $O$. Suppose the plane contains a pair of triangular holes of side length two, distributed symmetrically with respect to $l$ and $l'$ and oriented so that both holes point toward the origin. In the following article rhombus tilings of three different regions of the plane are considered, namely: tilings of the entire plane; tilings of the half plane that lies to the left of $l$ (where $l$ is considered a free boundary, so unit rhombi are allowed to protrude halfway across it); and tilings of the half plane that lies just below the fixed boundary $l'$. Asymptotic expressions for the interactions of the triangular holes in these three different regions are obtained thus providing further evidence for Ciucu's ongoing program that seeks to draw parallels between gaps in dimer systems on the hexagonal lattice and certain electrostatic phenomena.
On the Number of Non-Zero Elements of Joint Degree Vectors
Authors: Czabarka Éva , Rauh Johannes , Sadeghi Kayvan , Short Taylor , Székely László 
Published: January 2020

Joint degree vectors give the number of edges between vertices of degree $i$ and degree $j$ for $1\le i\le j\le n-1$ in an $n$-vertex graph. We find lower and upper bounds for the maximum number of nonzero elements in a joint degree vector as a function of $n$. This provides an upper bound on the number of estimable parameters in the exponential random graph model with bidegree-distribution as its sufficient statistics.
A General Method to Determine Limiting Optimal Shapes for Edge-Isoperimetric Inequalities
Authors: Veomett Ellen , Tsukerman Emmanuel 
Published: January 2020

For a general family of graphs on $\mathbb{Z}^n$, we translate the edge-isoperimetric problem into a continuous isoperimetric problem in $\mathbb{R}^n$. We then solve the continuous isoperimetric problem using the Brunn-Minkowski inequality and Minkowski's theorem on mixed volumes. This translation allows us to conclude, under a reasonable assumption about the discrete problem, that the shapes of the optimal sets in the discrete problem approach the shape of the optimal set in the continuous problem as the size of the set grows. The solution is the zonotope defined as the Minkowski sum of the edges of the original graph. We demonstrate the efficacy of this method by revisiting some previously solved classical edge-isoperimetric problems. We then apply our method to some discrete isoperimetric problems which had not previously been solved. The complexity of those solutions suggest that it would be quite difficult to find them using discrete methods only.
A Better Lower Bound on Average Degree of Online $k$-List-Critical Graphs
Authors: Rabern Landon 
Published: January 2020

We improve the best known bounds on average degree of online $k$-list-critical graphs for $k \geqslant 6$. Specifically, for $k \geqslant 7$ we show that every non-complete online $k$-list-critical graph has average degree at least $k-1 + \frac{(k-3)^2 (2 k-3)}{k^4-2 k^3-11 k^2+28 k-14}$ and every non-complete online $6$-list-critical graph has average degree at least $5 + \frac{93}{766}$. The same bounds hold for offline $k$-list-critical graphs.
The Largest Pure Partial Planes of Order 6 Have Size 25
Authors: Gao Yibo 
Published: January 2020

In this paper, we prove that the largest pure partial plane of order 6 has size 25. At the same time, we classify all pure partial planes of order 6 and size 25 up to isomorphism. Our major approach is computer search. The search space is very large so we use combinatorial arguments to rule out some of the cases. For the remaining cases, we subdivide each search by phases and use multiple checks to reduce search space via symmetry.
Strongly Connected Multivariate Digraphs
Authors: Wu Yaokun , Xu Zeying , Zhu Yinfeng 
Published: January 2020

Generalizing the idea of viewing a digraph as a model of a linear map, we suggest a multi-variable analogue of a digraph, called a hydra, as a model of a multi-linear map. Walks in digraphs correspond to usual matrix multiplication while walks in hydras correspond to the tensor multiplication introduced by Robert Grone in 1987. By viewing matrix multiplication as a special case of this tensor multiplication, many concepts on strongly connected digraphs are generalized to corresponding ones for hydras, including strongly connectedness, periods and primitiveness, etc. We explore the structure of all possible periods of strongly connected hydras, which turns out to be related to the existence of certain kind of combinatorial designs. We also provide estimates of largest primitive exponents and largest diameters of relevant hydras. Much existing research on tensors are based on some other definitions of multiplications of tensors and so our work here supplies new perspectives for understanding irreducible and primitive nonnegative tensors.
On a Special Class of Hyper-Permutahedra
Authors: Agnarsson Geir 
Published: January 2020

Minkowski sums of simplices in ${\mathbb{R}}^n$ form an interesting class of polytopes that seem to emerge in various situations. In this paper we discuss the Minkowski sum of the simplices $\Delta_{k-1}$ in ${\mathbb{R}}^n$ where $k$ and $n$ are fixed, their flags and some of their face lattice structure. In particular, we derive a closed formula for their exponential generating flag function. These polytopes are simple, include both the simplex $\Delta_{n-1}$ and the permutahedron $\Pi_{n-1}$, and form a Minkowski basis for more general permutahedra.