Search

We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0B\sqrt{n}\log{n}$. This is a factor of $\Theta(\sqrt{\log{n}})$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

We study the classical \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{\varOmega (\sqrt{\log n})}}$$\end{document}2Ω(logn), assuming \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}\not \subseteq \mathsf {DTIME}(n^{\mathcal {O}(\log n)})}$$\end{document}NP⊈DTIME(nO(logn)). This constitutes a significant gap to the best known approximation upper bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al. (Theory Comput 2:137–146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365–374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(1)}$$\end{document}O(1)-approximation when edges (or nodes) may be used by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}\left( \log n/\log \log n\right) }$$\end{document}Ologn/loglogn paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results:For MaxEDP, we give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{r} \log ({k}r))}$$\end{document}O(rlog(kr))-approximation algorithm. Up to a logarithmic factor, our result strengthens the best known ratio \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\sqrt{n})}$$\end{document}O(n) due to Chekuri et al., as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r\le n}$$\end{document}r≤n.Further, we show how to route \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varOmega ({\text {OPT}}^{*})}$$\end{document}Ω(OPT∗) pairs with congestion bounded by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}(\log (kr)/\log \log (kr))}$$\end{document}O(log(kr)/loglog(kr)), strengthening the bound obtained by the classic approach of Raghavan and Thompson.For MaxNDP, we give an algorithm that gives the optimal answer in time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${(k+r)^{\mathcal {O}(r)}\cdot n}$$\end{document}(k+r)O(r)·n. This is a substantial improvement on the run time of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^kr^{\mathcal {O}(r)}\cdot n}$$\end{document}2krO(r)·n, which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {NP}}$$\end{document}NP-hard even for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r=1}$$\end{document}r=1, and MaxNDP is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {W}[1]}$$\end{document}W[1]-hard when r is the parameter. This shows that neither problem is fixed-parameter tractable in r unless \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {FPT}= \mathsf {W}[1]}$$\end{document}FPT=W[1] and that our approximability results are relevant even for very small constant values of r.

Let us fix a prime $p$. The Erd\H{o}s-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $\mathbb{Z}^n$ contains $p$ points whose centroid is also a lattice point in $\mathbb{Z}^n$. For large $n$, this is essentially equivalent to asking for the maximum size of a subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero. In this paper, we give a new upper bound for this problem for any fixed prime $p\geq 5$ and large $n$. In particular, we prove that any subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero has size at most $C_p\cdot \left(2\sqrt{p}\right)^n$, where $C_p$ is a constant only depending on $p$. For $p$ and $n$ going to infinity, our bound is of the form $p^{(1/2)\cdot (1+o(1))n}$, whereas all previously known upper bounds were of the form $p^{(1-o(1))n}$ (with $p^n$ being a trivial bound). Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method. This method and its consequences were already applied by Naslund as well as by Fox and the author to prove bounds for the problem studied in this paper. However, using some key new ideas, we significantly improve their bounds., Comment: 11 pages

Let $S \subset \Bbb R^n$ be a smooth compact hypersurface with a strictly positive second fundamental form, $E$ be the Fourier extension operator on $S$, and $X$ be a Lebesgue measurable subset of $\Bbb R^n$. If $X$ contains a ball of each radius, then the problem of determining the range of exponents $(p,q)$ for which the estimate $\| Ef \|_{L^q(X)} \leq C \| f \|_{L^p(S)}$ holds is equivalent to the restriction conjecture. In this paper, we study the estimate under the following assumption on the set $X$: there is a number $0 < \alpha \leq n$ such that $|X \cap B_R| \leq c \, R^\alpha$ for all balls $B_R$ in $\Bbb R^n$ of radius $R \geq 1$. On the left-hand side of this estimate, we are integrating the function $|Ef(x)|^q$ against the measure $\chi_X dx$. Our approach consists of replacing the characteristic function $\chi_X$ of $X$ by an appropriate weight function $H$, and studying the resulting estimate in three different regimes: small values of $\alpha$, intermediate values of $\alpha$, and large values of $\alpha$. In the first regime, we establish the estimate by using already available methods. In the second regime, we prove a weighted H\"{o}lder-type inequality that holds for general non-negative Lebesgue measurable functions on $\Bbb R^n$, and combine it with the result from the first regime. In the third regime, we borrow a recent fractal Fourier restriction theorem of Du and Zhang and combine it with the result from the second regime. In the opposite direction, the results of this paper improve on the Du-Zhang theorem in the range $0 < \alpha < n/2$., Comment: 31 pages. Minor revision

A classical theorem of Koksma states that for Lebesgue almost every $x>1$ the sequence $(x^n)_{n=1}^{\infty}$ is uniformly distributed modulo one. In the present paper we extend Koksma's theorem to the pair correlation setting. More precisely, we show that for Lebesgue almost every $x>1$ the pair correlations of the fractional parts of $(x^n)_{n=1}^{\infty}$ are asymptotically Poissonian. The proof is based on a martingale approximation method., Version 2: some minor changes. The paper will appear in the Israel Journal of Mathematics

