scientific article
From MaRDI portal
Publication:2784326
zbMath0996.05001MaRDI QIDQ2784326
Publication date: 23 April 2002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Related Items
Full rainbow matchings in graphs and hypergraphs, The critical mean-field Chayes–Machta dynamics, A generalization of a Turán’s theorem about maximum clique on graphs, An LIL for cover times of disks by planar random walk and Wiener sausage, Short Monadic Second Order Sentences about Sparse Random Graphs, Submodular Functions: Learnability, Structure, and Optimization, Separation and Witnesses, Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism, EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs, Smoothed counting of 0–1 points in polyhedra, On the inclusion chromatic index of a graph, On conflict-free proper colourings of graphs without small degree vertices, Conflict‐free chromatic number versus conflict‐free chromatic index, Dynamic concentration of the triangle‐free process, Ranking graphs through hitting times of Markov chains, Self‐avoiding walk on the hypercube, Distribution of the autocorrelation of random Boolean functions, Lower Bounds for Maximum Weighted Cut, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, Percolation and epidemic processes in one-dimensional small-world networks (extended abstract), Constrained Submodular Maximization via a Nonsymmetric Technique, Bounded quantifier depth spectrum for random uniform hypergraphs, Random Gromov’s monsters do not act non-elementarily on hyperbolic spaces, On some aspects of evolution of generalized allocation schemes, Approximate Polytope Membership Queries, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, On triangle-free list assignments, On the concentration of the chromatic number of random graphs, Infinite Sidon Sets Contained in Sparse Random Sets of Integers, One-Sided Epsilon-Approximants, First-order properties of bounded quantifier depth of very sparse random graphs, Logical laws for short existential monadic second-order sentences about graphs, On the Chromatic Number of Random Cayley Graphs, Unnamed Item, Projections in vector spaces over finite fields, The Zero Forcing Number of Graphs, Assortment Optimization Under the Paired Combinatorial Logit Model, A short proof of Bernoulli disjointness via the local lemma, A note on improved upper bounds on the transversal number of hypergraphs, Packing Arborescences in Random Digraphs, On the coalescence time of reversible random walks, Deterministic extractors for small-space sources, On percolation and ‐hardness, Voting Procedures, Complexity of, ON EXTREME JOINT PROBABILITIES OF k EVENTS CHOSEN FROM n EVENTS, The chromatic number of the space $( {\mathbb R}^n, l_1)$, Induced Ramsey-type theorems, The intrinsic dimensionality of graphs, Induced Ramsey-type theorems, Threshold Functions for Distinct Parts: Revisiting Erdős–Lehner, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, The Hausdorff dimension of a class of random self-similar fractal trees, Unnamed Item, Using Rademacher permutations to reduce randomness, Extracting all the randomness and reducing the error in Trevisan's extractors, An approximation algorithm for the partial vertex cover problem in hypergraphs, On the distance domination number of bipartite graphs, Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint, A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs, Distant sum distinguishing index of graphs with bounded minimum degree, Unnamed Item, Length of the Longest Common Subsequence between Overlapping Words, Guess free maximization of submodular and linear sums, Expansion and Lack Thereof in Randomly Perturbed Graphs, The Communication Complexity of Distributed epsilon-Approximations, Nonrepetitive colorings of graphs, On Restriction Estimates for the Zero Radius Sphere over Finite Fields, Growth in groups: ideas and perspectives, Unnamed Item, Unnamed Item, Algorithmic Aspects of Combinatorial Discrepancy, The rank of sparse random matrices, Properties of Boolean functions with the extremal number of prime implicants, A note on the weak \((2,2)\)-conjecture, Some progress on the double Roman domination in graphs, Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, Plateaus can be harder in multi-objective optimization, Perfect matchings in uniform hypergraphs with large minimum degree, Retracted: A remark on the weak Turán's theorem, On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs, Probabilistic extensions of the Erdős-Ko-Rado property, Finite covers of random 3-manifolds, Nonrepetitive colorings of trees, Models of random knots, Packing directed cycles efficiently, Asymptotic behavior of the expected optimal value of the multidimensional assignment problem, Codes identifying sets of vertices in random networks, On the nonlinearity of monotone Boolean functions, Binary templates for comma-free DNA codes, Hamilton cycles in sparse robustly expanding digraphs, Pattern avoidance on graphs, Turán's theorem for pseudo-random graphs, Note on maximal bisection above tight lower bound, Properly coloured Hamiltonian cycles in edge-coloured complete graphs, A structure theorem for product sets in extra special groups, Randomized algorithm for the sum selection problem, Induced subgraphs of Ramsey graphs with many distinct degrees, Distant set distinguishing edge colourings of graphs, Diameters of random distance graphs, The halflie problem., Maximum cuts and judicious partitions in graphs without short cycles, Partitions of graphs with high minimum degree or connectivity., Domination analysis of combinatorial optimization problems., Matrix and discrepancy view of generalized random and quasirandom graphs, On \(r\)-dynamic chromatic number of graphs, Regret-based continuous-time dynamics., Problems and results in extremal combinatorics. I., An improved upper bound for the pebbling threshold of the \(n\)-path, An evolutionary approach to learning in a changing environment., On codes from hypergraphs., Independence numbers of hypergraphs with sparse neighborhoods., The Kadison-Singer problem in discrepancy theory., On forbidden subdivision characterizations of graph classes, The upper bound on \(k\)-tuple domination numbers of graphs, Nonrepetitive colorings of graphs -- a survey, A phase transition for a random cluster model on phylogenetic trees., Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning, Shadows and intersections: Stability and new proofs, The maximum edit distance from hereditary graph properties, Diffusion limited aggregation on a cylinder, Critical random graphs: Diameter and mixing time, Thue type problems for graphs, points, and numbers, Density of constant radius normal binary covering codes, Problems and results in extremal combinatorics. II, Covering the \(n\)-space by convex bodies and its chromatic number, Edge-colorings avoiding rainbow and monochromatic subgraphs, On the chromatic number of random graphs, Complexity measures of sign matrices, An approximate Dirac-type theorem for \(k\)-uniform hypergraphs, Embedding nearly-spanning bounded degree trees, The Grothendieck constant of random and pseudo-random graphs, Large independent sets in general random intersection graphs, Random sampling of colourings of sparse random graphs with a constant number of colours, Decomposition of multiple coverings into many parts, An estimate for the probability of dependent events, Proof of a conjecture on \(k\)-tuple domination in graphs, Edge colouring by total labellings, \(t\)-wise independence with local dependencies, An almost quadratic bound on vertex Folkman numbers, Large induced subgraphs with equated maximum degree, Rainbow paths, On rough isometries of Poisson processes on the line, An updated survey on the linear ordering problem for weighted or unweighted tournaments, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, Expected values of parameters associated with the minimum rank of a graph, On nearly radial marginals of high-dimensional probability measures, Hamiltonian degree sequences in digraphs, Pancyclicity of Hamiltonian and highly connected graphs, Invisible runners in finite fields, A note on the distribution of the number of prime factors of the integers, Discrepancy and signed domination in graphs and hypergraphs, Gibbs measures and phase transitions on sparse random graphs, Thresholding random geometric graph properties motivated by ad hoc sensor networks, Large sets in finite fields are sumsets, Vertex percolation on expander graphs, The degree distribution of random \(k\)-trees, A note on the distribution of the distance from a lattice, Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures, Large disjoint subgraphs with the same order and size, On sets of points that determine only acute angles, Topology of random clique complexes, Triangle packings and 1-factors in oriented graphs, Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number, Expander properties and the cover time of random intersection graphs, Two remarks on the Burr-Erdős conjecture, Two-batch liar games on a general bounded channel, On the cubicity of certain graphs, Some results on the incidence coloring number of a graph, Random regular graphs of non-constant degree: concentration of the chromatic number, On \(k\)-chromatically connected graphs, On character sums with distances on the upper half plane over a finite field, On distinct distances among points in general position and other related problems, A slight sharpening of LMN, The DNF exception problem, Asymptotic properties of random multidimensional assignment problems, Dynamic moral hazard without commitment, Bounded quantifier depth spectra for random graphs, On random subgraphs of Kneser and Schrijver graphs, Increasing paths in edge-ordered graphs: the hypercube and random graph, On decomposing graphs of large minimum degree into locally irregular subgraphs, On large subgraphs with small chromatic numbers contained in distance graphs, Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Dynamical sensitivity of the infinite cluster in critical percolation, Essential sign change numbers of full sign pattern matrices, Graph-theoretic design and analysis of key predistribution schemes, The cross-correlation measure of families of finite binary sequences: limiting distributions and minimal values, Universal zero-one \(k\)-law, On the zero-one \(k\)-law extensions, Conditional expanding bounds for two-variable functions over finite valuation rings, Computing Boolean functions from multiple faulty copies of input bits, Hadamard tensors and lower bounds on multiparty communication complexity, On the density of a graph and its blowup, \((2,1)\)-separating systems beyond the probabilistic bound, Correlation through bounded recall strategies, Maximal independent sets in bipartite graphs obtained from Boolean lattices, The structure of popular difference sets, Rainbow edge-coloring and rainbow domination, Some recent results on Ramsey-type numbers, Maximal independent sets in the covering graph of the cube, Parameterized complexity of MaxSat above average, A new bound for 3-satisfiable MaxSat and its algorithmic application, On high-dimensional acyclic tournaments, New bounds for the distance Ramsey number, Can colour-blind distinguish colour palettes?, On the number of orientations of random graphs with no directed cycles of a given length, On point-line incidences in vector spaces over finite fields, Stationary distribution and cover time of random walks on random digraphs, \(H\)-colouring bipartite graphs, Crossover can provably be useful in evolutionary computation, Zero-one \(k\)-law, A study of 3-arc graphs, Counterexamples to Borsuk's conjecture on spheres of small radius, Two are better than one: fundamental parameters of frame coherence, On derandomization and average-case complexity of monotone functions, Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube, Random half-integral polytopes, Two problems on independent sets in graphs, A structure theorem for Boolean functions with small total influences, Complexity of hard-core set proofs, Approximation algorithms for maximum independent set of pseudo-disks, Perfect matchings as IID factors on non-amenable groups, The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields, Combinatorial and computational aspects of graph packing and graph decomposition, On the independence number and Hamiltonicity of uniform random intersection graphs, Typical unpreparability of quantum states with quantum circuit model, What is Ramsey-equivalent to a clique?, On the least trimmed squares estimator, Nonrepetitive vertex colorings of graphs, Singular matrices with restricted rows in vector spaces over finite fields, On a Furstenberg-Katznelson-Weiss type theorem over finite fields, Colorful strips, Small spectral gap in the combinatorial Laplacian implies Hamiltonian, Upper bounds on the balanced \(\langle \mathbf{r}, \mathbf{s} \rangle\)-domination number of a graph, On the continuity of graph parameters, Degenerate and star colorings of graphs on surfaces, The strategic value of recall, A note on the discrepancy of matrices with bounded row and column sums, Discrete norms of a matrix and the converse to the expander mixing lemma, Random Kneser graphs and hypergraphs, Register loading via linear programming, Incidences between points and generalized spheres over finite fields and related problems, Lazy Cops and Robbers on generalized hypercubes, On a general many-dimensional excited random walk, \(L_p\) compression, traveling salesmen, and stable walks., Novel scaling limits for critical inhomogeneous random graphs, Discrepancy, chaining and subgaussian processes, Concentration of measure for quantum states with a fixed expectation value, Cubic polyhedral Ramanujan graphs with face size no larger than six, Vertex coloring complete multipartite graphs from random lists of size 2, On uncertainty principles in the finite dimensional setting, Optimal permutation anticodes with the infinity norm via permanents of \((0,1)\)-matrices, Connectivity and equilibrium in random games, Maximal operators and differentiation theorems for sparse sets, Pattern avoidance: themes and variations, Upper bounds for the 2-hued chromatic number of graphs in terms of the independence number, \(H\)-coloring tori, Distance edge-colourings and matchings, Semidefinite optimization in discrepancy theory, Is the critical percolation probability local?, Boolean-width of graphs, Distinct distances between points and lines in \(\mathbb{F}_q^2\), On codeword design in metric DNA spaces, Invitation to intersection problems for finite sets, Monochromatic sum and product in \(\mathbb{Z} / m \mathbb{Z}\), On the generalized Erdős-Falconer distance problems over finite fields, A randomised approximation algorithm for the hitting set problem, The Turán number of sparse spanning graphs, On the realization of subgraphs of a random graph by diameter graphs in Euclidean spaces, On a sequence of random distance graphs subject to the zero-one law, The structure of bull-free graphs I -- three-edge-paths with centers and anticenters, Independence numbers and chromatic numbers of some distance graphs, Relating multiway discrepancy and singular values of nonnegative rectangular matrices, Randomized approximation for the set multicover problem in hypergraphs, On homogeneous sets of positive integers, Strictly balanced uniform hypergraphs and generalizations of zero-one law, A decomposability index in logical analysis of data, Percolation on finite graphs and isoperimetric inequalities., Upper tails for subgraph counts in random graphs, Colouring powers of cycles from random lists, Inapproximability results for equations over finite groups, Typical rounding problems, Embedding graphs with bounded degree in sparse pseudorandom graphs, The number of edge-disjoint transitive triples in a tournament, Lower bounds for intersection searching and fractional cascading in higher dimension, Swarming on random graphs, Optimal inter-object correlation when replicating for availability, Random subgraphs of the 2D Hamming graph: The supercritical phase, On the \(L_{2}\)-discrepancy, Compositions of random transpositions, Independent transversals in locally sparse graphs, On thin sum-product bases, Approximating a sequence of observations by a simple process, Almost envy-freeness for groups: improved bounds via discrepancy theory, Sharp bounds for the chromatic number of random Kneser graphs, Graph coloring applied to secure computation in non-abelian groups, Gigantic component in random distance graphs of special form, On proper colorings of hypergraphs, Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size, Diversity in times of adversity: probabilistic strategies in microbial survival games, Rainbow connections of graphs: a survey, First order sentences about random graphs: small number of alternations, Collapsibility and vanishing of top homology in random simplicial complexes, Dominating set based exact algorithms for \(3\)-coloring, Distant total irregularity strength of graphs via random vertex ordering, Comparing the strength of query types in property testing: the case of \(k\)-colorability, Upper bound in the Erdős-Hajnal problem of hypergraph coloring, Gigantic and small components in random distance graphs of special form, On \(\alpha \)-domination in graphs, Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk, Tight bounds for shared memory systems accessed by Byzantine processes, Distance graphs with large chromatic number and without large cliques, Distant total sum distinguishing index of graphs, Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false, A note on asymptotically optimal neighbour sum distinguishing colourings, Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination, Upper bounds on the global offensive alliances in graphs, Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs, The 1-2-3 conjecture almost holds for regular graphs, On weak \(\epsilon\)-nets and the Radon number, Generalized arboricity of graphs with large girth, Hat chromatic number of graphs, Constructing dominating sets in circulant graphs, Some combinatorial number theory problems over finite valuation rings, A moment-generating formula for Erdős-Rényi component sizes, The multicovering radius problem for some types of discrete structures, A weighted regularity lemma with applications, Cluster tails for critical power-law inhomogeneous random graphs, Dimension reduction by random hyperplane tessellations, On colour-blind distinguishing colour pallets in regular graphs, The convexification effect of Minkowski summation, Distance graphs with large chromatic numbers and small clique numbers, Indicated coloring of graphs, Sequential complexities and uniform martingale laws of large numbers, One problem on geometric Ramsey numbers, Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\), Existential monadic second order convergence law fails on sparse random graphs, Evolutionary accessibility of modular fitness landscapes, Deterministic discrepancy minimization, Integer sets with prescribed pairwise differences being distinct, Minima in branching random walks, Decomposability of graphs into subgraphs fulfilling the 1-2-3 conjecture, Conflict-free coloring of string graphs, Gap-free compositions and gap-free samples of geometric random variables, Distance graphs with large chromatic number and without cliques of given size in the rational space, Building large free subshifts using the Local Lemma, Inclusion total chromatic number, Sequence length bounds for resolving a deep phylogenetic divergence, A note on the global offensive alliances in graphs, Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem, Rank conditions for sign patterns that allow diagonalizability, Infinite spectra of first-order properties for random hypergraphs, New probabilistic upper bounds on the domination number of a graph, Measurable versions of the Lovász local lemma and measurable graph colorings, On the rainbow matching conjecture for 3-uniform hypergraphs, Quantitative aspects of acyclicity, Limit laws for self-loops and multiple edges in the configuration model, Asymptotically the list colouring constants are 1, On the concentration of eigenvalues of random symmetric matrices, Total Thue colourings of graphs, Permutations destroying arithmetic structure, Epidemics on small worlds of tree-based wireless sensor networks, The probabilistic approach to limited packings in graphs, On the hardness of solving edge matching puzzles as SAT or CSP problems, \(F\)-factors in hypergraphs via absorption, Lower bounds of the skew spectral radii and skew energy of oriented graphs, On decomposing regular graphs into locally irregular subgraphs, Voting paradoxes and digraphs realizations, Asymmetric binary covering codes., On 2-coloring certain \(k\)-uniform hypergraphs, On general frameworks and threshold functions for multiple domination, On the zero-one 4-law for the Erdős-Rényi random graphs, Ample simplicial complexes, On coupon colorings of graphs, Rank of random half-integral polytopes — extended abstract —, Serving in the Dark should be done Non-Uniformly, Distant set distinguishing total colourings of graphs, The number of occurrences of a fixed spread among \(n\) directions in vector spaces over finite fields, Colouring Non-sparse Random Intersection Graphs, Some Introductory Notes on Random Graphs, The Mahler Conjecture in Two Dimensions via the Probabilistic Method, Hardness of fully dense problems, Additive approximation for edge-deletion problems, A survey on the linear ordering problem for weighted or unweighted tournaments, Relativized collapsing between BPP and PH under stringent oracle access, On Compiling Structured CNFs to OBDDs, Large communities in a scale-free network, On the longest path of a randomly weighted tournament, Poisson approximation for non-backtracking random walks, Generalized threshold processes on graphs, Limit points of spectra for first-order properties of random hypergraphs, Cycles in random meander systems, High entropy random selection protocols, The covering radius problem for sets of 1-factors of the complete uniform hypergraphs, On a local similarity of graphs, On the sizes of large subgraphs of the binomial random graph, Distant irregularity strength of graphs with bounded minimum degree, Degree Ramsey numbers for even cycles, The Domination Number of On-line Social Networks and Random Geometric Graphs, Graphs with $\chi=\Delta$ Have Big Cliques, Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms], How Many Conflicts Does It Need to Be Unsatisfiable?, On Ramsey Type Problems in Combinatorial Geometry, Partial Colorings of Unimodular Hypergraphs, Discrepancy of Sums of two Arithmetic Progressions, Random Graphs, Retractions and Clique Graphs, The loss of serving in the dark, Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms, Accessibility percolation on Cartesian power graphs, Thresholds for virus spread on networks, Expander graphs and their applications, A Poisson Approximation for an Occupancy Problem with Collisions, Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022, Hamilton decompositions of regular expanders: applications, On defensive alliances and strong global offensive alliances, Local/Global Phenomena in Geometrically Generated Graphs, Combinatorial extremum problems for 2-colorings of hypergraphs, The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs, Equivariant maps to subshifts whose points have small stabilizers, On two-variable expanders over finite rings, On distance sets and product sets in vector spaces over finite rings, Small Sample Spaces Cannot Fool Low Degree Polynomials, Limits of locally-globally convergent graph sequences, Random binary trees: from the average case analysis to the asymptotics of distributions, Choosability of graphs with infinite sets of forbidden differences, Improved bounds on acyclic edge colouring, New bounds on the \(k\)-domination number and the \(k\)-tuple domination number, On the expected maximum degree of Gabriel and Yao graphs, Bertrand's postulate, the prime number theorem and product anti-magic graphs, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Breaking the rhythm on graphs, Finding a vector orthogonal to roughly half a collection of vectors, An inscribing model for random polytopes, Practical construction and analysis of pseudo-randomness primitives, A sufficient condition for the bicolorability of a hypergraph, A once edge-reinforced random walk on a Galton-Watson tree is transient, Hypergraph Ramsey numbers, Non-independent randomized rounding and coloring, Logarithmic reduction of the level of randomness in some probabilistic geometric constructions, Maximal clusters in non-critical percolation and related models, On a hypergraph matching problem, A \((1-1/e)\)-approximation algorithm for the generalized assignment problem, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, Random edge can be exponential on abstract cubes, Generalized \(k\)-multiway cut problems, Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number, The threshold function for vanishing of the top homology group of random 𝑑-complexes, Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences, Limitations of randomized mechanisms for combinatorial auctions, On a conjecture of Thomassen, On the maximum values of the additive representation functions, On a series of Ramsey-type problems in combinatorial geometry, On the permanent of random Bernoulli matrices, On Testing Expansion in Bounded-Degree Graphs, On the Average-Case Complexity of Property Testing, Phase transitions in phylogeny, Selected Combinatorial Properties of Random Intersection Graphs, Sieving by large integers and covering systems of congruences, Tournaments and Semicomplete Digraphs, Ramsey functions involving \(K_{m,n}\) with \(n\) large, Small clique and large chromatic number, Counting and representing intersections among triangles in three dimensions, Random subgraphs of finite graphs. II: The lace expansion and the triangle condition, On the power of two choices: balls and bins in continuous time, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, Monotone maps, sphericity and bounded second eigenvalue, Efficient gossip and robust distributed computation, Locally consistent constraint satisfaction problems, A hypergraph extension of Turán's theorem, Performing work with asynchronous processors: Message-delay-sensitive bounds, SAT distributions with planted assignments and phase transitions between decision and optimization problems, Coordination through de Bruijn sequences, SAT Distributions with Phase Transitions between Decision and Optimization Problems, Discrepancy of Sums of Arithmetic Progressions
