Let be a finite Weyl group and the corresponding affine Weyl group. A random element of can be obtained as a reduced random walk on the alcoves of . By a theorem of Lam (Ann. Probab. 2015), such a walk almost surely approaches one of many directions. We compute these directions when is , and and the random walk is weighted by Kac and dual Kac labels. This settles Lam's questions for types and in the affirmative and for type in the negative. The main tool is a combinatorial two row model for a totally asymmetric simple exclusion process called the -TASEP, with four parameters. By specializing the parameters in different ways, we obtain TASEPs for each of the Weyl groups mentioned above. Computing certain correlations in these TASEPs gives the desired limiting directions.

Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.

Random tilings of geometrical shapes with dominos or lozenges have been a rich source of universal statistical distributions. This paper deals with domino tilings of checker board rectangular shapes such that the top two and bottom two adjacent squares have the same orientation and the two most left and two most right ones as well. It forces these so-called "skew-Aztec rectangles" to have cuts on either side. For large sizes of the domain and upon an appropriate scaling of the location of the cuts, one finds split tacnodes between liquid regions with two distinct adjacent frozen phases descending into the tacnode. Zooming about such split tacnodes, filaments appear between the liquid patches evolving in a bricklike sea of dimers of another type. This work shows that the random fluctuations in a neighborhood of the split tacnode are governed asymptotically by the discrete tacnode kernel, providing strong evidence that this kernel is a universal discrete-continuous limiting kernel occurring naturally whenever we have doubly interlacing patterns. The analysis involves the inversion of a singular Toeplitz matrix which leads to considerable difficulties.

A logical zonotope, which is a new set representation for binary vectors, is introduced in this paper. A logical zonotope is constructed by XORing a binary vector with a combination of other binary vectors called generators. Such a zonotope can represent up to 2γ binary vectors using only γ generators. It is shown that logical operations over sets of binary vectors can be performed on the zonotopes' generators and, thus, significantly reduce the computational complexity of various logical operations (e.g., XOR, NAND, AND, OR, and semi-tensor products). Similar to traditional zonotopes' role in the formal verification of dynamical systems over real vector spaces, logical zonotopes can efficiently analyze discrete dynamical systems defined over binary vector spaces. We illustrate the approach and its ability to reduce the computational complexity in two use cases: (1) encryption key discovery of a linear feedback shift register and (2) safety verification of a road traffic intersection protocol.

In this paper, we introduce a set representation called polynomial logical zonotopes for performing exact and computationally efficient reachability analysis on logical systems. We prove that through this polynomial-like construction, we are able to perform all of the fundamental logical operations (XOR, NOT, XNOR, AND, NAND, OR, NOR) between sets of points exactly in a reduced space, i.e., generator space with reduced complexity. Polynomial logical zonotopes are a generalization of logical zonotopes, which are able to represent up to 2γ binary vectors using only γ generators. Due to their construction, logical zonotopes are only able to support exact computations of some logical operations (XOR, NOT, XNOR), while other operations (AND, NAND, OR, NOR) result in over-approximations in the generator space. In order to perform all fundamental logical operations exactly, we formulate a generalization of logical zonotopes that is constructed by dependent generators and exponent matrices. While we are able to perform all of the logical operations exactly, this comes with a slight increase in computational complexity compared to logical zonotopes. To illustrate and showcase the computational benefits of polynomial logical zonotopes, we present the results of performing reachability analysis on two use cases: (1) safety verification of an intersection crossing protocol and (2) reachability analysis on a high-dimensional Boolean function. Moreover, to highlight the extensibility of logical zonotopes, we include an additional use case where we perform a computationally tractable exhaustive search for the key of a linear feedback shift register.

We prove several new instances of the cyclic sieving phenomenon (CSP) on Catalan objects of type A and type B. Moreover, we refine many of the known instances of the CSP on Catalan objects. For example, we consider triangulations refined by the number of “ears”, non-crossing matchings with a fixed number of short edges, and non-crossing configurations with a fixed number of loops and edges.

We prove several new instances of the cyclic sieving phenomenon (CSP) on Catalan objects of type A and type B . Moreover, we refine many of the known instances of the CSP on Catalan objects. For example, we consider triangulations refined by the number of "ears", non-crossing matchings with a fixed number of short edges, and non-crossing configurations with a fixed number of loops and edges.

