Topic overview

math.CO

Map preview

Topic at a glance

8936works

11175authors indexed

preprint2015arXiv

A study of a family of generating functions of Nelsen-Schmidt type and some identities on restricted barred preferential arrangements

A preferential arrangement of a set $X_n=\{1,2,...,n\}$ is an ordered partition of the set $X_n$ induced with a linear order. Separation of blocks of a preferential arrangement with bars result in the notation of barred preferential arrangements. Roger Nelsen and Harvey Schmidt have proposed the family of generating functions $P^k(m)=\frac{e^{km}}{2-e^m}$ ; which for $k=0$ and for $k=2$ they have shown that the generating functions are exponential generating functions for the number of preferential arrangements of a set $X_n$ and the number of chains in the power set of $X_n$ respectively. In this study we propose combinatorial structures whose integer sequences are generated by members of the family for all values of $k$ in $\mathbb{Z}^+$ . To do this we use a notion of restricted barred preferential arrangements. We then propose a more general family of generating functions $P^{r}_{j}(m)=\frac{e^{rm}}{(2-e^m)^j}$ for $r,j\in\mathbb{Z^+}$ . We derive some new identities on restricted barred preferential arrangements and give their combinatorial proofs. We also propose conjectures on number of restricted barred preferential arrangements.

preprint2016arXiv

Complete graph immersions in dense graphs

In this article we consider the relationship between vertex coloring and the immersion order. Specifically, a conjecture proposed by Abu-Khzam and Langston in 2003, which says that the complete graph with $t$ vertices can be immersed in any $t$ -chromatic graph, is studied. First, we present a general result about immersions and prove that the conjecture holds for graphs whose complement does not contain any induced cycle of length four and also for graphs having the property that every set of five vertices induces a subgraph with at least six edges. Then, we study the class of all graphs with independence number less than three, which are graphs of interest for Hadwiger's Conjecture. We study such graphs for the immersion-analog. If Abu-Khzam and Langston's conjecture is true for this class of graphs, then an easy argument shows that every graph of independence number less than $3$ contains $K_{\left\lceil\frac{n}{2}\right\rceil}$ as an immersion. We show that the converse is also true. That is, if every graph with independence number less than $3$ contains an immersion of $K_{\left\lceil\frac{n}{2}\right\rceil}$ , then Abu-Khzam and Langston's conjecture is true for thi

preprint2013arXiv

Random subgraphs make identification affordable

An identifying code of a graph is a dominating set which uniquely determines all the vertices by their neighborhood within the code. Whereas graphs with large minimum degree have small domination number, this is not the case for the identifying code number (the size of a smallest identifying code), which indeed is not even a monotone parameter with respect to graph inclusion. We show that every graph $G$ with $n$ vertices, maximum degree $Δ=ω(1)$ and minimum degree $δ\geq c\logΔ$ , for some constant $c>0$ , contains a large spanning subgraph which admits an identifying code with size $O\left(\frac{n\logΔ}δ\right)$ . In particular, if $δ=Θ(n)$ , then $G$ has a dense spanning subgraph with identifying code $O\left(\log n\right)$ , namely, of asymptotically optimal size. The subgraph we build is created using a probabilistic approach, and we use an interplay of various random methods to analyze it. Moreover we show that the result is essentially best possible, both in terms of the number of deleted edges and the size of the identifying code.

preprint2016arXiv

On statistical learning via the lens of compression

This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. The central theme of this work is establishing equivalences between learnability and compressibility, and utilizing these equivalences in the study of statistical learning theory. We begin with the setting of multiclass categorization (zero/one loss). We prove that in this case learnability is equivalent to compression of logarithmic sample size, and that uniform convergence implies compression of constant size. We then consider Vapnik's general learning setting: we show that in order to extend the compressibility-learnability equivalence to this case, it is necessary to consider an approximate variant of compression. Finally, we provide some applications of the compressibility-learnability equivalences: (i) Agnostic-case learnability and realizable-case learnability are equivalent in multiclass categorization problems (in terms of sample complexity). (ii) This equivalence between agnostic-case learnability and realizable-case learnability does not hold for general learning problems: Ther

preprint2017arXiv

$\text{VC}_{\ell}$ -dimension and the jump to the fastest speed of a hereditary $\mathcal{L}$ -property

