Source author record

Matthias Beck

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT math.AC Hardware Architecture math.MG

Catalog footprint

Research overview

36works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Lonely Runner Polyhedra

We study the \emph{Lonely Runner Conjecture}, conceived by Jörg M.~Wills in the 1960's: Given positive integers $n_1, n_2, \dots, n_k$ , there exists a positive real number $t$ such that for all $1 \le j \le k$ the distance of $t \, n_j$ to the nearest integer is at least $\frac{ 1 }{ k+1 }$ . Continuing a view-obstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral \emph{ansatz} to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture.

preprint2015arXiv

Partitions with fixed differences between largest and smallest parts

We study the number $p(n,t)$ of partitions of $n$ with difference $t$ between largest and smallest parts. Our main result is an explicit formula for the generating function $P_t(q) := \sum_{n \ge 1} p(n,t) \, q^n$ . Somewhat surprisingly, $P_t(q)$ is a rational function for $t>1$ ; equivalently, $p(n,t)$ is a quasipolynomial in $n$ for fixed $t>1$ . Our result generalizes to partitions with an arbitrary number of specified distances.

preprint2015arXiv

Positivity theorems for solid-angle polynomials

For a lattice polytope P, define A_P(t) as the sum of the solid angles of all the integer points in the dilate tP. Ehrhart and Macdonald proved that A_P(t) is a polynomial in the positive integer variable t. We study the numerator polynomial of the solid-angle series sum_{t >= 0} A_P(t) z^t. In particular, we examine nonnegativity of its coefficients, monotonicity and unimodality questions, and study extremal behavior of the sum of solid angles at vertices of simplices. Some of our results extend to more general valuations.

preprint2014arXiv

A bivariate chromatic polynomial for signed graphs

We study Dohmen--Pönitz--Tittmann's bivariate chromatic polynomial $c_Γ(k,l)$ which counts all $(k+l)$ -colorings of a graph $Γ$ such that adjacent vertices get different colors if they are $\le k$ . Our first contribution is an extension of $c_Γ(k,l)$ to signed graphs, for which we obtain an inclusion--exclusion formula and several special evaluations giving rise, e.g., to polynomials that encode balanced subgraphs. Our second goal is to derive combinatorial reciprocity theorems for $c_Γ(k,l)$ and its signed-graph analogues, reminiscent of Stanley's reciprocity theorem linking chromatic polynomials to acyclic orientations.

preprint2014arXiv

Parking functions, Shi arrangements, and mixed graphs

The \emph{Shi arrangement} is the set of all hyperplanes in $\mathbb R^n$ of the form $x_j - x_k = 0$ or $1$ for $1 \le j < k \le n$ . Shi observed in 1986 that the number of regions (i.e., connected components of the complement) of this arrangement is $(n+1)^{n-1}$ . An unrelated combinatorial concept is that of a \emph{parking function}, i.e., a sequence $(x_1, x_2, ..., x_n)$ of positive integers that, when rearranged from smallest to largest, satisfies $x_k \le k$ . (There is an illustrative reason for the term \emph{parking function}.) It turns out that the number of parking functions of length $n$ also equals $(n+1)^{n-1}$ , a result due to Konheim and Weiss from 1966. A natural problem consists of finding a bijection between the $n$ -dimensional Shi arragnement and the parking functions of length $n$ . Stanley and Pak (1996) and Athanasiadis and Linusson 1999) gave such (quite different) bijections. We will shed new light on the former bijection by taking a scenic route through certain mixed graphs.

preprint2014arXiv

Variations on a Generating-Function Theme: Enumerating Compositions with Parts Avoiding an Arithmetic Sequence

A \Def{composition} of a positive integer $n$ is a $k$ -tuple $(ł_1, ł_2, \dots, ł_k) \in \Z_{> 0}^k$ such that $n = ł_1 + ł_2 + \dots + ł_k$ . Our goal is to enumerate those compositions whose parts $ł_1, ł_2, \dots, ł_k$ avoid a fixed arithmetic sequence. When this sequence is given by the even integers (i.e., all parts of the compositions must be odd), it is well known that the number of compositions is given by the Fibonacci sequence. A much more recent theorem says that when the parts are required to avoid all multiples of a given integer $k$ , the resulting compositions are counted by a sequence given by a Fibonacci-type recursion of depth $k$ . We extend this result to arbitrary arithmetic sequences. Our main tool is a lemma on generating functions which is no secret among experts but deserves to be more widely known.

preprint2014arXiv

Very ample and Koszul segmental fibrations