We use a Dyck path model for unit-interval graphs to study the chromatic quasisymmetric functions introduced by Shareshian and Wachs, as well as unicellular LLT polynomials, revealing some parallel structure and phenomena regarding their e-positivity. The Dyck path model is also extended to circular arc digraphs to obtain larger families of polynomials, giving a new extension of LLT polynomials. Carrying over a lot of the noncircular combinatorics, we prove several statements regarding the e-coefficients of chromatic quasisymmetric functions and LLT polynomials, including a natural combinatorial interpretation for the e-coefficients for the line graph and the cycle graph for both families. We believe that certain e-positivity conjectures hold in all these families above. Furthermore, beyond the chromatic analogy, we study vertical-strip LLT polynomials, which are modified Hall-Littlewood polynomials. 

Using the combinatorics of a-unimodal sets, we establish two new results in the theory of quasisymmetric functions. First, we obtain the expansion of the fundamental basis into quasisymmetric power sums. Secondly, we prove that generating functions of reverse P-partitions expand positively into quasisymmetric power sums. Consequently any nonnegative linear combination of such functions is p-positive whenever it is symmetric. We apply this method to derive positivity results for chromatic quasisymmetric functions and unicellular LLT polynomials. 

This thesis consists of five papers in algebraic and enumerative combinatorics. The objects at the heart of the thesis are combinatorial polynomials in one or more variables. We study their zeros, coefficients and special evaluations. Hyperbolic polynomials may be viewed as multivariate generalizations of real-rooted polynomials in one variable. To each hyperbolic polynomial one may associate a convex cone from which a matroid can be derived - a so called hyperbolic matroid. In Paper A we prove the existence of an infinite family of non-representable hyperbolic matroids parametrized by hypergraphs. We further use special members of our family to investigate consequences to a central conjecture around hyperbolic polynomials, namely the generalized Lax conjecture. Along the way we strengthen and generalize several symmetric function inequalities in the literature, such as the Laguerre-Tur\'an inequality and an inequality due to Jensen. In Paper B we affirm the generalized Lax conjecture for two related classes of combinatorial polynomials: multivariate matching polynomials over arbitrary graphs and multivariate independence polynomials over simplicial graphs. In Paper C we prove that the multivariate $d$-matching polynomial is hyperbolic for arbitrary multigraphs, in particular answering a question by Hall, Puder and Sawin. We also provide a hypergraphic generalization of a classical theorem by Heilmann and Lieb regarding the real-rootedness of the matching polynomial of a graph. In Paper D we establish a number of equidistributions between Mahonian statistics which are given by conic combinations of vincular pattern functions of length at most three, over permutations avoiding a single classical pattern of length three. In Paper E we find necessary and sufficient conditions for a candidate polynomial to be complemented to a cyclic sieving phenomenon (without regards to combinatorial context). We further take a geometric perspective on the phenomenon by associating a convex rational polyhedral cone which has integer lattice points in correspondence with cyclic sieving phenomena. We find the half-space description of this cone and investigate its properties.

The generalized Lax conjecture asserts that each hyperbolicity cone is a linear slice of the cone of positive semidefinite matrices. We prove the conjecture for a multivariate generalization of the matching polynomial. This is further extended (albeit in a weaker sense) to a multivariate version of the independence polynomial for simplicial graphs. As an application we give a new proof of the conjecture for elementary symmetric polynomials (originally due to Brändén). Finally we consider a hyperbolic convolution of determinant polynomials generalizing an identity of Godsil and Gutman.

The first part of this note concerns stable averages of multivariate matching polynomials. In proving the existence of infinite families of bipartite Ramanujan d-coverings, Hall, Puder and Sawin introduced the d-matching polynomial of a graph G, defined as the uniform average of matching polynomials over the set of d-sheeted covering graphs of G. We prove that a natural multivariate version of the d-matching polynomial is stable, consequently giving a short direct proof of the real-rootedness of the d-matching polynomial. Our theorem also includes graphs with loops, thus answering a question of said authors. Furthermore we define a weaker notion of matchings for hypergraphs and prove that a family of natural polynomials associated to such matchings are stable. In particular this provides a hypergraphic generalization of the classical Heilmann-Lieb theorem.

We study cyclic sieving phenomena (CSP) on combinatorial objects from an abstract point of view by considering a rational polyhedral cone determined by the linear equations that define such phenomena. Each lattice point in the cone corresponds to a non-negative integer matrix which jointly records the statistic and cyclic order distribution associated with the set of objects realizing the CSP. In particular we consider a universal subcone onto which every CSP matrix linearly projects such that the projection realizes a CSP with the same cyclic orbit structure, but via a universal statistic that has even distribution on the orbits.

