cicyt UNIZAR

Combinatorics

New submissions

[ total of 42 entries: 1-42 ]
[ showing up to 2000 entries per page: fewer | more ]

New submissions for Tue, 20 Mar 18

[1]  arXiv:1803.06385 [pdf, ps, other]
Title: The $α$-normal labeling method for computing the $p$-spectral radii of uniform hypergraphs
Authors: Lele Liu, Linyuan Lu
Comments: 24 pages
Subjects: Combinatorics (math.CO)

Let $G$ be an $r$-uniform hypergraph of order $n$. For each $p\geq 1$, the $p$-spectral radius $\lambda^{(p)}(G)$ is defined as \[ \lambda^{(p)}(G):=\max_{|x_1|^p+\cdots+|x_n|^p=1} r\sum_{\{i_1,\ldots,i_r\}\in E(G)}x_{i_1}\cdots x_{i_r}. \] The $p$-spectral radius was introduced by Keevash-Lenz-Mubayi, and subsequently studied by Nikiforov in 2014. The most extensively studied case is when $p=r$, and $\lambda^{(r)}(G)$ is called the spectral radius of $G$. The $\alpha$-normal labeling method, which was introduced by Lu and Man in 2014, is effective method for computing the spectral radii of uniform hypergraphs. It labels each corner of an edge by a positive number so that the sum of the corner labels at any vertex is $1$ while the product of all corner labels at any edge is $\alpha$. Since then, this method has been used by many researchers in studying $\lambda^{(r)}(G)$. In this paper, we extend Lu and Man's $\alpha$-normal labeling method to the $p$-spectral radii of uniform hypergraphs for $p\ne r$; and find some applications.

[2]  arXiv:1803.06394 [pdf, ps, other]
Title: Combinatorial proofs of two Euler type identities due to Andrews
Comments: 14 pages
Subjects: Combinatorics (math.CO); Number Theory (math.NT)

We prove combinatorially some identities related to Euler's partition identity (the number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts). They were conjectured by Beck and proved by Andrews via generating functions.
Let $a(n)$ be the number of partitions of $n$ such that the set of even parts has exactly one element, $b(n)$ be the difference between the number of parts in all odd partitions of $n$ and the number of parts in all distinct partitions of $n$, and $c(n)$ be the number of partitions of $n$ in which exactly one part is repeated. Then, $a(n)=b(n)=c(n)$. The identity $a(n)=c(n)$ was proved combinatorially (in greater generality) by Fu and Tang. We prove combinatorially that $a(n)=b(n)$ and $b(n)=c(n)$. Our proof relies on bijections between a set and a multiset, where the partitions in the multiset are decorated with bit strings. Let $c_1(n)$ be the number of partitions of $n$ such that there is exactly one part occurring three times while all other parts occur only once and let $b_1(n)$ to be the difference between the total number of parts in the partitions of $n$ into distinct parts and the total number of different parts in the partitions of $n$ into odd parts. We prove combinatorially that $c_1(n)=b_1(n)$. In addition to these results by Andrews, we prove combinatorially that $b_1(n)=a_1(n)$, where $a_1(n)$ counts partitions of $n$ such that the set of even parts has exactly one element and satisfying some additional conditions. Moreover, we offer an analog of these results for the number of partitions of $n$ with exactly one part occurring two times while all other parts occur only once.

[3]  arXiv:1803.06408 [pdf, ps, other]
Title: Three Études on a sequence transformation pipeline
Authors: Paul Barry
Comments: 41 pages
Subjects: Combinatorics (math.CO)

We study a sequence transformation pipeline that maps certain sequences with rational generating functions to permutation-based sequence families of combinatorial significance. Many of the number triangles we encounter can be related to simplicial objects such as the associahedron and the permutahedron. The linkages between these objects is facilitated by the use of the previously introduced $\mathcal{T}$ transform.

[4]  arXiv:1803.06507 [pdf, ps, other]
Title: Covering Arrays for Equivalence Classes of Words
Comments: 17 pages
Subjects: Combinatorics (math.CO)

