Abstract Let X be an n-element point set in the k-dimensional unit cube $$[0,1]^k$$ [ 0 , 1 ] k where $$k \ge 2$$ k ≥ 2 . According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour) $$x_1, x_2, \ldots , x_n$$ x 1 , x 2 , … , x n through the n points, such that $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ∑ i = 1 n | x i - x i + 1 | k 1 / k ≤ c k , where $$|x-y|$$ | x - y | is the Euclidean distance between x and y, and $$c_k$$ c k is an absolute constant that depends only on k, where $$x_{n+1} \equiv x_1$$ x n + 1 ≡ x 1 . From the other direction, for every $$k \ge 2$$ k ≥ 2 and $$n \ge 2$$ n ≥ 2 , there exist n points in $$[0,1]^k$$ [ 0 , 1 ] k , such that their shortest tour satisfies $$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ∑ i = 1 n | x i - x i + 1 | k 1 / k = 2 1 / k · k . For the plane, the best constant is

Abstract. We address a problem which is a generalization of Turán-type problems recently introduced by Imolay, Karl, Nagy, and Váli. Let [Formula: see text] be a fixed graph and let [Formula: see text] be the union of [Formula: see text] edge-disjoint copies of [Formula: see text], namely [Formula: see text], where each [Formula: see text] is isomorphic to a fixed graph [Formula: see text] and [Formula: see text] for all [Formula: see text]. We call a subgraph [Formula: see text] multicolored if [Formula: see text] and [Formula: see text] share at most one edge for all [Formula: see text]. Define [Formula: see text] to be the maximum value [Formula: see text] such that there exists [Formula: see text] on [Formula: see text] vertices without a multicolored copy of [Formula: see text]. We show that [Formula: see text] and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.

Abstract. A result of Balogh et al. yields the minimum degree threshold that ensures a 2-colored graph contains a perfect matching of significant color-bias (i.e., a perfect matching that contains significantly more than half of its edges in one color). In this note we prove an analogous result for perfect matchings in [Formula: see text]-uniform hypergraphs. More precisely, for each [Formula: see text] and [Formula: see text] we determine the minimum [Formula: see text]-degree threshold for forcing a perfect matching of significant color-bias in an [Formula: see text]-colored [Formula: see text]-uniform hypergraph.

The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.

We prove that 1−o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n → ∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003.

Abstract. Denote by [Formula: see text] the smallest eigenvalue of the signless Laplacian matrix of an [Formula: see text]-vertex graph [Formula: see text]. Brandt conjectured in 1997 that for regular triangle-free graphs [Formula: see text]. We prove a stronger result: If [Formula: see text] is a triangle-free graph, then [Formula: see text]. Brandt’s conjecture is a subproblem of two famous conjectures of Erdős: (1) Sparse-half-conjecture: Every [Formula: see text]-vertex triangle-free graph has a subset of vertices of size [Formula: see text] spanning at most [Formula: see text] edges. (2) Every [Formula: see text]-vertex triangle-free graph can be made bipartite by removing at most [Formula: see text] edges. In our proof we use linear algebraic methods to upper bound [Formula: see text] by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.

For given posets $P$ and $Q$ and an integer $n$, the generalized Turán problem for posets asks for the maximum number of copies of $Q$ in a $P$-free subset of the $n$-dimensional Boolean lattice, $2^{[n]}$. In this paper, among other results, we show the following: (i) For every $n\geq 5$, the maximum number of 2-chains in a butterfly-free subfamily of $2^{[n]}$ is $\lceil\frac{n}{2} \rceil\binom{n}{\lfloor n/2\rfloor}$. (ii) For every fixed $s$, $t$ and $k$, a $K_{s,t}$-free family in $2^{[n]}$ has $O (n\binom{n}{\lfloor n/2\rfloor})$ $k$-chains. (iii) For every $n\geq 3$, the maximum number of $2$-chains in an ${N}$-free family is $\binom{n}{\lfloor n/2\rfloor}$, where ${N}$ is a poset on 4 distinct elements $\{p_1,p_2,q_1,q_2\}$ for which $p_1 < q_1$, $p_2 < q_1$ and $p_2 < q_2$. (iv) We also prove exact results for the maximum number of 2-chains in a family that has no 5-path and asymptotic estimates for the number of 2-chains in a family with no 6-path.