Reiner et.al. showed that every cyclic action gives rise to a unique polynomial (mod q^n-1) complementing the action to a CSP. We give a necessary and sufficient criterion for the converse to hold. This characterization allows one to determine if a combinatorial set with a statistic gives rise (in principle) to a CSP without having a combinatorial realization of the cyclic action. We apply the criterion to conjecture a new CSP involving stretched Schur polynomials and prove our conjecture for certain rectangular tableaux. Finally we study some geometric properties of the CSP cone. We explicitly determine its half-space description and in the prime order case we determine its extreme rays.

Using a unified formulation of N = 1, 2, 4, 8, super Yang-Mills theories in D = 3 spacetime dimensions with fields valued respectively in R, C, H, O, it was shown that tensoring left and right multiplets yields a Freudenthal magic square of D = 3 supergravities. When tied in with the more familiar R, C, H, O description of super Yang-Mills in D = 3, 4, 6, 10 this results in a magic pyramid of supergravities: the known 4x4 magic square at the base in D = 3, a 3x3 square in D = 4, a 2x2 square in D = 6 and Type II supergravity at the apex in D = 10.

Equivariant Ehrhart theory enumerates the lattice points in a polytope with respect to a group action. Answering a question of Stapledon, we describe the equivariant Ehrhart theory of the permutahedron, and we prove his Effectiveness Conjecture in this special case.

We prove that for k << (4)root n regular resolution requires length n(Omega(k)) to establish that an Erdos Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n(Omega(k)) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O∗(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O∗(2(0.5-δ)n)-time algorithm, with some constant δ &gt; 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ &gt; 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree (n= log n) in the Polynomial Calculus (over fields of characteristic 6= 2) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovasz-Schrijver proof system requires nrounds to refute these formulas for some > 0. The results are obtained by a worst-case to averagecase reduction of these formulas relying on a topological embedding theorem which may be of independent interest.

We consider generalizations of juggling Markov chains introduced by Ayyer, Bouttier, Corteel and Nunzi. We first study multispecies generalizations of all the finite models therein, namely the MJMC, the add-drop and the annihilation models. We then consider the case of several jugglers exchanging balls. In all cases, we give explicit product formulas for the stationary probability and closed-form expressions for the normalization factor if known.

The long code is a central tool in hardness of approximation especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results including the following: (1) For any ε &gt; 0, we show the existence of an n-vertex graph G where every set of o(n) vertices has expansion 1-ε but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563-572] who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo K into instances with alphabet k with a blowup of kpolylog(K) , improving over the previously known gadget with blowup of kω(K). (3) An n-variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the semidefinite programming version of the Sherali-Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.

The Ehrhart polynomialehr P(n) of a lattice polytope P gives the number of integer lattice points in the n-th dilate of P for all integers n≥ 0. The degree of P is defined as the degree of its h∗-polynomial, a particular transformation of the Ehrhart polynomial with many useful properties which serves as an important tool for classification questions in Ehrhart theory. A zonotope is the Minkowski (pointwise) sum of line segments. We classify all Ehrhart polynomials of lattice zonotopes of degree 2 thereby complementing results of Scott (Bull Aust Math Soc 15(3), 395–399, 1976), Treutlein (J Combin Theory Ser A 117(3), 354–360, 2010), and Henk and Tagami (Eur J Combin 30(1), 70–83, 2009). Our proof is constructive: by considering solid-angles and the lattice width, we provide a characterization of all 3-dimensional zonotopes of degree 2.

Random tilings of the two-periodic Aztec diamond contain three macroscopic regions: frozen, where the tilings are deterministic; rough, where the correlations between dominoes decay polynomially; smooth, where the correlations between dominoes decay exponentially. In a previous paper, the authors found that a certain averaging of height function differences at the rough-smooth interface converged to the extended Airy kernel point process. In this paper, we augment the local geometrical picture at this interface by introducing well-defined lattice paths which are closely related to the level lines of the height function. We show, after suitable centering and rescaling, that a point process from these paths converge to the extended Airy kernel point process provided that the natural parameter associated to the two-periodic Aztec diamond is small enough.

Factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely defined by its factor graph and the list of predicates. We show inapproximability of Max-3-LIN over non-abelian groups (both in the perfect completeness case and in the imperfect completeness case), with the same inapproximability factor as in the general case, even when the factor graph is fixed. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x · y · z = g, where x, y, z are the variables and g is a group element. We use representation theory and Fourier analysis over non-abelian groups to analyze the reductions. 

The factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely determined by its factor graph and the list of predicates. We show optimal inapproximability of Max-3-LIN over non-Abelian groups (both in the perfect completeness case and in the imperfect completeness case), even when the factor graph is fixed. Previous reductions which proved similar optimal inapproximability results produced factor graphs that were dependent on the input instance. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x· y· z= g, where x, y, z are the variables and g is a group element. We use representation theory and Fourier analysis over non-Abelian groups to analyze the reductions.

We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + ϵ)-approximate maximum matching in general graphs with O(poly(log n, 1/ϵ)) update time. (2) An algorithm that maintains an αk approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1 ≤ αk ≤ 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.

HTML clipboard Statistical physics seeks to explain macroscopic properties of matter in terms of microscopic interactions. Of particular interest is the phenomenon of phase transition: the sudden changes in macroscopic properties as external conditions are varied. Two models in particular are of great interest to mathematicians, namely the Ising model of a magnet and the percolation model of a porous solid. These models in turn are part of the unifying framework of the random-cluster representation, a model for random graphs which was first studied by Fortuin and Kasteleyn in the 1970’s. The random-cluster representation has proved extremely useful in proving important facts about the Ising model and similar models.

In this work we study the corresponding graphical framework for two related models. The first model is the transverse field quantum Ising model, an extension of the original Ising model which was introduced by Lieb, Schultz and Mattis in the 1960’s. The second model is the space–time percolation process, which is closely related to the contact model for the spread of disease. In Chapter 2 we define the appropriate space–time random-cluster model and explore a range of useful probabilistic techniques for studying it. The space– time Potts model emerges as a natural generalization of the quantum Ising model. The basic properties of the phase transitions in these models are treated in this chapter, such as the fact that there is at most one unbounded fk-cluster, and the resulting lower bound on the critical value in .

In Chapter 3 we develop an alternative graphical representation of the quantum Ising model, called the random-parity representation. This representation is based on the random-current representation of the classical Ising model, and allows us to study in much greater detail the phase transition and critical behaviour. A major aim of this chapter is to prove sharpness of the phase transition in the quantum Ising model—a central issue in the theory— and to establish bounds on some critical exponents. We address these issues by using the random-parity representation to establish certain differential inequalities, integration of which gives the results.

In Chapter 4 we explore some consequences and possible extensions of the results established in Chapters 2 and 3. For example, we determine the critical point for the quantum Ising model in and in ‘star-like’ geometries.

This paper is concerned with lower bounds for the connectivity of graphs (one-dimensional skeleta) of triangulations of compact manifolds. We introduce a structural invariant b_M for simplicial d-manifolds M taking values in the range 0 <= b_M <= d-1. The main result is that b_M influences connectivity in the following way: The graph of a d-dimensional simplicial compact manifold M is (2d - b_M)-connected. The parameter b_M has the property that b_M = 0 if the complex M is flag. Hence, our result interpolates between Barnette's theorem (1982) that all d-manifold graphs are (d+1)-connected and Athanasiadis' theorem (2011) that flag d-manifold graphs are 2d-connected. The definition of b_M involves the concept of banner triangulations of manifolds, a generalization of flag triangulations.

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified"algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õk(n+rr) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õk hides poly(k, log(n)). This implies the following consequences. (i) An improvement over the Õk(nr) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An Õk(|E|+|V||V|)-time algorithm for the k-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õk(|V||E|) bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility. Matroid intersection. We show a matroid intersection algorithm with Õ(nr) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP'85], graphic matroid intersection [Gabow-Xu FOCS'89], simple job scheduling matroid intersection [Xu-Gabow ISAAC'94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a "unified"algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. Lower bounds. We show simple super-linear (ω(nlogn)) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log2(3)n-o(n) bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19].

