Results 111 to 120 of about 997,897 (240)
Reconstructing Random Pictures
Random Structures &Algorithms, Volume 66, Issue 1, January 2025.ABSTRACT Given a random binary picture Pn$$ {P}_n $$ of size n$$ n $$, that is, an n×n$$ n\times n $$ grid filled with zeros and ones uniformly at random, when is it possible to reconstruct Pn$$ {P}_n $$ from its k$$ k $$‐deck, that is, the multiset of all its k×k$$ k\times k $$ subgrids?
Bhargav Narayanan, Corrine Yap
wiley +1 more source
Short proofs of some extremal results III [PDF]
arXiv, 2019 We prove a selection of results from different areas of extremal combinatorics, including complete or partial solutions to a number of open problems. These results, coming mainly from extremal graph theory and Ramsey theory, have been collected together because in each case the relevant proofs are reasonably short.
arxiv
Discrete Analysis, 2017 Quasirandom Cayley graphs, Discrete Analysis 2017:6, 14 pp. An extremely important phenomenon in extremal combinatorics is that of _quasirandomness_: for many combinatorial structures, it is possible to identify a list of deterministic properties, each ...
David Conlon, Yufei Zhao
doaj +1 more source
Short proofs of some extremal results II [PDF]
arXiv, 2015 We prove several results from different areas of extremal combinatorics, including complete or partial solutions to a number of open problems. These results, coming mainly from extremal graph theory and Ramsey theory, have been collected together because in each case the relevant proofs are quite short.
arxiv
Lengths of extremal square-free ternary words [PDF]
arXiv, 2020 A square-free word $w$ over a fixed alphabet $\Sigma$ is extremal if every word obtained from $w$ by inserting a single letter from $\Sigma$ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free ternary words.
arxiv
Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case
Discrete Analysis, 2017 Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case, Discrete Analysis 2017:5, 34 pp. Szemerédi's theorem, proved in 1975, asserts that for every positive integer $k$ and every $\delta>0$ there exists $n$ such that every subset
Sean Prendiville
doaj +1 more source
Beyond sum-free sets in the natural numbers [PDF]
, 2014 For an interval [1,N]⊆N, sets S⊆[1,N] with the property that |{(x,y)∈S2:x+y∈S}|=0, known as sum-free sets, have attracted considerable attention. In this paper, we generalize this notion by considering r(S)=|{(x,y)∈S2:x+y∈S}|, and analyze its behaviour ...
Huczynska, Sophie
core
Improving bounds on packing densities of 4-point permutations
, 2018 We consolidate what is currently known about packing densities of 4-point permutations and in the process improve the lower bounds for the packing densities of 1324 and 1342.
Sliacan, Jakub, Stromquist, Walter
core +1 more source
The number of extremal components of an extremal measure [PDF]
arXiv, 2010 It is known that the Littlewood-Richardson coefficients can be calculated using a certain class of measures, and these measures have a rigidity property when the coefficient is equal to 1. Rigid measures decompose uniquely into sums of extremal rigid measures.
arxiv
A Note on the Frankl Conjecture [PDF]
arXiv, 2019 The Frankl conjecture (called also union-closed sets conjecture) is one of the famous unsolved conjectures in combinatorics of finite sets. In this short note, we introduce and to some extent justify some variants of the Frankl conjecture.
arxiv