Covering arrays for words of length $t$ over a $d$ letter alphabet are $k \times n$ arrays with entries from the alphabet so that for each choice of $t$ columns, each of the $d^t$ $t$-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case words are equivalent if they induce the same partition of a $t$ element set. In the second case, words of the same weight are equivalent. In both cases we produce logarithmic upper bounds on the minimum size $k=k(n)$ of a covering array. Definitive results for $t=2,3,4$, as well as general results, are provided.

[5]  arXiv:1803.06568 [pdf, ps, other]
Title: Splittable and unsplittable graphs and configurations
Comments: 19 pages, 10 figures
Subjects: Combinatorics (math.CO)

We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic $(n_3)$ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most 60 vertices with respect to splittability. Finally, we show that all cyclic flag-transitive configurations with the exception of the Fano plane and the M\"obius-Kantor configuration are splittable.

[6]  arXiv:1803.06636 [pdf, ps, other]
Title: Complexity problems in enumerative combinatorics
Authors: Igor Pak
Comments: 30 pages; an expanded version of the ICM 2018 paper (Section 4 added, refs expanded)
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); History and Overview (math.HO); Probability (math.PR)

We give a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.

[7]  arXiv:1803.06664 [pdf, ps, other]
Title: An Introduction to the Moebius Function
Authors: Chris Godsil
Comments: This is a slightly revised version of an old set of notes that have been available on my webpage for some time. The changes are not substantial. I've eliminated some old typos and introduced some ne ones (doubtless), and added one new section
Subjects: Combinatorics (math.CO)

This is an introduction to the M\"obius function of a poset. The chief novelty is in the exposition. We show how order-preserving maps from one poset to another can be used to relate their M\"obius functions. We derive the basic results on the M\"obius function, applying them in particular to geometric lattices.

[8]  arXiv:1803.06706 [pdf, ps, other]
Title: Descent distribution on Catalan words avoiding a pattern of length at most three
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

Catalan words are particular growth-restricted words over the set of non-negative integers, and they represent still another combinatorial class counted by the Catalan numbers. We study the distribution of descents on the sets of Catalan words avoiding a pattern of length at most three: for each such a pattern $p$ we provide a bivariate generating function where the coefficient of $x^ny^k$ in its series expansion is the number of length $n$ Catalan words with $k$ descents and avoiding $p$. As a byproduct, we enumerate the set of Catalan words avoiding $p$, and we provide the popularity of descents on this set. Some of the obtained enumerating sequences are not yet recorded in the On-line Encyclopedia of Integer Sequences.

[9]  arXiv:1803.06710 [pdf, other]
Title: Almost all string graphs are intersection graphs of plane convex sets
Comments: This is the full version of a paper appearing in the proceedings of SoCG 2018
Subjects: Combinatorics (math.CO); Computational Geometry (cs.CG)

A {\em string graph} is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of {\em almost all} string graphs on $n$ vertices can be partitioned into {\em five} cliques such that some pair of them is not connected by any edge ($n\rightarrow\infty$). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that {\em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets.

[10]  arXiv:1803.06768 [pdf, ps, other]
Title: Gallai's path decomposition conjecture for triangle-free planar graphs
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)

A path decomposition of a graph $G$ is a collection of edge-disjoint paths of $G$ that covers the edge set of $G$. Gallai (1968) conjectured that every connected graph on $n$ vertices admits a path decomposition of cardinality at most $\lfloor (n+1)/2\rfloor$. Gallai's Conjecture has been verified for many classes of graphs. In particular, Lov\'asz (1968) verified this conjecture for graphs with at most one vertex with even degree, and Pyber (1996) verified it for graphs in which every cycle contains a vertex with odd degree. Recently, Bonamy and Perrett (2016) verified Gallai's Conjecture for graphs with maximum degree at most $5$, and Botler et al. (2017) verified it for graphs with treewidth at most $3$. In this paper, we verify Gallai's Conjecture for triangle-free planar graphs.

[11]  arXiv:1803.06788 [pdf, other]
Title: The Cohomology for Wu Characteristics
Authors: Oliver Knill
Comments: 40 pages, 12 figures
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Algebraic Topology (math.AT)