We study the geometry and complexity of Voronoi cells of lattices with respect to arbitrary norms. On the positive side, we show for strictly convex and smooth norms that the geometry of Voronoi cells of lattices in any dimension is similar to the Euclidean case, i.e., the Voronoi cells are defined by the Voronoi-relevant vectors and the facets of a Voronoi cell are in one-to-one correspondence with these vectors. On the negative side, we show that Voronoi cells are combinatorially much more complicated for arbitrary strictly convex and smooth norms than in the Euclidean case. In particular, we construct a family of three-dimensional lattices whose number of Voronoi-relevant vectors with respect to the `3-norm is unbounded. Our result indicates that the single exponential time algorithm of Micciancio and Voulgaris for solving the shortest vector problem (SVP) and the closest vector problem (CVP) in the Euclidean norm cannot be extended to achieve deterministic single exponential time algorithms for lattice problems with respect to arbitrary `p-norms. In fact, the algorithm of Micciancio and Voulgaris and its run time analysis crucially depend on the fact that, for the Euclidean norm, the number of Voronoi-relevant vectors is single exponential in the lattice dimension. Copyright 

A long-standing open conjecture in combinatorics asserts that a Gorenstein lattice polytope with the integer decomposition property (IDP) has a unimodal (Ehrhart) h*-polynomial. This conjecture can be viewed as a strengthening of a previously disproved conjecture which stated that any Gorenstein lattice polytope has a unimodal h*-polynomial. The first counterexamples to unimodality for Gorenstein lattice polytopes were given in even dimensions greater than five by Mustata and Payne, and this was extended to all dimensions greater than five by Payne. While there exist numerous examples in support of the conjecture that IDP reflexives are h*-unimodal, its validity has not yet been considered for families of reflexive lattice simplices that closely generalize Payne's counterexamples. The main purpose of this work is to prove that the former conjecture does indeed hold for a natural generalization of Payne's examples. The second purpose of this work is to extend this investigation to a broader class of lattice simplices, for which we present new results and open problems. 

Eulerian polynomials are fundamental in combinatorics and algebra. In this paper we study the linear transformation A : R[t] -> R[t] defined by A(t(n)) = A(n)(t), where A(n)(t) denotes the n-th Eulerian polynomial. We give combinatorial, topological and Ehrhart theoretic interpretations of the operator A, and investigate questions of unimodality and real-rootedness. In particular, we disprove a conjecture by Brenti (1989) concerning the preservation of real zeros, and generalize and strengthen recent results of Haglund and Zhang (2019) on binomial Eulerian polynomials.

In algebraic, topological, and geometric combinatorics, inequalities among the coefficients of combinatorial polynomials are frequently studied. Recently, a notion called the alternatingly increasing property, which is stronger than unimodality, was introduced. In this paper, we relate the alternatingly increasing property to real-rootedness of the symmetric decomposition of a polynomial to develop a systematic approach for proving the alternatingly increasing property for several classes of polynomials. We apply our results to strengthen and generalize real-rootedness, unimodality, and alternatingly increasing results pertaining to colored Eulerian and derangement polynomials, Ehrhart h*-polynomials for lattice zonotopes, h-polynomials of barycentric subdivisions of doubly Cohen-Macaulay level simplicial complexes, and certain local h-polynomials for subdivisions of simplices. In particular, we prove two conjectures of Athanasiadis.

The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: for every α ∈ (0, 1] and every non-negative integer d, there is βcol = βcol(α, d) ∈ (0, 1] with the following property. Let F1,..., Fd+1 be finite nonempty families of convex sets in ℝd of sizes n1,..., nd+1, respectively. If at least αn1n2 · · · nd+1 of the colorful (d + 1)-tuples have a nonempty intersection, then there is i ∈ [d + 1] such that Fi contains a subfamily of size at least βcolni with a nonempty intersection. (A colorful (d + 1)-tuple is a (d + 1)-tuple (F1,..., Fd+1) such that Fi belongs to Fi for every i.) The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with βcol = α/(d + 1). In 2017 Kim proved the theorem with better function βcol, which in particular tends to 1 when α tends to 1. Kim also conjectured what is the optimal bound for βcol(α, d) and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984. We verify Kim's conjecture by extending Kalai's approach to the colorful scenario. Moreover, we obtain optimal bounds also in a more general setting when we allow several sets of the same color. 

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e.g., this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (Gap-ETH) [4], [5], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k(o(1))-FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log(1/4+epsilon) (OPT) approximation for DomSet for any constant epsilon > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

