Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphical Designs and Extremal Combinatorics
291
0
0.0
(
0
)
Authors
Konstantin Golubev
Ask ChatGPT about the research
No Arabic abstract
A graphical design is a proper subset of vertices of a graph on which many eigenfunctions of the Laplacian operator have mean value zero. In this paper, we show that extremal independent sets make extremal graphical designs, that is, a design on which the maximum possible number of eigenfunctions have mean value zero. We then provide examples of such graphs and sets, which arise naturally in extremal combinatorics. We also show that sets which realize the isoperimetric constant of a graph make extremal graphical designs, and provide examples for them as well. We investigate the behavior of graphical designs under the operation of weak graph product. In addition, we present a family of extremal graphical designs for the hypercube graph.
rate research
Read More
One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of its eigenvalues. It is easily seen that the Hoffman bound is sharp on the tensor power of a graph whenever it is sharp for the original graph. In this paper, we introduce the related problem of upper-bounding independent sets in tensor powers of hypergraphs. We show that many of the prominent open problems in extremal combinatorics, such as the Turan problem for (hyper-)graphs, can be encoded as special cases of this problem. We also give a new generalization of the Hoffman bound for hypergraphs which is sharp for the tensor power of a hypergraph whenever it is sharp for the original hypergraph. As an application of our Hoffman bound, we make progress on the problem of Frankl on families of sets without extended triangles from 1990. We show that if $frac{1}{2}nle2klefrac{2}{3}n,$ then the extremal family is the star, i.e. the family of all sets that contains a given element. This covers the entire range in which the star is extremal. As another application, we provide spectral proofs for Mantels theorem on triangle-free graphs and for Frankl-Tokushige theorem on $k$-wise intersecting families.
The study of intersection problems in Extremal Combinatorics dates back perhaps to 1938, when Paul ErdH{o}s, Chao Ko and Richard Rado proved the (first) `ErdH{o}s-Ko-Rado theorem on the maximum possible size of an intersecting family of $k$-element subsets of a finite set. Since then, a plethora of results of a similar flavour have been proved, for a range of different mathematical structures, using a wide variety of different methods. Structures studied in this context have included families of vector subspaces, families of graphs, subsets of finite groups with given group actions, and of course uniform hypergraphs with stronger or weaker intersection conditions imposed. The methods used have included purely combinatorial ones such as shifting/compressions, algebraic methods (including linear-algebraic, Fourier analytic and representation-theoretic), and more recently, analytic, probabilistic and regularity-type methods. As well as being natural problems in their own right, intersection problems have connections with many other parts of Combinatorics and with Theoretical Computer Science (and indeed with many other parts of Mathematics), both through the results themselves, and the methods used. In this survey paper, we discuss both old and new results (and both old and new methods), in the field of intersection problems. Many interesting open problems remain; we will discuss several. For expositional and pedagogical purposes, we also take this opportunity to give slightly streamlin
Operads are algebraic devices offering a formalization of the concept of operations with several inputs and one output. Such operations can be naturally composed to form bigger and more complex ones. Coming historically from algebraic topology, operads intervene now as important objects in computer science and in combinatorics. The theory of operads, together with the algebraic setting and the tools accompanying it, promises advances in these two areas. On the one hand, operads provide a useful abstraction of formal expressions, and also, provide connections with the theory of rewrite systems. On the other hand, a lot of operads involving combinatorial objects highlight some of their properties and allow to discover new ones. This book presents the theory of nonsymmetric operads under a combinatorial point of view. It portrays the main elements of this theory and the links it maintains with several areas of computer science and combinatorics. A lot of examples of operads appearing in combinatorics are studied and some constructions relating operads with known algebraic structures are presented. The modern treatment of operads consisting in considering the space of formal power series associated with an operad is developed. Enrichments of nonsymmetric operads as colored, cyclic, and symmetric operads are reviewed. This text is addressed to any computer scientist or combinatorist who looks a complete and a modern description of the theory of nonsymmetric operads. Evenly, this book is intended to an audience of algebraists who are looking for an original point of view fitting in the context of combinatorics.
In this expository paper we describe a powerful combinatorial formula and its implications in geometry, topology, and algebra. This formula first appeared in the appendix of a book by Andersen, Jantzen, and Soergel. Sara Billey discovered it independently five years later, and it played a prominent role in her work to evaluate certain polynomials closely related to Schubert polynomials. Billeys formula relates many pieces of Schubert calculus: the geometry of Schubert varieties, the action of the torus on the flag variety, combinatorial data about permutations, the cohomology of the flag variety and of the Schubert varieties, and the combinatorics of root systems (generalizing
We show that the deletion theorem of a free arrangement is combinatorial, i.e., whether we can delete a hyperplane from a free arrangement keeping freeness depends only on the intersection lattice. In fact, we give an explicit sufficient and necessary condition for the deletion theorem in terms of characteristic polynomials. This gives a lot of corollaries including the existence of free filtrations. The proof is based on the result about the form of minimal generators of a logarithmic derivation module of a multiarrangement which satisfies the $b_2$-equality.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