While Euler characteristic X(G)=sum_x w(x) super counts simplices, Wu characteristics w_k(G) = sum_(x_1,x_2,...,x_k) w(x_1)...w(x_k) super counts simultaneously pairwise interacting k-tuples of simplices in a finite abstract simplicial complex G. More general is the k-intersection number w_k(G_1,...G_k), where x_i in G_i. We define interaction cohomology H^p(G_1,...,G_k) compatible with w_k and invariant under Barycentric subdivison. It allows to distinguish spaces which simplicial cohomology can not: it can identify algebraically the Moebius strip and the cylinder for example. The cohomology satisfies the Kuenneth formula: the Poincare polynomials p_k(t) are ring homomorphisms from the strong ring to the ring of polynomials in t. The Dirac operator D=d+d^* defines the block diagonal Hodge Laplacian L=D^2 which leads to the generalized Hodge correspondence b_p(G)=dim(H^p_k(G)) = dim(ker(L_p)) and Euler-Poincare w_k(G)=sum_p (-1)^p dim(H^p_k(G)) for Wu characteristic. Also, like for traditional simplicial cohomology, isospectral Lax deformation D' = [B(D),D], with B(t)=d(t)-d^*(t)-ib(t), D(t)=d(t)+d(t)^* + b(t) can deform the exterior derivative d. The Brouwer-Lefschetz fixed point theorem generalizes to all Wu characteristics: given an endomorphism T of G, the super trace of its induced map on k'th cohomology defines a Lefschetz number L_k(T). The Brouwer index i_T,k(x_1,...,x_k) = product_j=1^k w(x_j) sign(T|x_j) attached to simplex tuple which is invariant under T leads to the formula L_k(T) = sum_T(x)=x i_T,k(x). For T=Id, the Lefschetz number L_k(Id) is equal to the k'th Wu characteristic w_k(G) of the graph G and the Lefschetz formula reduces to the Euler-Poincare formula for Wu characteristic.

[12]  arXiv:1803.06806 [pdf, ps, other]
Title: On certain unimodal sequences and strict partitions
Comments: 11 pages, 2 figures, 1 table
Subjects: Combinatorics (math.CO)

Building on a bijection of Vandervelde, we enumerate certain unimodal sequences whose alternating sum equals zero. This enables us to refine the enumeration of strict partitions with respect to the number of parts and the BG-rank.

[13]  arXiv:1803.06825 [pdf, ps, other]
Title: A counterexample to Las Vergnas' strong map conjecture on realizable oriented matroids
Authors: Pei Wu
Comments: 5 pages
Subjects: Combinatorics (math.CO)

The Las Vergnas' strong map conjecture, states that any strong map of oriented matroids $f:\mathcal{M}_1\rightarrow\mathcal{M}_2$ can be factored into extensions and contractions. The conjecture is known to be false due to a construction by Richter-Gebert, he find a non-factorizable strong map $f:\mathcal{M}_1\rightarrow\mathcal{M}_2$, however in his example $\mathcal{M}_1$ is not realizable. The problem that whether there exists a non-factorizable strong map between realizable oriented matroids still remains open. In this paper we provide a counterexample to the strong map conjecture on realizable oriented matroids, which is a strong map $f:\mathcal{M}_1\rightarrow\mathcal{M}_2$, $\mathcal{M}_1$ is an alternating oriented matroid of rank $4$ and $f$ has corank $2$. We prove it is not factorizable by showing that there is no uniform oriented matroid $\mathcal{M}^{\prime}$ of rank $3$ such that $\mathcal{M}_1\rightarrow\mathcal{M}^{\prime}\rightarrow\mathcal{M}_2$.

[14]  arXiv:1803.06879 [pdf, other]
Title: The tree of numerical semigroups with low multiplicity
Subjects: Combinatorics (math.CO); Commutative Algebra (math.AC)

We show that the number of numerical semigroups with multiplicity three, four or five and fixed genus is increasing as a function in the genus. To this end we use the Kunz polytope for these multiplicities. Counting numerical semigroups with fixed multiplicity and genus is then an integer partition problem with some extra conditions (those of membership to the Kunz polytope). For the particular case of multiplicity four, we are able to prove that the number of numerical semigroups with multiplicity four and genus $g$ is the number of partitions $x+y+z=g+6$ with $0<x\le y\le z$, $x\neq 1$, $y\neq 2$ and $z\neq 3$.