Model abstraction for finite state automata is beneficial to reduce the complexity of discrete-event systems (DES), enhances the readability and facilitates the control synthesis and verification of DES. Supremal quasi-congruence computation is an effective way for reducing the state space of DES. Effective algorithms on the supremal quasi-congruence relation have been developed based on the graph theory. This paper proposes a new approach to translate the supremal quasi-congruence computation into a satisfiability (SAT) problem that determines whether there exists an assignment for Boolean variables in the state-to-coset allocation matrix. If the result is satisfied, then the supremal quasi-congruence relation exists and the minimum equivalence classes is obtained. Otherwise, it indicates that there is no such supremal quasi-congruence relation, and a new set of observable events needs to be modified or reselected for the original system model. The satisfiability problem on the computation of supremal quasi-congruence relation is solved by different methods, which are respectively implemented by mixed integer linear programming (MILP) in MATLAB, binary linear programming (BLP) in CPLEX, and a SAT-based solver (Z3Py). Compared with the MILP and BLP methods, the SAT method is more efficient and stable. The computation time of model abstraction for large-scale systems by Z3Py solver is significantly reduced.

We study-y-vectors associated with h\ast-vectors of symmetric edge polytopes both from a deterministic and a probabilistic point of view. On the deterministic side, we prove nonnegativity of-y2 for any graph and completely characterize the case when-y2 = 0. The latter also confirms a conjecture by Lutz and Nevo in the realm of symmetric edge polytopes. On the probabilistic side, we show that the-y-vectors of symmetric edge polytopes of most ErdoH \s--Re'\nyi random graphs are asymptotically almost surely nonnegative up to any fixed entry. This proves that Gal's conjecture holds asymptotically almost surely for arbitrary unimodular triangulations in this setting.

We associate with every pure flag simplicial complex Δ a standard graded Gorenstein F-RΔ whose homological features are largely dictated by the combinatorics and topology of Δ . As our main result, we prove that the residue field F has a k-step linear RΔ-resolution if and only if Δ satisfies Serre's condition (S k) over F and that RΔ is Koszul if and only if Δ is Cohen-Macaulay over F. Moreover, we show that RΔ has a quadratic Gröbner basis if and only if Δ is shellable. We give two applications: first, we construct quadratic Gorenstein F-s that are Koszul if and only if the characteristic of F is not in any prescribed set of primes. Finally, we prove that whenever RΔ is Koszul the coefficients of its γ-vector alternate in sign, settling in the negative an ic generalization of a conjecture by Charney and Davis.

Coordination control of multiple rigid bodies attracts much attention of researchers due to its wide applications. This paper presents the pose synchronization problem of the moving rigid bodies whose dynamics is described by the group SE(3). The case of bidirectional neighbor graphs with switching interconnection topologies is considered. We design a distributed control law based on relative rotation matrices and relative positions between the neighboring rigid bodies, and show that the SE(3) reaches pose synchronization if and only if the neighbor graphs are infinitely jointly connected, which relaxes the theoretical results in the existing literature.

Generalizing the famous Bernstein-Kushnirenko theorem, Khovanskii proved in 1978 a combinatorial formula for the arithmetic genus of the compactification of a generic complete intersection associated to a family of lattice polytopes. Recently, an analogous combinatorial formula, called the discrete mixed volume, was introduced by Bihan and shown to be nonnegative. By making a footnote of Khovanskii in his paper explicit, we interpret this invariant as the (motivic) arithmetic genus of the non-compact generic complete intersection associated to the family of lattice polytopes.

If a pure simplicial complex is partitionable, then its h-vector has a combinatorial interpretation in terms of any partitioning of the complex. Given a non-partitionable complex increment , we construct a complex Gamma superset of increment of the same dimension such that both Gamma and the relative complex (Gamma , increment ) are partitionable. This allows us to rewrite the h-vector of any pure simplicial complex as the difference of two h-vectors of partitionable complexes, giving an analogous interpretation of the h-vector of a non-partitionable complex. By contrast, for a given complex increment it is not always possible to find a complex Gamma such that both Gamma and (Gamma , increment ) are Cohen- Macaulay. We characterize when this is possible, and we show that the construction of such a Gamma in this case is remarkably straightforward. We end with a note on a similar notion for shellability and a connection to Simon's conjecture on extendable shellability for uniform matroids.

The average kissing number in ℝn is the supremum of the average degrees of contact graphs of packings of finitely many balls (of any radii) in ℝn. We provide an upper bound for the average kissing number based on semidefinite programming that improves previous bounds in dimensions 3,.., 9. A very simple upper bound for the average kissing number is twice the kissing number; in dimensions 6,.., 9 our new bound is the first to improve on this simple upper bound.