In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $\text{VC}$ -dimension called $\text{VC}_{\ell}$ -dimension. Let $\mathcal{L}$ be a finite relational language with maximum arity $r$ . A hereditary $\mathcal{L}$ -property is a class of finite $\mathcal{L}$ -structures closed under isomorphism and substructures. The \emph{speed} of a hereditary $\mathcal{L}$ -property $\mathcal{H}$ is the function which sends $n$ to $|\mathcal{H}_n|$ , where $\mathcal{H}_n$ is the set of elements of $\mathcal{H}$ with universe $\{1,\ldots, n\}$ . It was previously known there exists a gap between the fastest possible speed of a hereditary $\mathcal{L}$ -property and all lower speeds, namely between the speeds $2^{Θ(n^r)}$ and $2^{o(n^r)}$ . We strengthen this gap by showing that for any hereditary $\mathcal{L}$ -property $\mathcal{H}$ , either $|\mathcal{H}_n|=2^{Θ(n^r)}$ or there is $ε>0$ such that for all large enough $n$ , $|\mathcal{H}_n|\leq 2^{n^{r-ε}}$ . This improves what was previously known about this gap when $r\geq 3$ . Further, we show this gap can be characterized in terms of $\text{VC}_{\ell}$ -dimension, therefore draw

preprint2017arXiv

A Tutte polynomial for maps