In the hierarchy of structural sophistication for lattice polytopes, normal polytopes mark a point of origin; very ample and Koszul polytopes occupy bottom and top spots in this hierarchy, respectively. In this paper we explore a simple construction for lattice polytopes with a twofold aim. On the one hand, we derive an explicit series of very ample 3-dimensional polytopes with arbitrarily large deviation from the normality property, measured via the highest discrepancy degree between the corresponding Hilbert functions and Hilbert polynomials. On the other hand, we describe a large class of Koszul polytopes of arbitrary dimensions, containing many smooth polytopes and extending the previously known class of Nakajima polytopes.

preprint2013arXiv

Bipartite graphs are weak antimagic

The \emph{Antimagic Graph Conjecture} asserts that every connected graph $G = (V, E)$ except $K_2$ admits an edge labeling such that each label $1, 2, ..., |E|$ is used exactly once and the sums of the labels on all edges incident with a given node are distinct. We study an associated counting function (replacing the upper bound on the possible labels by a variable) and prove that a variant of this counting function, when we do not require the labels to be distinct, is a polynomial if $G$ is bipartite. As a consequence, we show that every connected bipartite graph $G = (V, E)$ except $K_2$ admits a \emph{weakly} antimagic labeling, that is, each edge label is among $1, 2, ..., |E|$ (repetition allowed) and the sums of the labels on all edges incident with a given node are distinct. We also present a natural extension of these results to directed and bidirected graphs; this extension gives rise to a (bi-)directed version of the Antimagic Graph Conjecture, which might be of independent interest.

preprint2013arXiv

Enumerating Colorings, Tensions and Flows in Cell Complexes

We study quasipolynomials enumerating proper colorings, nowhere-zero tensions, and nowhere-zero flows in an arbitrary CW-complex $X$ , generalizing the chromatic, tension and flow polynomials of a graph. Our colorings, tensions and flows may be either modular (with values in $\mathbb{Z}/k\mathbb{Z}$ for some $k$ ) or integral (with values in $\{-k+1,\dots,k-1\}$ ). We obtain deletion-contraction recurrences and closed formulas for the chromatic, tension and flow quasipolynomials, assuming certain unimodularity conditions. We use geometric methods, specifically Ehrhart theory and inside-out polytopes, to obtain reciprocity theorems for all of the aforementioned quasipolynomials, giving combinatorial interpretations of their values at negative integers as well as formulas for the numbers of acyclic and totally cyclic orientations of $X$ .

preprint2013arXiv

Euler-Mahonian Statistics via Polyhedral Geometry

A variety of descent and major-index statistics have been defined for symmetric groups, hyperoctahedral groups, and their generalizations. Typically associated to pairs of such statistics is an Euler--Mahonian distribution, a bivariate generating function identity encoding these statistics. We use techniques from polyhedral geometry to establish new multivariate generalizations for many of the known Euler--Mahonian distributions. The original bivariate distributions are then straightforward specializations of these multivariate identities. A consequence of these new techniques are bijective proofs of the equivalence of the bivariate distributions for various pairs of statistics.

preprint2013arXiv

Lattice-point generating functions for free sums of convex sets

Let $\J$ and $\K$ be convex sets in $\R^{n}$ whose affine spans intersect at a single rational point in $\J \cap \K$, and let $\J \oplus \K = \conv(\J \cup \K)$. We give formulas for the generating function {equation*} σ_{\cone(\J \oplus \K)}(z_1,..., z_n, z_{n+1}) = \sum_{(m_1,..., m_n) \in t(\J \oplus \K) \cap \Z^{n}} z_1^{m_1}... z_n^{m_n} z_{n+1}^{t} {equation*} of lattice points in all integer dilates of $\J \oplus \K$ in terms of $σ_{\cone \J}$ and $σ_{\cone \K}$, under various conditions on $\J$ and $\K$. This work is motivated by (and recovers) a product formula of B.\ Braun for the Ehrhart series of $¶\oplus \Q$ in the case where $¶$ and $\Q$ are lattice polytopes containing the origin, one of which is reflexive. In particular, we find necessary and sufficient conditions for Braun's formula and its multivariate analogue.

preprint2013arXiv

Nowhere-Zero $\vec k$ -Flows on Graphs

We introduce and study a multivariate function that counts nowhere-zero flows on a graph G, in which each edge of G has an individual capacity. We prove that the associated counting function is a piecewise-defined polynomial in these capacities, which satisfy a combinatorial reciprocity law that incorporates totally cyclic orientations of G.