This paper provides upper and lower bounds on the kissing number of congruent radius r > 0 spheres in hyperbolic H-n and spherical S-n spaces, for n >= 2. For that purpose, the kissing number is replaced by the kissing function kappa(H)(n, r), resp. kappa(S)(n, r), which depends on the dimension n and the radius r. After we obtain some theoretical upper and lower bounds for kappa(H)(n, r), we study their asymptotic behaviour and show, in particular, that kappa(H)(n, r) similar to (n - 1) . d(n-1) . B(n-1/2, 1/2) . e((n-1)r), where d(n) is the sphere packing density in Rn, and B is the beta-function. Then we produce numeric upper bounds by solving a suitable semidefinite program, as well as lower bounds coming from concrete spherical codes. A similar approach allows us to locate the values of kappa(S)(n, r), for n = 3, 4, over subintervals in [0, pi] with relatively high accuracy.

We present a complete classification of all minimal problems for generic arrangements of points and lines completely observed by calibrated perspective cameras. We show that there are only 30 minimal problems in total, no problems exist for more than 6 cameras, for more than 5 points, and for more than 6 lines. We present a sequence of tests for detecting minimality starting with counting degrees of freedom and ending with full symbolic and numeric verification of representative examples. For all minimal problems discovered, we present their algebraic degrees, i.e.the number of solutions, which measure their intrinsic difficulty. It shows how exactly the difficulty of problems grows with the number of views. Importantly, several new minimal problems have small degrees that might be practical in image matching and 3D reconstruction.

When given a Bayesian network, a common use of it is calculating conditional probabilities. This is known as inference. In order to be able to infer effectively, the structure of the Bayesian network is required to have low treewidth. Therefore, the problem of learning the structure of Bayesian networks with bounded treewidth is studied in this thesis. This is solved by reducing the problem to a mixed integer linear problem using several formulation for the structure of the Bayesian network as well as for bounding the treewidth of the structure. Solving the problem in this way gives an algorithm known as an anytime algorithm which can be aborted during the run and return a solution as well as an upper bound for the value of the best possible solution. Tests show that several of these formulations are of practical use as implementations of them prove solutions to be optimal or nearly optimal for several data sets.

We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization. As a special case we obtain proofs of two conjectures of Claesson and Linusson. Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.

We consider a family of birth processes and birth-and-death processes on Young diagrams of integer partitions of n. This family incorporates three famous models from very different fields: Rost's totally asymmetric particle model (in discrete time), Simon's urban growth model, and Moran's infinite alleles model. We study stationary distributions and limit shapes as n tends to infinity, and present a number of results and conjectures.

In a two-sided version of the famous secretary problem, employers search for a secretary at the same time as secretaries search for an employer. Nobody accepts being put on hold, and nobody is willing to take part in more than N interviews. Preferences are independent, and agents seek to optimize the expected rank of the partner they obtain among the N potential partners. We find that in any subgame perfect equilibrium, the expected rank grows as the square root of N (whereas it tends to a constant in the original secretary problem). We also compute how much agents can gain by cooperation.

Coxeter matroids generalize matroids just as flag varieties of Lie groups generalize Grassmannians. Valuations of Coxeter matroids are functions that behave well with respect to subdivisions of a Coxeter matroid into smaller ones. We compute the universal valuative invariant of Coxeter matroids. A key ingredient is the family of Coxeter Schubert matroids, which correspond to the Bruhat cells of flag varieties. In the process, we compute the universal valuation of generalized Coxeter permutohedra, a larger family of polyhedra that model Coxeter analogues of combinatorial objects such as matroids, clusters, and posets.

In the case of the representation of an integer by an indefinite ternary quadratic form, the violation of the integral Hasse principle can be explained via the Brauer-Manin obstruction. In this note, we study the occurrences of this phenomenon for several families of non-diagonal ternary quadratic forms. 

We provide a combinatorial way of computing Speyer’s g-polynomial on arbitrary Schubert matroids via the enumeration of certain Delannoy paths. We define a new statistic of a basis in a matroid, and express the g-polynomial of a Schubert matroid in terms of it and internal and external activities. Some surprising positivity properties of the g-polynomial of Schubert matroids are deduced from our expression. Finally, we combine our formulas with a fundamental result of Derksen and Fink to provide an algorithm for computing the g-polynomial of an arbitrary matroid.