[15]  arXiv:1803.06914 [pdf, ps, other]
Title: Mixing Time of Markov chain of the Knapsack Problem
Comments: 9 pages, 2 figures
Subjects: Combinatorics (math.CO); Data Structures and Algorithms (cs.DS); Probability (math.PR)

To find the number of assignments of zeros and ones satisfying a specific Knapsack Problem is $\#P$ hard, so only approximations are envisageable. A Markov chain allowing uniform sampling of all possible solutions is given by Luby, Randall and Sinclair. In 2005, Morris and Sinclair, by using a flow argument, have shown that the mixing time of this Markov chain is $\mathcal{O}(n^{9/2+\epsilon})$, for any $\epsilon > 0$. By using a canonical path argument on the distributive lattice structure of the set of solutions, we obtain an improved bound, the mixing time is given as $\tau_{_{x}}(\epsilon) \leq n^{3} \ln (16 \epsilon^{-1})$.

[16]  arXiv:1803.06915 [pdf, other]
Title: Exploiting symmetry in network analysis
Comments: Main Text (7 pages) plus Supplementary Information (24 pages)
Subjects: Combinatorics (math.CO); Social and Information Networks (cs.SI); Data Analysis, Statistics and Probability (physics.data-an); Physics and Society (physics.soc-ph)

Virtually all network analyses involve structural measures or metrics between pairs of vertices, or of the vertices themselves. The large amount of redundancy present in real-world networks is inherited by such measures, and this has practical consequences which have not yet been explored in full generality, nor systematically exploited by network practitioners. Here we develop a complete framework to study and quantify the effect of redundancy on arbitrary network measures, and explain how to exploit redundancy in practice, achieving, for instance, remarkable lossless compression and computational reduction ratios in several real-world networks against some popular measures.

[17]  arXiv:1803.07020 [pdf, ps, other]
Title: An efficient algorithm for packing cuts and (2,3)-metrics in a planar graph with three holes
Comments: 25 pages, 10 figures
Subjects: Combinatorics (math.CO)

We consider a planar graph $G$ in which the edges have nonnegative integer lengths such that the length of every cycle of $G$ is even, and three faces are distinguished, called holes in $G$. It is known that there exists a packing of cuts and (2,3)-metrics with nonnegative integer weights in $G$ which realizes the distances within each hole. We develop a strongly polynomial purely combinatorial algorithm to find such a packing.

[18]  arXiv:1803.07042 [pdf, ps, other]
Title: On the $k$-independence number of graphs
Subjects: Combinatorics (math.CO)

This paper improves and unifies the existing spectral bounds on the $k$-independence number of a graph, which is the maximum size of a set of vertices at pairwise distance greater than $k$. The previous bounds known in the literature follow as a corollary of the main results in this work.

Cross-lists for Tue, 20 Mar 18

[19]  arXiv:1803.06366 (cross-list from math.CT) [pdf, ps, other]
Title: Graphs, Ultrafilters and Colourability
Authors: Felix Dilke
Comments: 12 pages
Subjects: Category Theory (math.CT); Combinatorics (math.CO)

Let $\beta$ be the functor from Set to CHaus which maps each discrete set X to its Stone-Cech compactification, the set $\beta$ X of ultrafilters on X. Every graph G with vertex set V naturally gives rise to a graph $\beta G$ on the set $\beta V$ of ultrafilters on V . In what follows, we interrelate the properties of G and $\beta G$. Perhaps the most striking result is that G can be finitely coloured iff $\beta G$ has no loops.

[20]  arXiv:1803.06411 (cross-list from math.AG) [pdf, ps, other]
Title: The 21 reducible polars of Klein's quartic
Comments: 28 pages, contains Singular's script
Subjects: Algebraic Geometry (math.AG); Commutative Algebra (math.AC); Combinatorics (math.CO)

We describe the singularities and related properties of the arrangement of 21 reducible polars of Klein's quartic, containing Klein's well-known arrangement of $21$ lines.

[21]  arXiv:1803.06496 (cross-list from math.OC) [pdf, ps, other]
Title: A simple algorithm for Max Cut
Comments: Submitted to Conference on March 17, 2018
Subjects: Optimization and Control (math.OC); Combinatorics (math.CO); Numerical Analysis (math.NA)