preprint2013arXiv

On Weak Chromatic Polynomials of Mixed Graphs

A \emph{mixed graph} is a graph with directed edges, called arcs, and undirected edges. A $k$ -coloring of the vertices is proper if colors from ${1,2,...,k}$ are assigned to each vertex such that $u$ and $v$ have different colors if $uv$ is an edge, and the color of $u$ is less than or equal to (resp. strictly less than) the color of $v$ if $uv$ is an arc. The weak (resp. strong) chromatic polynomial of a mixed graph counts the number of proper $k$ -colorings. Using order polynomials of partially ordered sets, we establish a reciprocity theorem for weak chromatic polynomials giving interpretations of evaluations at negative integers.

preprint2013arXiv

Rademacher-Carlitz Polynomials

We introduce and study the \emph{Rademacher-Carlitz polynomial} \[ \RC(u, v, s, t, a, b) := \sum_{k = \lceil s \rceil}^{\lceil s \rceil + b - 1} u^{\fl{\frac{ka + t}{b}}} v^k \] where $a, b \in \Z_{>0}$ , $s, t \in \R$ , and $u$ and $v$ are variables. These polynomials generalize and unify various Dedekind-like sums and polynomials; most naturally, one may view $\RC(u, v, s, t, a, b)$ as a polynomial analogue (in the sense of Carlitz) of the \emph{Dedekind-Rademacher sum} \[ \r_t(a,b) := \sum_{k=0}^{b-1}\left(\left(\frac{ka+t}{b} \right)\right) \left(\left(\frac{k}{b} \right)\right), \] which appears in various number-theoretic, combinatorial, geometric, and computational contexts. Our results come in three flavors: we prove a reciprocity theorem for Rademacher-Carlitz polynomials, we show how they are the only nontrivial ingredients of integer-point transforms $σ(x,y):=\sum_{(j,k) \in \mathcal{P}\cap \Z^2} x^j y^k$ of any rational polyhedron $\mathcal{P}$ , and we derive a novel reciprocity theorem for Dedekind-Rademacher sums, which follows naturally from our setup.

preprint2013arXiv

Relations for Bernoulli--Barnes Numbers and Barnes Zeta Functions

The \emph{Barnes $ζ$ -function} is \[ ζ_n (z, x; \a) := \sum_{\m \in \Z_{\ge 0}^n} \frac{1}{\left(x + m_1 a_1 + \dots + m_n a_n \right)^z} \] defined for $\Re(x) > 0$ and $\Re(z) > n$ and continued meromorphically to $\C$. Specialized at negative integers $-k$ , the Barnes $ζ$ -function gives \[ ζ_n (-k, x; \a) = \frac{(-1)^n k!}{(k+n)!} \, B_{k+n} (x; \a) \] where $B_k(x; \a)$ is a \emph{Bernoulli--Barnes polynomial}, which can be also defined through a generating function that has a slightly more general form than that for Bernoulli polynomials. Specializing $B_k(0; \a)$ gives the \emph{Bernoulli--Barnes numbers}. We exhibit relations among Barnes $ζ$ -functions, Bernoulli--Barnes numbers and polynomials, which generalize various identities of Agoh, Apostol, Dilcher, and Euler.

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 results to establish several conjectures by Pensyl and Savage regarding the symmetry of h*-vectors for s-lecture hall polytopes. We end with open questions and directions for further research.

preprint2013arXiv

The combinatorics of interval-vector polytopes

An \emph{interval vector} is a $(0,1)$ -vector in $\mathbb{R}^n$ for which all the 1's appear consecutively, and an \emph{interval-vector polytope} is the convex hull of a set of interval vectors in $\mathbb{R}^n$ . We study three particular classes of interval vector polytopes which exhibit interesting geometric-combinatorial structures; e.g., one class has volumes equal to the Catalan numbers, whereas another class has face numbers given by the Pascal 3-triangle.

preprint2012arXiv

Combinatorial Reciprocity Theorems

A common theme of enumerative combinatorics is formed by counting functions that are polynomials evaluated at positive integers. In this expository paper, we focus on four families of such counting functions connected to hyperplane arrangements, lattice points in polyhedra, proper colorings of graphs, and $P$ -partitions. We will see that in each instance we get interesting information out of a counting function when we evaluate it at a \emph{negative} integer (and so, a priori the counting function does not make sense at this number). Our goals are to convey some of the charm these "alternative" evaluations of counting functions exhibit, and to weave a unifying thread through various combinatorial reciprocity theorems by looking at them through the lens of geometry, which will include some scenic detours through other combinatorial concepts.