In this paper we study 1/k geodesics, those closed geodesics that minimize on all subintervals of length $L/k$, where $L$ is the length of the geodesic. We develop new techniques to study the minimizing properties of these curves on doubled polygons, and demonstrate a sequence of doubled polygons whose closed geodesics exhibit unbounded minimizing properties. We also compute the length of the shortest closed geodesic on doubled odd-gons and show that this length approaches 4 times the diameter., Comment: This paper is a result of a SUMRY (REU) project at Yale

In this paper we study some cube packing problems. In particular we are interested in compact subsets of $\mathbb{R}^n,n\geq 2$, which contain boundaries of cubes with all side lengths in $(0,1)$. We show here that such sets must have lower box dimension at least $n-0.5$ and we will also provide sharp examples. We also show here that such sets must be large in general in a precise sense which is also introduced in this paper., 9 pages. arXiv admin note: text overlap with arXiv:1711.06533

This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-three}. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model $G(2n,p,q)$, which is a random graph consisting of two distinct Erdős-Renyi graphs $G(n,p)$ joined by random edges with density $q\leq p$. We obtain two main results. First, if $p=\omega(\log n/n)$ and $r=q/p$ is a constant, we show that there is a phase transition in $r$ with threshold $r^*$ (specifically, $r^*=\sqrt{5}-2$ for the Best-of-two, and $r^*=1/7$ for the Best-of-three). If $r>r^*$, the process reaches consensus within $O(\log \log n+\log n/\log (np))$ steps for any initial opinion configuration with a bias of $\Omega(n)$. By contrast, if $r r^*$, we show that, for any initial opinion configuration, the process reaches consensus within $O(\log n)$ steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.

A graph Γ is called a bi-circulant if it admits a cyclic group as a group of automorphisms acting semiregularly on the vertices of Γ with two orbits. The characterization of tetravalent edgetransitive bi-circulants was given in several recent papers. In this paper, a classification is given of connected tetravalent vertex-transitive bi-circulants of order twice an odd integer.

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work., Comment: An an earlier version of this paper appeared in SODA 2010. That paper contained preliminary versions of some of the results of this paper