Based on an explicit equivalent continuous optimization problem, we propose a simple continuous iterative algorithm for Max Cut, which converges to a local optimum in finite steps. The inner subproblem is solved analytically and thus no optimization solver is called. Preliminary results on G-set demonstrate the performance. In particular, the ratio between the best cut values achieved by the simple algorithm without any local breakout techniques and the best known ones is of at least $0.986$.

[22]  arXiv:1803.06539 (cross-list from cs.DM) [pdf, other]
Title: The Graph Structure of Chebyshev Polynomials over Finite Fields and Applications
Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

We completely describe the functional graph associated to iterations of Chebyshev polynomials over finite fields. Then, we use our structural results to obtain estimates for the average rho length, average number of connected components and the expected value for the period and preperiod of iterating Chebyshev polynomials.

[23]  arXiv:1803.06592 (cross-list from math.RT) [pdf, ps, other]
Title: Layer structure of irreducible Lie algebra modules
Authors: Jorgen Rasmussen
Comments: 23 pages
Subjects: Representation Theory (math.RT); High Energy Physics - Theory (hep-th); Mathematical Physics (math-ph); Combinatorics (math.CO)

Let $\mathfrak{g}$ be a finite-dimensional simple complex Lie algebra. A layer sum is introduced as the sum of formal exponentials of the distinct weights appearing in an irreducible $\mathfrak{g}$-module. It is argued that the character of every finite-dimensional irreducible $\mathfrak{g}$-module admits a decomposition in terms of layer sums, with only non-negative integer coefficients. Ensuing results include a new approach to the computation of Weyl characters and weight multiplicities, and a closed-form expression for the number of distinct weights in a finite-dimensional irreducible $\mathfrak{g}$-module. The latter is given by a polynomial in the Dynkin labels, of degree equal to the rank of $\mathfrak{g}$.

[24]  arXiv:1803.06858 (cross-list from cs.DS) [pdf, ps, other]
Title: An improved isomorphism test for bounded-tree-width graphs
Comments: 34 pages, 1 figures
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

We give a new fpt algorithm testing isomorphism of $n$-vertex graphs of tree width $k$ in time $2^{k\operatorname{polylog} (k)}\operatorname{poly} (n)$, improving the fpt algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time $2^{\mathcal{O}(k^5\log k)}\operatorname{poly} (n)$. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree width $k$. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai's algorithm as a black box in one place.
We also give a second algorithm which, at the price of a slightly worse running time $2^{\mathcal{O}(k^2 \log k)}\operatorname{poly} (n)$, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also used as a canonization algorithm.

[25]  arXiv:1803.06901 (cross-list from math.RT) [pdf, ps, other]
Title: Cyclic Sieving and Cluster Duality for Grassmannian
Comments: 40 pages
Subjects: Representation Theory (math.RT); Mathematical Physics (math-ph); Algebraic Geometry (math.AG); Combinatorics (math.CO)

We introduce a decorated configuration space $\mathscr{C}onf_n^\times(a)$ with a potential function $\mathcal{W}$. We prove the cluster duality conjecture of Fock-Goncharov for Grassmannians, that is, the tropicalization of $(\mathscr{C}onf_n^\times(a), \mathcal{W})$ canonically parametrizes a linear basis of the homogenous coordinate ring of the Grassmannian ${\rm Gr}_a(n)$. We prove that $(\mathscr{C}onf_n^\times(a), \mathcal{W})$ is equivalent to the mirror Landau-Ginzburg model of Grassmannian considered by Marsh-Rietsch and Rietsch-Williams. As an application, we show a cyclic sieving phenomenon involving plane partitions under a sequence of piecewise-linear toggles.

Replacements for Tue, 20 Mar 18

