BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Matthias Beck

Matthias Beck contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COmath.NTHardware Architecturemath.AC

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
21works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

21 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;s reciprocity theorem for chromatic polynomials. Thus in the second part of the paper we develop an analogue of Stanley&#39;s theorem to mixed graphs, which connects their chromatic polynomials to acyclic orientations.

0 citations0 reviewsNo code linkedOpen access
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&#39;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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;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.

0 citations0 reviewsNo code linkedOpen access
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&#39;s theory of lattice-point enumeration.

0 citations0 reviewsNo code linkedOpen access
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&#39;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&#39;s and some new identities by elementary methods of discrete Fourier Analysis.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;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.

0 citations0 reviewsNo code linkedOpen access