We follow the example of Tutte in his construction of the dichromate of a graph (that is, the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial in order to construct a new polynomial invariant of maps (graphs embedded in orientable surfaces). We call this the surface Tutte polynomial. The surface Tutte polynomial of a map contains the Las Vergnas polynomial, Bollobás-Riordan polynomial and Kruskhal polynomial as specializations. By construction, the surface Tutte polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests.

preprint2016arXiv

Broken circuit complexes of series-parallel networks

Let $(h_0,h_1,\ldots,h_s)$ with $h_s\ne0$ be the $h$ -vector of the broken circuit complex of a series-parallel network $M$ . Let $G$ be a graph whose cycle matroid is $M$ . We give a formula for the difference $h_{s-1}-h_1$ in terms of an ear decomposition of $G$ . A number of applications of this formula are provided, including several bounds for $h_{s-1}-h_1$ , a characterization of outerplanar graphs, and a solution to a conjecture on $A$ -graphs posed by Fenton. We also prove that $h_{s-2}\geq h_2$ when $s\geq 4$ .

preprint2013arXiv

s-Lecture Hall Partitions, Self-Reciprocal Polynomials, and Gorenstein Cones

In 1997, Bousquet-Melou and Eriksson initiated the study of lecture hall partitions, a fascinating family of partitions that yield a finite version of Euler's celebrated odd/distinct partition theorem. In subsequent work on s-lecture hall partitions, they considered the self-reciprocal property for various associated generating functions, with the goal of characterizing those sequences s that give rise to generating functions of the form $((1-q^{e_1})(1-q^{e_2})...(1-q^{e_n}))^{-1}$ . We continue this line of investigation, connecting their work to the more general context of Gorenstein cones. We focus on the Gorenstein condition for s-lecture hall cones when s is a positive integer sequence generated by a second-order homogeneous linear recurrence with initial values 0 and 1. Among such sequences s, we prove that the n-dimensional s-lecture hall cone is Gorenstein for all n greater than or equal to 1 if and only if s is an l-sequence. One consequence is that among such sequences s, unless s is an l-sequence, the generating function for the s-lecture hall partitions can have the form $((1-q^{e_1})(1-q^{e_2})...(1-q^{e_n}))^{-1}$ for at most finitely many n. We also apply the res

preprint2016arXiv

Word Length Perturbations in Certain Symmetric Presentations of Dihedral Groups

Given a finite group with a generating subset there is a well-established notion of length for a group element given in terms of its minimal length expression as a product of elements from the generating set. Recently, certain quantities called $λ_{1}$ and $λ_{2}$ have been defined that allow for a precise measure of how stable a group is under certain types of small perturbations in the generating expressions for the elements of the group. These quantities provide a means to measure differences among all possible paths in a Cayley graph for a group, establish a group theoretic analog for the notion of stability in nonlinear dynamical systems, and play an important role in the application of groups to computational genomics. In this paper, we further expose the fundamental properties of $λ_{1}$ and $λ_{2}$ by establishing their bounds when the underlying group is a dihedral group. An essential step in our approach is to completely characterize so-called symmetric presentations of the dihedral groups, providing insight into the manner in which $λ_{1}$ and $λ_{2}$ interact with finite group presentations. This is of interest independent of the study of the quantities $λ_{1},\; λ_{2}$

preprint2017arXiv

Enumeration of Fuss-Schröder paths

In this paper we enumerate the number of $(k, r)$ -Fuss-Schröder paths of type $λ$ . Y. Park and S. Kim studied small Schröder paths with type $λ$ . Generalizing the results to small $(k, r)$ -Fuss-Schröder paths with type $λ$ , we give a combinatorial interpretation for the number of small $(k, r)$ -Fuss-Schröder paths of type $λ$ by using Chung-Feller style. We also give two sets of sparse noncrossing partitions of $[2(k + 1)n + 1]$ and $[2(k + 1)n + 2]$ which are in bijection with the set of all small and large, respectively, $(k, r)$ -Fuss-Schröder paths of type $λ$ .

preprint2017arXiv

Coloring graphs of various maximum degree from random lists

Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $Δ=Δ(n)$ . Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$ -subsets of a color set $\mathcal{C}$ of size $σ= σ(n)$ . Such a list assignment is called a \emph{random $(k,\mathcal{C})$ -list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$ ) of the existence of a proper coloring $φ$ of $G$ , such that $φ(v) \in L(v)$ for every vertex $v$ of $G$ , a so-called $L$ -coloring. We give various lower bounds on $σ$ , in terms of $n$ , $k$ and $Δ$ , which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$ -coloring of $G$ . In particular, we show, for all fixed $k$ and growing $n$ , that if $σ(n) = ω(n^{1/k^2} Δ^{1/k})$ and $Δ=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$ , then the probability that $G$ has an $L$ -coloring tends to 1 as $n \rightarrow \infty$ . If $k\geq 2$ and $Δ= Ω(n^{1/2})$ , then the same conclusion holds provided that $σ=ω(Δ)$ . We also give related results for other bounds on $Δ$ , when $k$ is constant or a strictly increasing function of $n$ .

preprint2016arXiv

A complexity theorem for the Novelli-Pak-Stoyanovskii algorithm

We describe two aspects of the behaviour of entries of Young tableaux during the application of the Novelli-Pak-Stoyanovskii algorithm. We derive two theorems which both contain a generalized version of a conjecture by Krattenthaler and Müller concerning the complexity of the Novelli-Pak-Stoyanovskii algorithm as corollary.

preprint2016arXiv

Notes on use of generalized entropies in counting

We address an idea of applying generalized entropies in counting problems. First, we consider some entropic properties that are essential for such purposes. Using the $α$ -entropies of Tsallis-Havrda-Charvát type, we derive several results connected with Shearer's lemma. In particular, we derive upper bounds on the maximum possible cardinality of a family of $k$ -subsets, when no pairwise intersections of these subsets may coincide. Further, we revisit the Minc conjecture. Our approach leads to a family of one-parameter extensions of Brégman's theorem. A utility of the obtained bounds is explicitly exemplified.

preprint2016arXiv

On Prefix Normal Words and Prefix Normal Forms

A $1$ -prefix normal word is a binary word with the property that no factor has more $1$ s than the prefix of the same length; a $0$ -prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of $1$ s and $0$ s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We give enumeration results on $\textit{pnw}(n)$ , the number of prefix normal words of length $n$ , showing that, for sufficiently large $n$ , $2^{n-4 \sqrt{n \lg n}} \le \textit{pnw}(n) \le 2^{n - \lg n + 1}.$ For fixed density (number of $1$ s), we show that the ordinary generating function of the number of prefix normal words of length $n$ and density $d$ is a rational function. Finally, we give experimental r

preprint2017arXiv

Rational Polygons: Odd Compression Ratio and Odd Plane Coverings

Let P be a polygon with rational vertices in the plane. We show that for any finite odd-sized collection of translates of P, the area of the set of points lying in an odd number of these translates is bounded away from 0 by a constant depending on P alone. The key ingredient of the proof is a construction of an odd cover of the plane by translates of P. That is, we establish a family F of translates of P covering (almost) every point in the plane a uniformly bounded odd number of times.

preprint2016arXiv

New Existence and Nonexistence Results for Strong External Difference Families

In this paper, we use character-theoretic techniques to give new nonexistence results for $(n,m,k,λ)$ -strong external difference families (SEDFs). We also use cyclotomic classes to give two new classes of SEDFs with $m=2$ .

preprint2016arXiv

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2

We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution to Cauchy's additive functional equation on bounded convex domains. This provides a k-dimensional generalization of the so-called interval lemma, allowing us to deduce affine properties of the function from certain additivity relations. (2) We study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. (3) We give a theory of non-extremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under the assumption of a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function.

preprint2017arXiv

The second Feng-Rao number for codes coming from telescopic semigroups

In this manuscript we show that the second Feng-Rao number of any telescopic numerical semigroup agrees with the multiplicity of the semigroup. To achieve this result we first study the behavior of Apéry sets under gluings of numerical semigroups. These results provide a bound for the second Hamming weight of one-point Algebraic Geometry codes, which improves upon other estimates such as the Griesmer Order Bound.

preprint2016arXiv

Some extremal results on complete degenerate hypergraphs

Let $K^{(r)}_{s_1,s_2,\cdots,s_r}$ be the complete $r$ -partite $r$ -uniform hypergraph and $ex(n,K^{(r)}_{s_1,s_2,\cdots,s_r})$ be the maximum number of edges in any $n$ -vertex $K^{(r)}_{s_1,s_2,\cdots,s_r}$ -free $r$ -uniform hypergraph. It is well-known in the graph case that $ex(n,K_{s,t})=Θ(n^{2-1/s})$ when $t$ is sufficiently larger than $s$ . In this note, we generalize the above to hypergraphs by showing that if $s_r$ is sufficiently larger than $s_1,s_2,\cdots,s_{r-1}$ then $ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})=Θ\left(n^{r-\frac{1}{s_1s_2\cdots s_{r-1}}}\right).$ This follows from a more general Turán type result we establish in hypergraphs, which also improves and generalizes some recent results of Alon and Shikhelman. The lower bounds of our results are obtained by the powerful random algebraic method of Bukh. Another new, perhaps unsurprising insight which we provide here is that one can also use the random algebraic method to construct non-degenerate (hyper-)graphs for various Turán type problems. The asymptotics for $ex(n, K^{(r)}_{s_1,s_2,\cdots,s_r})$ is also proved by Verstraëte independently with a different approach.