[26]  arXiv:1503.06556 (replaced) [pdf, ps, other]
Title: 3-connected Reduction for Regular Graph Covers
Comments: The journal version of the first part of arXiv:1402.3774
Subjects: Combinatorics (math.CO)
[27]  arXiv:1703.07301 (replaced) [pdf, other]
Title: Linearly many rainbow trees in properly edge-coloured complete graphs
Subjects: Combinatorics (math.CO)
[28]  arXiv:1704.00889 (replaced) [pdf, ps, other]
Title: Crystal analysis of type $C$ Stanley symmetric functions
Comments: 39 pages
Journal-ref: Electronic Journal of Combinatorics 24(3) (2017) #P3.51
Subjects: Combinatorics (math.CO)
[29]  arXiv:1705.02166 (replaced) [pdf, ps, other]
Title: Lines in Euclidean Ramsey theory
Comments: 7 pages
Subjects: Combinatorics (math.CO)
[30]  arXiv:1705.04735 (replaced) [pdf, ps, other]
Title: On the weak Roman domination number of lexicographic product graphs
Subjects: Combinatorics (math.CO)
[31]  arXiv:1711.07587 (replaced) [pdf, other]
Title: Domination structure for number three
Authors: Misa Nakanishi
Subjects: Combinatorics (math.CO)
[32]  arXiv:1801.03972 (replaced) [pdf, ps, other]
Title: Extremal $G$-free induced subgraphs of Kneser graphs
Comments: Minor changes
Subjects: Combinatorics (math.CO)
[33]  arXiv:1802.09051 (replaced) [pdf, ps, other]
Title: Graphs with equal domination and covering numbers
Comments: 17 pages, 6 figures
Subjects: Combinatorics (math.CO)
[34]  arXiv:1802.09312 (replaced) [pdf, other]
Title: DP-3-coloring of some planar graphs
Comments: 15 pages, five figures
Subjects: Combinatorics (math.CO)
[35]  arXiv:1803.02792 (replaced) [pdf, ps, other]
Title: Lozenge tilings of hexagons with central holes and dents
Authors: Tri Lai
Comments: Version 2: 93 pages and many figures; list of references and main proofs are updated. Comments are welcome!
Subjects: Combinatorics (math.CO)
[36]  arXiv:1803.05775 (replaced) [pdf, ps, other]
Title: $\mathfrak{q}$-crystal structure on primed tableaux and on signed unimodal factorizations of reduced words of type $B$
Authors: Toya Hiroshima
Comments: 25 pages. Reference [1] added; Remark 3.2 deleted; arXiv admin note: text overlap with arXiv:1704.00889 by other authors
Subjects: Combinatorics (math.CO)
[37]  arXiv:1609.02360 (replaced) [pdf, ps, other]
Title: Canonical syzygies of smooth curves on toric surfaces
Subjects: Algebraic Geometry (math.AG); Combinatorics (math.CO)
[38]  arXiv:1705.00429 (replaced) [src]
Title: Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs
Comments: The algorithm for block graphs in this manuscript contains some flaws. More precisely, Proposition 20 is not correct. Therefore, we withdraw this manuscript
Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[39]  arXiv:1706.01015 (replaced) [pdf, other]
Title: The split-and-drift random graph, a null model for speciation
Comments: added Proposition 2.4 and formal proofs of Proposition 2.3 and 2.6
Subjects: Probability (math.PR); Combinatorics (math.CO); Populations and Evolution (q-bio.PE)
[40]  arXiv:1712.00434 (replaced) [pdf, other]
Title: On the treewidth of triangulated 3-manifolds
Comments: 23 pages, 3 figures, 1 table. An extended abstract of this paper is to appear in the Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), Budapest, June 11-14 2018
Subjects: Geometric Topology (math.GT); Computational Geometry (cs.CG); Combinatorics (math.CO)
[41]  arXiv:1801.01165 (replaced) [pdf, other]
Title: Automorphism groups and Ramsey properties of sparse graphs
Comments: 40 pages, 3 figures, new proof of Theorem 3.19 and other minor revisions
Subjects: Group Theory (math.GR); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Dynamical Systems (math.DS); Logic (math.LO)
[42]  arXiv:1802.08934 (replaced) [pdf, other]
Title: The Archimedean limit of random sorting networks
Authors: Duncan Dauvergne
Comments: 58 pages, 5 figures. Changes from v1: the proof of Lemma 7.2 has been lengthened for clarity; otherwise, only minor edits have been made
Subjects: Probability (math.PR); Combinatorics (math.CO)
[ total of 42 entries: 1-42 ]
[ showing up to 2000 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)