preprint2012arXiv

Counting Group Valued Graph Colorings

There are many variations on partition functions for graph homomorphisms or colorings. The case considered here is a counting or hard constraint problem in which the range or color graph carries a free and vertex transitive Abelian group action so that the colors are identified with the elements of this group. A Fourier transform is used to obtain an expansion for the numbers of colorings with terms indexed by isthmus free subgraphs of the domain. The terms are products of a polynomial in the edge density a of the color graph and the number of colorings of the indexing subgraph of the domain into the complementary color graph. The polynomial in a is independent of the color group and the term has order (1-a) to the r where r is the number of vertices minus the number of components in the indexing subgraph. Thus if (1-a) is small there is a main term indexed by the empty subgraph which is a polynomial in a and the first dependence on the coloring group occurs in the lowest order corrections which are indexed by the shortest cycles in the graph and are of order (1-a) to the g-1 where g is the length of these shortest cycles. The main theorem is stated as a reciprocity law. Examples are given in which the coloring groups are long cycles and products of short cycles and adjacent vertices are required to have distant rather than distinct colors. The chromatic polynomial of a graph corresponds to using any group and taking the allowed set to be the complement of the identity.

preprint2012arXiv

Flows on Simplicial Complexes

Given a graph $G$ , the number of nowhere-zero $\ZZ_q$-flows $ϕ_G(q)$ is known to be a polynomial in $q$ . We extend the definition of nowhere-zero $\ZZ_q$-flows to simplicial complexes $Δ$ of dimension greater than one, and prove the polynomiality of the corresponding function $ϕ_Δ(q)$ for certain $q$ and certain subclasses of simplicial complexes.

preprint2012arXiv

Lattice Point Generating Functions and Symmetric Cones

We show that a recent identity of Beck-Gessel-Lee-Savage on the generating function of symmetrically contrained compositions of integers generalizes naturally to a family of convex polyhedral cones that are invariant under the action of a finite reflection group. We obtain general expressions for the multivariate generating functions of such cones, and work out the specific cases of a symmetry group of type A (previously known) and types B and D (new). We obtain several applications of the special cases in type B, including identities involving permutation statistics and lecture hall partitions.

preprint2011arXiv

An Extreme Family of Generalized Frobenius Numbers

We study a generalization of the \emph{Frobenius problem}: given $k$ positive relatively prime integers, what is the largest integer $g_0$ that cannot be represented as a nonnegative integral linear combination of these parameters? More generally, what is the largest integer $g_s$ that has exactly $s$ such representations? We illustrate a family of parameters, based on a recent paper by Tripathi, whose generalized Frobenius numbers $g_0, \ g_1, \ g_2, ...$ exhibit unnatural jumps; namely, $g_0, \ g_1, \ g_k, \ g_{\binom{k+1}{k-1}}, \ g_{\binom{k+2}{k-1}}, ...$ form an arithmetic progression, and any integer larger than $g_{\binom{k+j}{k-1}}$ has at least $\binom{k+j+1}{k-}$ representations. Along the way, we introduce a variation of a generalized Frobenius number and prove some basic results about it.

preprint2011arXiv

Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs

A \emph{Golomb ruler} is a sequence of distinct integers (the \emph{markings} of the ruler) whose pairwise differences are distinct. Golomb rulers can be traced back to additive number theory in the 1930s and have attracted recent research activities on existence problems, such as the search for \emph{optimal} Golomb rulers (those of minimal length given a fixed number of markings). Our goal is to enumerate Golomb rulers in a systematic way: we study [g_m(t) := # {\x \in \Z^{m+1} : \, 0 = x_0 < x_1 < ... < x_{m-1} < x_m = t, \text{all} x_j - x_k \text{distinct}},] the number of Golomb rulers with $m+1$ markings and length $t$ . Our main result is that $g_m(t)$ is a quasipolynomial in $t$ which satisfies a combinatorial reciprocity theorem: $(-1)^{m-1} g_m(-t)$ equals the number of rulers $\x$ of length $t$ with $m+1$ markings, each counted with its \emph{Golomb multiplicity}, which measures how many combinatorially different Golomb rulers are in a small neighborhood of $\x$. Our reciprocity theorem can be interpreted in terms of certain mixed graphs associated to Golomb rulers; in this language, it is reminiscent of Stanley's reciprocity theorem for chromatic polynomials. Thus in the second part of the paper we develop an analogue of Stanley's theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations.

preprint2011arXiv

Mahonian Partition Identities Via Polyhedral Geometry

In a series of papers, George Andrews and various coauthors successfully revitalized seemingly forgotten, powerful machinery based on MacMahon's $Ω$ operator to systematically compute generating functions $\sum_{\la \in P} z_1^{\la_1}...z_n^{\la_n}$ for some set $P$ of integer partitions $\la = (\la_1,..., \la_n)$. Our goal is to geometrically prove and extend many of the Andrews et al theorems, by realizing a given family of partitions as the set of integer lattice points in a certain polyhedron.

preprint2011arXiv

Symmetrically Constrained Compositions

Given integers $a_1, a_2, ..., a_n$ , with $a_1 + a_2 + ... + a_n \geq 1$ , a symmetrically constrained composition $λ_1 + lambda_2 + ... + lambda_n = M$ of $M$ into $n$ nonnegative parts is one that satisfies each of the the $n!$ constraints ${\sum_{i=1}^n a_i λ_{π(i)} \geq 0 : π\in S_n}$ . We show how to compute the generating function of these compositions, combining methods from partition theory, permutation statistics, and lattice-point enumeration.

preprint2010arXiv

Bernoulli--Dedekind Sums

Let $p_1,p_2,\dots,p_n, a_1,a_2,\dots,a_n \in \N$ , $x_1,x_2,\dots,x_n \in \R$ , and denote the $k$ th periodized Bernoulli polynomial by $\B_k(x)$. We study expressions of the form \[ \sum_{h \bmod{a_k}} \ \prod_{\substack{i=1\\ i\not=k}}^{n} \ \B_{p_i}\left(a_i \frac{h+x_k}{a_k}-x_i\right). \] These \highlight{Bernoulli--Dedekind sums} generalize and unify various arithmetic sums introduced by Dedekind, Apostol, Carlitz, Rademacher, Sczech, Hall--Wilson--Zagier, and others. Generalized Dedekind sums appear in various areas such as analytic and algebraic number theory, topology, algebraic and combinatorial geometry, and algorithmic complexity. We exhibit a reciprocity theorem for the Bernoulli--Dedekind sums, which gives a unifying picture through a simple combinatorial proof.

preprint2010arXiv

Nowhere-Harmonic Colorings of Graphs

Proper vertex colorings of a graph are related to its boundary map, also called its signed vertex-edge incidence matrix. The vertex Laplacian of a graph, a natural extension of the boundary map, leads us to introduce nowhere-harmonic colorings and analogues of the chromatic polynomial and Stanley's theorem relating negative evaluations of the chromatic polynomial to acyclic orientations. Further, we discuss some examples demonstrating that nowhere-harmonic colorings are more complicated from an enumerative perspective than proper colorings.

preprint2010arXiv

Six Little Squares and How Their Numbers Grow

We find the numbers of $3 \times 3$ magic, semimagic, and magilatin squares, as functions either of the magic sum or of an upper bound on the entries in the square. Our results on magic and semimagic squares differ from previous ones in that we require the entries in the square to be distinct from each other and we derive our results not by \emph{ad hoc} reasoning but from the general geometric and algebraic method of our paper "An enumerative geometry for magic and magilatin labellings". Here we illustrate that method with a detailed analysis of $3\times3$ squares.

preprint2009arXiv

Enumeration of $4 \times 4$ Magic Squares

A \emph{magic square} is an $n \times n$ array of distinct positive integers whose sum along any row, column, or main diagonal is the same number. We compute the number of such squares for $n=4$ , as a function of either the magic sum or an upper bound on the entries. The previous record for both functions was the $n=3$ case. Our methods are based on inside-out polytopes, i.e., the combination of hyperplane arrangements and Ehrhart's theory of lattice-point enumeration.

preprint2008arXiv

Finite Trigonometric Character Sums Via Discrete Fourier Analysis

We prove several old and new theorems about finite sums involving characters and trigonometric functions. These sums can be traced back to theta function identities from Ramanujan's notebooks and were systematically first studied by Berndt and Zaharescu; their proofs involved complex contour integration. We show how to prove most of Berndt-Zaharescu's and some new identities by elementary methods of discrete Fourier Analysis.

preprint2008arXiv

On the Log-Concavity of Hilbert Series of Veronese Subrings and Ehrhart Series

For every positive integer $n$ , consider the linear operator $\U_{n}$ on polynomials of degree at most $d$ with integer coefficients defined as follows: if we write $\frac{h(t)}{(1 - t)^{d + 1}} = \sum_{m \geq 0} g(m) t^{m}$ , for some polynomial $g(m)$ with rational coefficients, then $\frac{\U_{n}h(t)}{(1- t)^{d + 1}} = \sum_{m \geq 0} g(nm) t^{m}$. We show that there exists a positive integer $n_{d}$ , depending only on $d$ , such that if $h(t)$ is a polynomial of degree at most $d$ with nonnegative integer coefficients and $h(0) \geq 1$ , then for $n \geq n_{d}$ , $\U_{n}h(t)$ has simple, real, strictly negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart $δ$ -polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen--MacCauley graded rings.

preprint2008arXiv

Root polytopes and growth series of root lattices

The convex hull of the roots of a classical root lattice is called a root polytope. We determine explicit unimodular triangulations of the boundaries of the root polytopes associated to the root lattices A_n, C_n, and D_n, and compute their f-and h-vectors. This leads us to recover formulae for the growth series of these root lattices, which were first conjectured by Conway-Mallows-Sloane and Baake-Grimm and proved by Conway-Sloane and Bacher-de la Harpe-Venkov.

preprint2008arXiv

Theorems of Brion, Lawrence, and Varchenko on rational generating functions for cones

We discuss and give elementary proofs of results of Brion and of Lawrence-Varchenko on the lattice-point enumerator generating functions for polytopes and cones. This largely expository note contains a new proof of Brion's Formula using irrational decompositions, and a generalization of the Lawrence-Varchenko formula.

preprint2007arXiv

Logic Design for On-Chip Test Clock Generation - Implementation Details and Impact on Delay Test Quality

This paper addresses delay test for SOC devices with high frequency clock domains. A logic design for on-chip high-speed clock generation, implemented to avoid expensive test equipment, is described in detail. Techniques for on-chip clock generation, meant to reduce test vector count and to increase test quality, are discussed. ATPG results for the proposed techniques are given.

preprint2005arXiv

Inside-Out Polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.

preprint2003arXiv

A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains

Meshalkin's theorem states that a class of ordered p-partitions of an n-set has at most $\max \binom{n}{a_1,...,a_p}$ members if for each k the k'th parts form an antichain. We give a new proof of this and the corresponding LYM inequality due to Hochberg and Hirsch, which is simpler and more general than previous proofs. It extends to a common generalization of Meshalkin's theorem and Erdos's theorem about r-chain-free set families.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Matthias Beck

Research overview

Is this your work?

36 publications

Lonely Runner Polyhedra

Partitions with fixed differences between largest and smallest parts

Positivity theorems for solid-angle polynomials

A bivariate chromatic polynomial for signed graphs

Parking functions, Shi arrangements, and mixed graphs

Variations on a Generating-Function Theme: Enumerating Compositions with Parts Avoiding an Arithmetic Sequence

Very ample and Koszul segmental fibrations

Bipartite graphs are weak antimagic

Enumerating Colorings, Tensions and Flows in Cell Complexes

Euler-Mahonian Statistics via Polyhedral Geometry

Lattice-point generating functions for free sums of convex sets

Nowhere-Zero k⃗\vec kk-Flows on Graphs

On Weak Chromatic Polynomials of Mixed Graphs

Rademacher-Carlitz Polynomials

Relations for Bernoulli--Barnes Numbers and Barnes Zeta Functions

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

The combinatorics of interval-vector polytopes

Combinatorial Reciprocity Theorems

Counting Group Valued Graph Colorings

Flows on Simplicial Complexes

Lattice Point Generating Functions and Symmetric Cones

An Extreme Family of Generalized Frobenius Numbers

Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs

Mahonian Partition Identities Via Polyhedral Geometry

Symmetrically Constrained Compositions

Bernoulli--Dedekind Sums

Nowhere-Harmonic Colorings of Graphs

Six Little Squares and How Their Numbers Grow

Enumeration of 4×44 \times 44×4 Magic Squares

Finite Trigonometric Character Sums Via Discrete Fourier Analysis

On the Log-Concavity of Hilbert Series of Veronese Subrings and Ehrhart Series

Root polytopes and growth series of root lattices

Theorems of Brion, Lawrence, and Varchenko on rational generating functions for cones

Logic Design for On-Chip Test Clock Generation - Implementation Details and Impact on Delay Test Quality

Inside-Out Polytopes

A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains

See the researcher in context

Building this map preview

Nowhere-Zero $\vec k$ -Flows on Graphs

Enumeration of $4 \times 4$ Magic Squares