Let G be a graph with vertex set V(G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …, |E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to $${{1 + \left| {E(G)} \right|} \over 2} \cdot d(v)$$ , where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V(G), |{e : e ∈ Ev, f(e) ≤ Δ/2}| = |{e : e ∈ Ev, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.

Associated to a presentable $\infty$-category $\mathcal{C}$ and an object $X \in \mathcal{C}$ is the tangent $\infty$-category $\mathcal{T}_X\mathcal{C}$, consisting of parameterized spectrum objects over $X$. This gives rise to a cohomology theory, called Quillen cohomology, whose category of coefficients is $\mathcal{T}_X\mathcal{C}$. When $\mathcal{C}$ consists of algebras over a nice $\infty$-operad in a stable $\infty$-category, $\mathcal{T}_X\mathcal{C}$ is equivalent to the $\infty$-category of operadic modules, by work of Basterra--Mandell, Schwede and Lurie. In this paper we develop the model-categorical counterpart of this identification and extend it to the case of algebras over an enriched operad, taking values in a model category which is not necessarily stable. This extended comparison can be used, for example, to identify the cotangent complex of enriched categories, an application we take up in a subsequent paper., Comment: The section concerning stabilization of model categories was separated into an independent paper, appearing now as arXiv:1802.08031

In the first part of the paper, we clarify the connections between several algebraic objects appearing in matroid theory: both partial fields and hyperfields are fuzzy rings, fuzzy rings are tracts, and these relations are compatible with the respective matroid theories. Moreover, fuzzy rings are ordered blueprints and lie in the intersection of tracts with ordered blueprints; we call the objects of this intersection pastures. In the second part, we construct moduli spaces for matroids over pastures. We show that, for any non-empty finite set $E$, the functor taking a pasture $F$ to the set of isomorphism classes of rank-$r$ $F$-matroids on $E$ is representable by an ordered blue scheme $Mat(r,E)$, the moduli space of rank-$r$ matroids on $E$. In the third part, we draw conclusions on matroid theory. A classical rank-$r$ matroid $M$ on $E$ corresponds to a $\mathbb{K}$-valued point of $Mat(r,E)$ where $\mathbb{K}$ is the Krasner hyperfield. Such a point defines a residue pasture $k_M$, which we call the universal pasture of $M$. We show that for every pasture $F$, morphisms $k_M\to F$ are canonically in bijection with $F$-matroid structures on $M$. An analogous weak universal pasture $k_M^w$ classifies weak $F$-matroid structures on $M$. The unit group of $k_M^w$ can be canonically identified with the Tutte group of $M$. We call the sub-pasture $k_M^f$ of $k_M^w$ generated by ``cross-ratios' the foundation of $M$,. It parametrizes rescaling classes of weak $F$-matroid structures on $M$, and its unit group is coincides with the inner Tutte group of $M$. We show that a matroid $M$ is regular if and only if its foundation is the regular partial field, and a non-regular matroid $M$ is binary if and only if its foundation is the field with two elements. This yields a new proof of the fact that a matroid is regular if and only if it is both binary and orientable., 85 pages; some additional material, e.g. a new section 5.6; the terminology has been adapted to the usage in follow-up papers

This paper is devoted to the study of the quadruple Roman domination in trees, and it is a contribution to the Special Issue “Theoretical computer science and discrete mathematics” of Symmetry. For any positive integer k, a [k]-Roman dominating function ([k]-RDF) of a simple graph G is a function from the vertex set V of G to the set {0,1,2,…,k+1} if for any vertex u∈V with f(u)&lt, k, ∑x∈N(u)∪{u}f(x)≥|{x∈N(u):f(x)≥1}|+k, where N(u) is the open neighborhood of u. The weight of a [k]-RDF is the value Σv∈Vf(v). The minimum weight of a [k]-RDF is called the [k]-Roman domination number γ[kR](G) of G. In this paper, we establish sharp upper and lower bounds on γ[4R](T) for nontrivial trees T and characterize extremal trees.

The paper studies the connectivity properties of facet graphs of simplicial complexes of combinatorial interest. In particular, it is shown that the facet graphs of d-cycles, d-hypertrees and d-hypercuts are, respectively, (d +1)-, d-and (n − d − 1)-vertex-connected. It is also shown that the facet graph of a d-cycle cannot be split into more than s connected components by removing at most s vertices. In addition, the paper discusses various related issues, as well as an extension to cell-complexes.

A uniform attachment graph (with parameter $k$), denoted $G_{n,k}$ in the paper, is a random graph on the vertex set $[n]$, where each vertex $v$ makes $k$ selections from $[v-1]$ uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well-studied random graphs: $k$-out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of $G_{n,k}$ to show that the conductance of $G_{n,k}$ is of order $(\log n)^{-1}$. We also study the bootstrap percolation on $G_{n,k}$, where, each vertex is either initially infected with probability $p$, independently of others, or gets infected later as a result of having $r$ infected neighbors at some point. We show that, for $2\le r\le k-1$, if $p\ll (\log n)^{-r/(r-1)}$, then, with probability approaching 1, the process ends before all vertices get infected. On the other hand, if $p\ge \omega(\log n)^{-r/(r-1)}$, where $\omega$ is a certain very slowly growing function, then all the vertices get infected with probability approaching 1.

Let P be a Borel probability measure on ℝ generated by an infinite system of similarity mappings {Sj : j ∈ ℕ} such that $$P=\Sigma_{j=1}^{\infty}\frac{1}{2^{j}}P\circ{S}_j^{-1}$$ , where for each j ∈ ℕ and x ∈ ℝ, $$S_j(x)=\frac{1}{3^j}x+1-\frac{1}{3^{j-1}}$$ . Then, the support of P is the dyadic Cantor set C generated by the similarity mappings f1, f2 : ℝ → ℝ such that f1(x) = 1/3x and f2(x) = 1/3x+ 2/3 for all x ∈ ℝ. In this paper, using the infinite system of similarity mappings {Sj : j ∈ ℕ} associated with the probability vector $$(\frac{1}{2},\frac{1}{{{2^2}}},...)$$ , for all n ∈ ℕ, we determine the optimal sets of n-means and the nth quantization errors for the infinite self-similar measure P. The technique obtained in this paper can be utilized to determine the optimal sets of n-means and the nth quantization errors for more general infinite self-similar measures.

In [BGLM] and [GLNP] it was conjectured that if $H$ is a simple Lie group of real rank at least 2, then the number of conjugacy classes of (arithmetic) lattices in $H$ of covolume at most $x$ is $x^{(\gamma(H)+o(1))\log x/\log\log x}$ where $\gamma(H)$ is an explicit constant computable from the (absolute) root system of $H$. In [BLu] we disproved this conjecture. In this paper we prove that for most groups $H$ the conjecture is actually true if we restrict to counting only non-uniform lattices., Comment: 23 pages, revised following referee's comments. Dedicated to Aner Shalev on his 60th birthday. This paper is related to our previous work arXiv:0905.1841 with which it shares some preliminaries

Recent studies of [Formula: see text]-groups of coclass [Formula: see text] concentrate on the coclass graph [Formula: see text]. While the detailed structure of [Formula: see text] is unknown, it is known that its general structure is dominated by the subgraph of ‘skeleton groups’. The original definition of these groups is technical, but some modifications for special cases have been used successfully in the literature. Given their importance, in this paper we define and investigate skeleton groups more rigorously. In particular, we study their isomorphism problem, which is a crucial step towards understanding the skeleton subgraph of [Formula: see text]. During our work we identified erroneous arguments for constructing isomorphisms in a proof of the 2013 paper on [Formula: see text]. We correct these errors here by proving the required results in a more general context.

In this paper we introduce a natural model for the realization space of a polytope up to projective equivalence which we call the slack realization space of the polytope. The model arises from the positive part of an algebraic variety determined by the slack ideal of the polytope. This is a saturated determinantal ideal that encodes the combinatorics of the polytope. We also derive a new model of the realization space of a polytope from the positive part of the variety of a related ideal. The slack ideal offers an effective computational framework for several classical questions about polytopes such as rational realizability, non-prescribability of faces, and realizability of combinatorial polytopes., Comment: The original arXiv submission of this paper has now been split into two parts; this paper describing the slack realization space of a polytope and applications of the slack ideal, and a second paper focussing on toric slack ideals and projective uniqueness

Kavut, Selçuk (Balikesir Author), Very recently, a class of cryptographically significant Boolean functions were constructed by Tang and Maitra [IEEE Trans. Inform. Theory, 64 ( 2018), pp. 393-402] by modifying the PSap class of bent functions. The basic ideas used in Tang-Maitra construction were derived from a modification of a subclass of bent functions which is defined over the finite field, and a concern was raised in the same paper whether the implementation of such functions will be as efficient as that of Maiorana-McFarland type bent functions. In this paper, we look at the concrete realization of such functions over a vector space and answer the question positively. The first part of this paper investigates how the finite field implementation of the functions can be viewed as simple truth tables. Next, we present a completely new construction that itself starts from Maiorana-McFarland bent functions which are straightforward concatenations of linear functions., National Natural Science Foundation of China - 61872435 61602394 Fundamental Research Funds for the Central Universities - 2682016CX113 2682018ZT25

Two permutations of $[n]=\{1,2 \ldots n\}$ are \textit{$k$-neighbor separated} if there are two elements that are neighbors in one of the permutations and that are separated by exactly $k-2$ other elements in the other permutation. Let the maximal number of pairwise $k$-neighbor separated permutations of $[n]$ be denoted by $P(n,k)$. In a previous paper, the authors have determined $P(n,3)$ for every $n$, answering a question of K\"orner, Messuti and Simonyi affirmatively. In this paper we prove that for every fixed positive integer $\ell $, $$P(n,2^\ell+1) = 2^{n-o(n)}. $$ We conjecture that for every fixed even $k$, $P(n,k)=2^{n-o(n)}$. We also show that this conjecture is asymptotically true in the following sense $$\lim_{k \rightarrow \infty} \lim_{n \rightarrow \infty} \sqrt[n]{P(n,k)}=2.$$ Finally, we show that for even $n$, $P(n,n)= 3n/2$.

A $(\beta,\epsilon)$-hopset for a weighted undirected $n$-vertex graph $G=(V,E)$ is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most $\beta$ edges, whose length is within $1+\epsilon$ of the shortest path. In her seminal paper, Cohen \cite[JACM 2000]{C00} introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various other settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen \cite{C00} devised efficient algorithms for constructing hopsets with {\em polylogarithmic} in $n$ number of hops. Her constructions remain the state-of-the--art since the publication of her paper in STOC'94, i.e., for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a {\em constant number of hops}. We also find efficient algorithms for hopsets in various computational settings, improving the best known constructions. Generally, our hopsets strictly outperform the hopsets of \cite{C00}, both in terms of their parameters, and in terms of the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from $s$ sources. Our results improve the running time for this problem in the parallel, distributed and streaming models, for a vast range of $s$.

In 1998, R. Downey in his review paper outlined a research agenda for the study and description of sufficient conditions for computable representability of linear orderings, namely, the problem of describing order properties P such that, for any low linear ordering Limplies that, the feasibility of the condition P(L) implies that L has a computable presentation. This paper is a part of the research program initiated by R. Downey. It is shown in the paper that any low linear ordering whose factor order (in other words, condensation) is η (the order type of naturally ordered natural numbers) has a computable presentation via a 0—computable isomorphism if this ordering does not contain a strongly η-like infinite interval. A countable linear ordering is said to be strongly η-like if there exists some natural number k such that each maximal block of the ordering is of cardinality no more than k. It is also proved that the above result does not hold for a 0—computable isomorphism instead of the 0—computable one. Namely, we construct a low linear ordering L with condensation η and without strongly η-like infinite interval so that L has no computable presentation via a 0— computable isomorphism.

With generating function and structural analysis, this paper presents the subtree generating functions and the subtree number index of generalized book graphs, generalized fan graphs, and generalized wheel graphs, respectively. As an application, this paper also briefly studies the subtree number index and the asymptotic properties of the subtree densities in regular book graphs, regular fan graphs, and regular wheel graphs. The results provide the basis for studying novel structural properties of the graphs generated by generalized book graphs, fan graphs, and wheel graphs from the perspective of the subtree number index.

This paper introduces a general approach to the idea of protection of graphs, which encompasses the known variants of secure domination and introduces new ones. Specifically, we introduce the study of secure w-domination in graphs, where w=(w0,w1,⋯,wl) is a vector of nonnegative integers such that w0&ge, 1. The secure w-domination number is defined as follows. Let G be a graph and N(v) the open neighborhood of v&isin, V(G). We say that a function f:V(G)⟶{0,1,⋯,l} is a w-dominating function if f(N(v))=&sum, u&isin, N(v)f(u)&ge, wi for every vertex v with f(v)=i. The weight of f is defined to be &omega, (f)=&sum, v&isin, V(G)f(v). Given a w-dominating function f and any pair of adjacent vertices v,u&isin, V(G) with f(v)=0 and f(u)&gt, 0, the function fu&rarr, v is defined by fu&rarr, v(v)=1, fu&rarr, v(u)=f(u)&minus, 1 and fu&rarr, v(x)=f(x) for every x&isin, V(G)∖{u,v}. We say that a w-dominating function f is a secure w-dominating function if for every v with f(v)=0, there exists u&isin, N(v) such that f(u)&gt, 0 and fu&rarr, v is a w-dominating function as well. The secure w-domination number of G, denoted by &gamma, ws(G), is the minimum weight among all secure w-dominating functions. This paper provides fundamental results on &gamma, ws(G) and raises the challenge of conducting a detailed study of the topic.

Given a finite poset $\mathcal P$, we call a family $\mathcal F$ of subsets of $[n]$ $\mathcal P$-saturated if $\mathcal F$ does not contain an induced copy of $\mathcal P$, but adding any other set to $\mathcal F$ creates an induced copy of $\mathcal P$. The induced saturated number of $\mathcal P$, denoted by $\text{sat}^*(n,\mathcal P)$, is the size of the smallest $\mathcal P$-saturated family with ground set $[n]$. In this paper we are mainly interested in the four-point poset called the butterfly. Ferrara, Kay, Kramer, Martin, Reiniger, Smith and Sullivan showed that the saturation number for the butterfly lies between $\log_2{n}$ and $n^2$. We give a linear lower bound of $n+1$. We also prove some other results about the butterfly and the poset $\mathcal N$., Comment: 13 pages

The main purpose of this paper is to use the Hardy&ndash, Littlewood method to study the solvability of mixed powers of primes. To be specific, we consider the even integers represented as the sum of one prime, one square of prime, one cube of prime, and one biquadrate of prime. However, this representation can not be realized for all even integers. In this paper, we establish the exceptional set of this kind of representation and give an upper bound estimate.

We have studied the k-rainbow domination number of C n □ C m for k &ge, 4 (Gao et al. 2019), in which we present the 3-rainbow domination number of C n □ C m , which should be bounded above by the four-rainbow domination number of C n □ C m . Therefore, we give a rough bound on the 3-rainbow domination number of C n □ C m . In this paper, we focus on the 3-rainbow domination number of the Cartesian product of cycles, C n □ C m . A 3-rainbow dominating function (3RDF) f on a given graph G is a mapping from the vertex set to the power set of three colors { 1 , 2 , 3 } in such a way that every vertex that is assigned to the empty set has all three colors in its neighborhood. The weight of a 3RDF on G is the value &omega, ( f ) = &sum, v &isin, V ( G ) | f ( v ) | . The 3-rainbow domination number, &gamma, r 3 ( G ) , is the minimum weight among all weights of 3RDFs on G. In this paper, we determine exact values of the 3-rainbow domination number of C 3 □ C m and C 4 □ C m and present a tighter bound on the 3-rainbow domination number of C n □ C m for n &ge, 5 .

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollob\'as independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered' complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered' analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Kor\'andi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Kor\'andi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$., Comment: Reflected minor suggestions from reviewers

In this paper we introduce a general framework for the study of limits of relational structures in general and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as "tractable cases" of a general theory. As an outcome of this, we provide extensions of known results. We believe that this put these into next context and perspective. For example, we prove that the sparse--dense dichotomy exactly corresponds to random free graphons. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be "almost" studied component-wise. We also propose the structure of limits objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role of elementary brick these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of {\em modeling} we introduce here. Our example is also the first "intermediate class" with explicitly defined limit structures., Comment: added journal reference

Amdeberhan's conjectures on the enumeration, the average size, and the largest size of $(n,n+1)$-core partitions with distinct parts have motivated many research on this topic. Recently, Straub and Nath-Sellers obtained formulas for the numbers of $(n, dn-1)$ and $(n, dn+1)$-core partitions with distinct parts, respectively. Let $X_{s,t}$ be the size of a uniform random $(s,t)$-core partition with distinct parts when $s$ and $t$ are coprime to each other. Some explicit formulas for the $k$-th moments $\mathbb{E} [X_{n,n+1}^k]$ and $\mathbb{E} [X_{2n+1,2n+3}^k]$ were given by Zaleski and Zeilberger when $k$ is small. Zaleski also studied the expectation and higher moments of $X_{n,dn-1}$ and conjectured some polynomiality properties concerning them in arXiv:1702.05634. Motivated by the above works, we derive several polynomiality results and asymptotic formulas for the $k$-th moments of $X_{n,dn+1}$ and $X_{n,dn-1}$ in this paper, by studying the beta sets of core partitions. In particular, we show that these $k$-th moments are asymptotically some polynomials of n with degrees at most $2k$, when $d$ is given and $n$ tends to infinity. Moreover, when $d=1$, we derive that the $k$-th moment $\mathbb{E} [X_{n,n+1}^k]$ of $X_{n,n+1}$ is asymptotically equal to $\left(n^2/10\right)^k$ when $n$ tends to infinity. The explicit formulas for the expectations $\mathbb{E} [X_{n,dn+1}]$ and $\mathbb{E} [X_{n,dn-1}]$ are also given. The $(n,dn-1)$-core case in our results proves several conjectures of Zaleski on the polynomiality of the expectation and higher moments of $X_{n,dn-1}$., Comment: This paper has been accepted for publication in SCIENCE CHINA Mathematics

A topological invariant is a numerical parameter associated with molecular graph and plays an imperative role in the study and analysis of quantitative structure activity/property relationships (QSAR/QSPR). The correlation between the entire π-electron energy and the structure of a molecular graph was explored and understood by the first Zagreb index. Recently, Liu et al. (2019) calculated the first general Zagreb index of the F-sum graphs. In the same paper, they also proposed the open problem to compute the general Randić index RαΓ=∑uv∈EΓdΓu×dΓvα of the F-sum graphs, where α∈R and dΓu denote the valency of the vertex u in the molecular graph Γ. Aim of this paper is to compute the lower and upper bounds of the general Randić index for the F-sum graphs when α∈N. We present numerous examples to support and check the reliability as well as validity of our bounds. Furthermore, the results acquired are the generalization of the results offered by Deng et al. (2016), who studied the general Randić index for exactly α=1.

Given a graph $G$, a probability measure $\mu$ on the subsets of the edge set of $G$ is said to be $1$-independent if events determined by edge sets that are at graph distance at least $1$ apart in $G$ are independent. Call such a probability measure a $1$-ipm on $G$, and denote by $\mathbf{G}_{\mu}$ the associated random spanning subgraph of $G$. Let $\mathcal{M}_{1,\geqslant p}(G)$ (resp. $\mathcal{M}_{1,\leqslant p}(G)$) denote the collection of $1$-ipms $\mu$ on $G$ for which each edge is included in $\mathbf{G}_{\mu}$ with probability at least $p$ (resp. at most $p$). Let $\mathbb{Z}^2$ denote the square integer lattice. Balister and Bollob\'as raised the question of determining the critical value $p_{\star}=p_{1,c}(\mathbb{Z}^2)$ such that for all $p>p_{\star}$ and all $\mu \in \mathcal{M}_{1,\geqslant p}(\mathbb{Z}^2)$, $\left(\mathbf{\mathbb{Z}^2}\right)_{\mu}$ almost surely contains an infinite component. This can be thought of as asking for a $1$-independent analogue of the celebrated Harris--Kesten theorem. In this paper we investigate both this problem and connectivity problems for $1$-ipms more generally. We give two lower bounds on $p_{\star}$ that significantly improve on the previous bounds. Furthermore, motivated by the Russo--Seymour--Welsh lemmas, we define a $1$-independent critical probability for long paths and determine its value for the line and ladder lattices. Finally, for finite graphs $G$ we study $f_{1,G}(p)$ (respectively $F_{1,G}(p)$), the infimum (resp. supremum) over all $\mu\in \mathcal{M}_{1,\geqslant p}(G)$ (resp. all $\mu \in \mathcal{M}_{1,\leqslant p}(G)$) of the probability that $\mathbf{G}_{\mu}$ is connected. We determine $f_{1,G}(p)$ and $F_{1,G}(p)$ exactly when $G$ is a path, a complete graph and a cycle of length at most $5$. Many new problems arise from our work, which are discussed in the final section of the paper., Comment: 43 pages, 3 figures

A cut $\varepsilon$-sparsifier of a weighted graph $G$ is a re-weighted subgraph of $G$ of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $\varepsilon$. Since their introduction by Bencz\'ur and Karger [STOC'96], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA'17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains., Comment: Full version of a STACS'19 paper

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ1 equal to a3. For a Shilla graph, let us put a = a3 and b = k/a. It is proved in this paper that a Shilla graph with b2 = c2 and noninteger eigenvalues has the following intersection array: $$\left\{ {\frac{{{b^2}\left( {b - 1} \right)}}{2},\frac{{\left( {b - 1} \right)\left( {{b^2} - b + 2} \right)}}{2},\frac{{b\left( {b - 1} \right)}}{4};1,\frac{{b\left( {b - 1} \right)}}{4},\frac{{b{{\left( {b - 1} \right)}^2}}}{2}} \right\}$$ If Γ is a Q-polynomial Shilla graph with b2 = c2 and b = 2r, then the graph Γ has intersection array $$\left\{ {2tr\left( {2r + 1} \right),\left( {2r + 1} \right)\left( {2rt + t + 1} \right),r\left( {r + t} \right);1,r\left( {r + t} \right),t\left( {4{r^2} - 1} \right)} \right\}$$ and, for any vertex u in Γ, the subgraph Γ3(u) is an antipodal distance-regular graph with intersection array $$\left\{ {t\left( {2r + 1} \right),\left( {2r - 1} \right)\left( {t + 1} \right),1;1,t + 1,t\left( {2r + 1} \right)} \right\}$$ The Shilla graphs with b2 = c2 and b = 4 are also classified in the paper.

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the graph. Suppose also that $r < m$, where $2m$ is the average degree. We determine a critical function $a_c(t)$ such that when $a(t) \gg a_c(t)$, complete infection occurs with high probability as $t \rightarrow \infty$, but when $a(t) \ll a_c (t)$, then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to $a(t)$., This paper is significantly different to the previous version

For a sequence of integers $\{a(x)\}_{x \geq 1}$ we show that the distribution of the pair correlations of the fractional parts of $\{ \langle \alpha a(x) \rangle \}_{x \geq 1}$ is asymptotically Poissonian for almost all $\alpha$ if the additive energy of truncations of the sequence has a power savings improvement over the trivial estimate. Furthermore, we give an estimate for the Hausdorff dimension of the exceptional set as a function of the density of the sequence and the power savings in the energy estimate. A consequence of these results is that the Hausdorff dimension of the set of $\alpha$ such that $\{\langle \alpha x^d \rangle\}$ fails to have Poissonian pair correlation is at most $\frac{d+2}{d+3} < 1$. This strengthens a result of Rudnick and Sarnak which states that the exceptional set has zero Lebesgue measure. On the other hand, classical examples imply that the exceptional set has Hausdorff dimension at least $\frac{2}{d+1}$. An appendix by Jean Bourgain was added after the first version of this paper was written. In this appendix two problems raised in the paper are solved., Comment: 22 pages. Version 2 contains an appendix by Jean Bourgain. Version 3 with corrections suggested by the referee. The paper will be published in the Israel Journal of Mathematics

Let G be a graph of order n . A subset S of V ( G ) is a dominating set of G if every vertex in V ( G ) ⧹ S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ∑ i = γ ( G ) n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i , and γ ( G ) is the size of a smallest dominating set of G , called the domination number of G . We say two graphs G and H are dominating equivalent if D ( G , x ) = D ( H , x ) . A graph G is said to be dominating unique , or simply D -unique, if D ( H , x ) = D ( G , x ) implies that H ≅ G . The goal of this paper is to find a new approach to determine the dominating uniqueness of graphs. In this paper, we define a new graph polynomial, called star polynomial, and introduced an analogy notion of star uniqueness of graphs. As an application, if G is a graph without isolated vertices, we show that a graph G is star unique if and only if G ‾ ∨ K m is dominating unique for each m ⩾ 0 . As a by-product, the dominating uniqueness of many families of dense graphs is also determined.

In this paper we investigate Ramanujan’s inequality concerning the prime counting function, asserting that π ( x 2 ) < e x log x π ( x e ) \pi \left( {{x^2}} \right) < {{ex} \over {\log x}}\pi \left( {{x \over e}} \right) for x sufficiently large. First, we study its sharpness by giving full asymptotic expansions of its left and right hand sides expressions. Then, we discuss the structure of Ramanujan’s inequality, by replacing the factor x log x {x \over {\log x}} on its right hand side by the factor x log x - h {x \over {\log x - h}} for a given h, and by replacing the numerical factor e by a given positive α. Finally, we introduce and study inequalities analogous to Ramanujan’s inequality.

In 1874, Franz Mertens proved the so-called Mertens’ theorem, and in 1974, Kenneth S. Williams showed Mertens’ theorem associated with a character. In a previous paper, we presented a graph-theoretic analogue to Williams’ theorem. In this paper, we generalize our previous work in the sense that a character is extended to a representation. To our knowledge, a number-theoretic analogue to our result is not yet known. So, we expect that, by using our methods, it can be proven in the future.

In this paper, we examine embeddings of alternating and symmetric groups into almost simple groups of exceptional type. In particular, we prove that if the alternating or symmetric group has degree equal to 5, or 8 or more, then it cannot appear as the maximal subgroup of any almost simple exceptional group of Lie type. Furthermore, in the remaining open cases of degrees 6 and 7 we give considerable information about the possible embeddings. Note that no maximal alternating or symmetric subgroups are known in the remaining cases. This is the first in a sequence of papers aiming to substantially improve the state of knowledge about the maximal subgroups of exceptional groups of Lie type.

The aim of the paper is to present the binomial transformation formulae of Fibonacci numbers scaled by complex multipliers. Many of these new and nontrivial relations follow from the fundamental properties of the so-called delta-Fibonacci numbers defined by Wituła and Słota. The paper contains some original relations connecting the values of delta-Fibonacci numbers with the respective values of Chebyshev polynomials of the first and second kind.

This paper studies a higher dimensional generalization of Frieze's $\zeta(3)$-limit theorem in the Erd\"os-R\'enyi graph process. Frieze's theorem states that the expected weight of the minimum spanning tree converges to $\zeta(3)$ as the number of vertices goes to infinity. In this paper, we study the $d$-Linial-Meshulam process as a model for random simplicial complexes, where $d=1$ corresponds to the Erd\"os-R\'enyi graph process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in $O(n^{d-1})$., Comment: 24 pages

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

Let D ∈ ℤ and let C D be the set of all monic cubic polynomials x 3 + ax 2 + bx + c ∈ ℤ[x] with the discriminant equal to D. Along the line of our preceding papers, the following Theorem has been proved: If D is square-free and 3 ∤ h(−3D) where h(−3D) is the class number of Q ( − 3 D ) , $\mathbb Q(\sqrt {-3D}),$ then all polynomials in C D have the same type of factorization over the Galois field 𝔽 p where p is a prime, p > 3. In this paper, we prove the validity of the above implication also for primes 2 and 3.

The study of the global structure of ultrafilters on the natural numbers with respect to the quasi-orders of Rudin-Keisler and Rudin-Blass reducibility was initiated in the 1970s by Blass, Keisler, Kunen, and Rudin. In a 1973 paper Blass studied the special class of P-points under the quasi-ordering of Rudin-Keisler reducibility. He asked what partially ordered sets can be embedded into the P-points when the P-points are equipped with this ordering. This question is of most interest under some hypothesis that guarantees the existence of many P-points, such as Martin’s axiom for σ \sigma -centered posets. In his 1973 paper he showed under this assumption that both ω 1 {\omega }_{1} and the reals can be embedded. Analogous results were obtained later for the coarser notion of Tukey reducibility. We prove in this paper that Martin’s axiom for σ \sigma -centered posets implies that the Boolean algebra P ( ω ) / FIN \mathcal {P}(\omega ) / \operatorname {FIN} equipped with its natural partial order can be embedded into the P-points both under Rudin-Keisler and Tukey reducibility. Consequently, the continuum hypothesis implies that every partial order of size at most continuum embeds into the P-points under both notions of reducibility.

This paper continues a recent resurgence of interest in combinatorial properties of a poset that are associated with graph properties of its cover graph and order diagram. The following two theorems appearing in a 1977 paper of Trotter and Moore have played important roles in motivating this more modern research: (1) The dimension of a poset is at most 3 when its cover graph is at tree; (2) The dimension of a poset is at most 3 when the poset has a zero and its order diagram is planar. Although the underlying ideas lay dormant for more than 30 years, the first of these two results has become the base case for recent results bounding the dimension of a poset in terms of (a) the tree-width of its cover graph, and (b) the maximum dimension of its blocks. The second result is the base case for bounding the dimension of a planar poset in terms of the number of minimal elements. Continuing with this line of research, we show that every poset whose cover graph is a tree is a circle order, i.e., it has a representation as a family of circular disks in the Euclidean plane partially ordered by inclusion.

This is the last paper of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For every $\alpha>0$ there exists a number~$k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first two papers of this series, we decomposed the host graph $G$, and found a suitable combinatorial structure inside the decomposition. In the third paper, we refined this structure, and proved that any graph satisfying the conditions of the above approximate version of the Loebl-Komlos-Sos Conjecture contains one of ten specific configurations. In this paper we embed the tree $T$ in each of the ten configurations., Comment: 81 pages, 12 figures. A fix reflecting the change of Preconfiguration Clubs in Paper III, additional small changes

This is the third of a series of four papers in which we prove the following relaxation of the Loebl-Komlos-Sos Conjecture: For every $\alpha>0$ there exists a number $k_0$ such that for every $k>k_0$ every $n$-vertex graph $G$ with at least $(\frac12+\alpha)n$ vertices of degree at least $(1+\alpha)k$ contains each tree $T$ of order $k$ as a subgraph. In the first paper of the series, we gave a decomposition of the graph $G$ into several parts of different characteristics. In the second paper, we found a combinatorial structure inside the decomposition. In this paper, we will give a refinement of this structure. In the forthcoming fourth paper, the refined structure will be used for embedding the tree $T$., Comment: 59 pages, 4 figures; further comments by a referee incorporated; this includes a subtle but important fix to Lemma 5.1; as a consequence, Preconfiguration Clubs was changed