Extremal Combinatorics
From MaRDI portal
Publication:3061152
DOI10.1007/978-3-642-17364-6zbMath1239.05001MaRDI QIDQ3061152
Publication date: 14 December 2010
Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-17364-6
combinatorics; Ramsey theory; extremal set theory; communication complexity; spectral graph theory; polynomial method; linear algebra method; probablistic method
05D05: Extremal set theory
05D10: Ramsey theory
05-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
Related Items
New applications of the polynomial method: The cap set conjecture and beyond, Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic, Unnamed Item, Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$, Combinatorics in the exterior algebra and the Bollobás Two Families Theorem, Constructing integer-magic graphs via the Combinatorial Nullstellensatz, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, Some open questions about line arrangements in the projective plane, A Probability Perspective to a Combinatorics Problem, Algorithmic Polynomials, On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs, Approximate Counting of k-Paths: Deterministic and in Polynomial Space, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Rank Vertex Cover as a Natural Problem for Algebraic Compression, LONELY RUNNERS IN FUNCTION FIELDS, Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs, Erdös--Hajnal Properties for Powers of Sparse Graphs, An Optimal Separation of Randomized and Quantum Query Complexity, Exploiting c-Closure in Kernelization Algorithms for Graph Problems, Parameterized complexity of perfectly matched sets, Immune sets in monotone infection rules. Characterization and complexity, Competitive Algorithms for Generalized k -Server in Uniform Metrics, Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings, Bussey systems and Steiner's tactical problem, Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius, 2-step nilpotent \(L_{\infty}\)-algebras and hypergraphs, Word-Size RMR Tradeoffs for Recoverable Mutual Exclusion, Size, Depth and Energy of Threshold Circuits Computing Parity Function., On the path separation number of graphs, Reducing rank of the adjacency matrix by graph modification, On the number of orientations of random graphs with no directed cycles of a given length, On the number of matroids compared to the number of sparse paving matroids, Determining majority in networks with local interactions and very small local memory, Rank reduction of oriented graphs by vertex and edge deletions, Partial covering arrays: algorithms and asymptotics, Exploiting hidden structure in selecting dimensions that distinguish vectors, Linear preservers for the \(q\)-permanent, cycle \(q\)-permanent expansions, and positive crossings in digraphs, Convex geometries are extremal for the generalized Sauer-Shelah bound, Dioid partitions of groups, Bayesian-OverDBC: a Bayesian density-based approach for modeling overlapping clusters, Noncrossing partitions, noncrossing graphs, and \(q\)-permanental equations, On the existence of ordinary triangles, Colored ray configurations, Multiplicative complexity of vector valued Boolean functions, A new decomposition technique for maximal clique enumeration for sparse graphs, On the number of bases of almost all matroids, Representability of Lyndon-Maddux relation algebras, Fractional \(L\)-intersecting families, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, On the complexity of monotone circuits for threshold symmetric Boolean functions, On the mutual visibility in Cartesian products and triangle-free graphs, Correlation bounds for fields and matroids, On the geography of line arrangements, Bipartite Hansel results for hypergraphs, System of unbiased representatives for a collection of bicolorings, Wide-sense 2-frameproof codes, On efficiently solvable cases of quantum \(k\)-SAT, The main eigenvalues of signed graphs, Uniform forcing and immune sets in graphs and hypergraphs, Balas formulation for the union of polytopes is optimal, Daisy cubes and distance cube polynomial, Computing majority by constant depth majority circuits with low fan-in gates, From edge-coloring to strong edge-coloring, Linearized Wenger graphs, Counting colorings of a regular graph, A note on the gap between rank and border rank, Almost difference sets in nonabelian groups, Cubicity, degeneracy, and crossing number, Limiting curves for the Pascal adic transformation, The complexity of binary matrix completion under diameter constraints, The Turán number of directed paths and oriented cycles, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Extensions of Fractional Precolorings Show Discontinuous Behavior, A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time, Reducing Rank of the Adjacency Matrix by Graph Modification, Trades in Complex Hadamard Matrices