preprint2016arXiv

On the boundary of the region defined by homomorphism densities

The Kruskal-Katona theorem together with a theorem of Razborov determine the closure of the set of points defined by the homomorphism density of the edge and the triangle in finite graphs. The boundary of this region is a countable union of algebraic curves, and in particular, it is almost everywhere differentiable. One can more generally consider the region defined by the homomorphism densities of a list of given graphs, and ask whether the boundary is as well-behaved as in the case of the triangle and the edge. Towards answering this question in the negative, we construct examples which show that the restrictions of the boundary to certain hyperplanes can have nowhere differentiable parts.

preprint2007arXiv

Computing parametric rational generating functions with a primal Barvinok algorithm

Computations with Barvinok's short rational generating functions are traditionally being performed in the dual space, to avoid the combinatorial complexity of inclusion--exclusion formulas for the intersecting proper faces of cones. We prove that, on the level of indicator functions of polyhedra, there is no need for using inclusion--exclusion formulas to account for boundary effects: All linear identities in the space of indicator functions can be purely expressed using half-open variants of the full-dimensional polyhedra in the identity. This gives rise to a practically efficient, parametric Barvinok algorithm in the primal space.

preprint2016arXiv

Lp expander Complexes

We discuss two combinatorical ways of generalizing the definition of expander graphs and Ramanujan graphs, to quotients of buildings of higher dimension. The two possible definitions are equivalent for affine buildings, giving the notion of an Lp-expander complex. We calculate explicit spectral gaps on many combinatorical operators, on any Lp-expander complex. We associate with any complex a natural "zeta function", generalizing the Ihara-Hashimoto zeta function of a finite graph. We generalize a well known theorem of Hashimoto, showing that a complex is Ramanujan if and only if the zeta function satisfies the Riemann hypothesis.

preprint2017arXiv

Facial structures of lattice path matroid polytopes

A lattice path matroid is a transversal matroid corresponding to a pair of lattice paths on the plane. A matroid base polytope is the polytope whose vertices are the incidence vectors of the bases of the given matroid. In this paper, we study facial structures of matroid base polytopes corresponding to lattice path matroids.

preprint2017arXiv

A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo p

Let $K=\{k_1,k_2,\ldots,k_r\}$ and $L=\{l_1,l_2,\ldots,l_s\}$ be disjoint subsets of $\{0,1,\ldots,p-1\}$ , where $p$ is a prime and $A=\{A_1,A_2,\ldots,A_m\}$ be a family of subsets of $[n]$ such that $|A_i|\pmod{p}\in K$ for all $A_i\in A$ and $|A_i\cap A_j|\pmod{p}\in L$ for $i\ne j$ . In 1991, Alon, Babai and Suzuki conjectured that if $n\geq s+\max_{1\leq i\leq r} k_i$ , then $|A|\leq {n\choose s}+{n\choose s-1}+\cdots+{n\choose s-r+1}$ . In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition $n\geq 2s-r$ . In 2015, Hwang and Kim verified the conjecture of Alon, Babai and Suzuki. In this paper, we will prove that if $n\geq 2s-2r+1$ or $n\geq s+\max_{1\leq i\leq r}k_i$ , then $|A|\leq{n-1\choose s}+{n-1\choose s-1}+\cdots+{n-1\choose s-2r+1}.$ This result strengthens the upper bound of Alon, Babai and Suzuki's conjecture when $n\geq 2s-2$ .