Let $\mathcal{H}$ be an $r$-uniform hypergraph. The minimum positive co-degree of $\mathcal{H}$, denoted by $\delta_{r-1}^+(\mathcal{H})$, is the minimum $k$ such that if $S$ is an $(r-1)$-set contained in a hyperedge of $\mathcal{H}$, then $S$ is contained in at least $k$ hyperedges of $\mathcal{H}$. For $r\geq k$ fixed and $n$ sufficiently large, we determine the maximum possible size of an intersecting $r$-uniform $n$-vertex hypergraph with minimum positive co-degree $\delta_{r-1}^+(\mathcal{H}) \geq k$ and characterize the unique hypergraph attaining this maximum. This generalizes the Erd\Hos--Ko--Rado theorem which corresponds to the case $k=1$. Our proof is based on the delta-system method.

An edge coloring of a graph $G$ is a Gallai coloring if it contains no rainbow triangle. We show that the number of Gallai $r$-colorings of $K_n$ is $(\binom{r}{2}+o(1))2^{\binom{n}{2}}$. This result indicates that almost all Gallai $r$-colorings of $K_n$ use only 2 colors. We also study the extremal behavior of Gallai $r$-colorings among all $n$-vertex graphs. We prove that the complete graph $K_n$ admits the largest number of Gallai 3-colorings among all $n$-vertex graphs when $n$ is sufficiently large, while for $r\geq 4$, it is the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$. Our main approach is based on the hypergraph container method, developed independently by Balogh, Morris, and Samotij as well as by Saxton and Thomason, together with some stability results.

Borrowing László Székely's lively expression, we show that Hill's conjecture is “asymptotically at least $98.5\%$ true.” This long-standing conjecture states that the crossing number cr$(K_n)$ of the complete graph $K_n$ is $H(n) := \frac{1}{4}{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{n-1}{2}\rfloor}{\lfloor\frac{n-2}{2}\rfloor}{\lfloor\frac{n-3}{2}\rfloor}$ for all $n\ge 3$. This has been verified only for $n\le 12$. Using the flag algebra framework, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large $n$, cr$(K_n) > 0.905\, H(n)$. Also using this framework, we prove that asymptotically cr$(K_n)$ is at least $0.985\, H(n)$. We also show that the spherical geodesic crossing number of $K_n$ is asymptotically at least $0.996\, H(n)$.

Alon, Balogh, Keevash, and Sudakov proved that the $(k-1)$-partite Turán graph maximizes the number of distinct $r$-edge-colorings with no monochromatic $K_k$ for all fixed $k$ and $r=2,3$, among all $n$-vertex graphs. In this paper, we determine this function asymptotically for $r=2$ among $n$-vertex graphs with a sublinear independence number. Somewhat surprisingly, unlike Alon, Balog, Keevash, and Sudakov's result, the extremal construction from Ramsey--Turán theory, as a natural candidate, does not maximize the number of distinct edge-colorings with no monochromatic cliques among all graphs with a sublinear independence number, even in the 2-colored case. In the second problem, we determine the maximum number of triangles asymptotically in an $n$-vertex $K_k$-free graph $G$ with $\alpha(G)=o(n)$. The extremal graphs have a similar structure to the extremal graphs for the classical Ramsey--Turán problem, i.e., when the number of edges is maximized.

In the influential paper in which he proved that every graph with $m$ edges can be embedded in a book with $O({m}^{1/2})$ pages, Malitz proved the existence of $d$-regular $n$-vertex graphs that require $\Omega(\sqrt{d}n^{\frac{1}{2}-\frac{1}{d}})$ pages. In view of the $O({m}^{1/2})$ bound, this last bound is tight when $d > \log{n}$, and Malitz asked if it is also tight when $d< \log{n}$. We answer negatively to this question by showing that there exist $d$-regular graphs that require $\Omega(n^{\frac{1}{2}-\frac{1}{2(d-1)}})$ pages. In addition, we show that the bound $O({m}^{1/2})$ is not tight either for most $d$-regular graphs by proving that for each fixed $d$, with high probability the random $d$-regular graph can be embedded in $o({m}^{1/2})$ pages. We also give a simpler proof of Malitz's $O({m}^{1/2})$ bound and improve the proportionality constant.

The Gyárfás tree packing conjecture states that any set of $n-1$ trees $T_{1},T_{2},\dots, T_{n-1}$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ (for $n$ large enough). We show that $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_{n+1}$ (for $n$ large enough). We also prove that any set of $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that no tree is a star and $T_i$ has $n-i+1$ vertices packs into $K_{n}$ (for $n$ large enough). Finally, we prove that $t=\frac{1}{4}n^{1/3}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ as long as each tree has maximum degree at least $2n^{2/3}$ (for $n$ large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlós, Sárközy, and Szemerédi [Combin. Probab. Comput., 10 (2001), pp. 397--416].

Let $B_i^{(k)}$ be the $k$-uniform hypergraph whose vertex set is of the form $S\cup T$, where $|S|=i$, $|T|=k-1$, and $S\cap T=\emptyset$, and whose edges are the $k$-subsets of $S\cup T$ that contain either $S$ or $T$. We derive upper and lower bounds for the Turán density of $B_i^{(k)}$ that are close to each other as $k\to\infty$. We also obtain asymptotically tight bounds for the Turán density of several other infinite families of hypergraphs. The constructions that imply the lower bounds are derived from elementary number theory by probabilistic arguments, and the upper bounds follow from some results of de Caen, Sidorenko, and Keevash.

A graph is called H-free if it contains no copy of H. Let $\mathrm{ex}(n,H)$ denote the Turán number for H, i.e., the maximum number of edges that an n-vertex H-free graph may have. An old result of Kleitman and Winston states that there are $2^{O(\mathrm{ex}(n,C_4))}$ $C_4$-free graphs on n vertices. Füredi showed that almost all $C_4$-free graphs of order n have at least $c\,\mathrm{ex}(n,C_4)$ edges for some positive constant c. We prove that there is a positive constant $\varepsilon$ such that almost all $C_4$-free graphs have at most $(1-\varepsilon)\,\mathrm{ex}(n,C_4)$ edges. This resolves a conjecture of Balogh, Bollobás, and Simonovits for the 4-cycle.

In the Avoider-Enforcer game on the complete graph $K_n$, the players (Avoider and Enforcer) each take an edge in turn. Given a graph property $\mathcal{P}$, Enforcer wins the game if Avoider's graph has the property $\mathcal{P}$. An important parameter is $\tau_E(\mathcal{P})$, the smallest integer t such that Enforcer can win the game against any opponent in t rounds. In this paper, let $\mathcal{F}$ be an arbitrary family of graphs and $\mathcal{P}$ be the property that a member of $\mathcal{F}$ is a subgraph or is an induced subgraph. We determine the asymptotic value of $\tau_E(\mathcal{P})$ when $\mathcal{F}$ contains no bipartite graph and establish that $\tau_E(\mathcal{P})=o(n^2)$ if $\mathcal{F}$ contains a bipartite graph. The proof uses the game of JumbleG and the Szemerédi regularity lemma.

The first-fit chromatic number of a graph is the number of colors needed in the worst case of a greedy coloring. It is also called the Grundy number, which is defined to be the maximum number of classes in an ordered partition of the vertex set of a graph G into independent sets $V_1, V_2, \dots, V_k$ so that for each $1\le i

Let $\ell$ be any positive integer, let n be a sufficiently large number, and let G be a graph on n vertices. Define, for any k, $\nu_k(G)= | \{ |E(H)| : H$ is an induced subgraph of G on k vertices$\} |$. We show that if there exists a k, $2\ell \leq k \leq n-2\ell$, such that $\nu_k(G) \le \ell$, then G has a complete or an empty subgraph on at least $n-\ell+1$ vertices and a homogeneous set of size at least $n-2\ell+2$. These results are sharp.

Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a √n x √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπr2/log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.

This paper concerns the design of a multiple description scalar quantization (MDSQ) system for two identical channels for an unbounded discrete information source. This translates to the combinatorial problem of finding an arrangement of the integers into the infinite plane square grid so that each row and each column contains exactly N numbers, such that the difference between any two numbers in the same row (or column) is at most d, with d to be minimized for a given N. The best previous lower and upper bounds on the lowest d were N/sup 2//3+O(N) and N/sup 2//2+O(N). We give new lower and upper bounds, both of the form 3N/sup 2//8+O(N). We also consider minimizing the maximal variance in any row or column and show that it must be at least N/sup 4//60+O(N/sup 3/), and that it does not have to be more than 3N/sup 4//160+O(N/sup 3/).

We show how to construct an arrangement of n lines having a monotone path of length O(n2-(d/vlog n)), where d>0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.