Abstract. We study the extremal number for paths in [Formula: see text]-uniform hypergraphs where two consecutive edges of the path intersect alternately in sets of sizes [Formula: see text] and [Formula: see text] with [Formula: see text] and all other pairs of edges have empty intersection. Our main result, which is about hypergraphs that are blowups of trees, determines asymptotically the extremal number of these [Formula: see text]-paths that have an odd number of edges or that have an even number of edges and [Formula: see text]. This generalizes the Erdős–Gallai theorem for graphs, which is the case of [Formula: see text]. Our proof method involves a novel twist on Katona’s permutation method, where we partition the underlying hypergraph into two parts, one of which is very small. We also find the asymptotics of the extremal number for the [Formula: see text]-path of length 4 using the different [Formula: see text]-systems method.

The Reconstruction Conjecture of Ulam asserts that, for n ≥ 3, every n-vertex graph is determined by the multiset of its induced subgraphs with n-1 vertices. The conjecture is known to hold for various special classes of graphs but remains wide open. We survey results on the more general conjecture by Kelly from 1957 that for every positive integerlthere exists Ml(with M1=3) such that when n ≥ Mlevery n-vertex graph is determined by the multiset of its induced subgraphs with n-lvertices.

Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values.

An $r$-uniform hypergraph is a tight $r$-tree if its edges can be ordered so that every edge $e$ contains a vertex $v$ that does not belong to any preceding edge and the set $e-v$ lies in some preceding edge. A conjecture of Kalai personal communication published in Frankl and Füredi, J. Combin. Theory Ser. A, 45 (1987), pp. 226--262, generalizing the Erdös--Sós conjecture for trees, asserts that if $T$ is a tight $r$-tree with $t$ edges and $G$ is an $n$-vertex $r$-uniform hypergraph containing no copy of $T$, then $G$ has at most $\frac{t-1}{r}\binom{n}{r-1}$ edges. A trunk $T'$ of a tight $r$-tree $T$ is a tight subtree such that every edge of $T-T'$ has $r-1$ vertices in some edge of $T'$ and a vertex outside $T'$. For $r\ge 3$, the only nontrivial family of tight $r$-trees for which this conjecture has been proved is the family of $r$-trees with trunk size one in J. Combin. Theory Ser. A, 45 (1987), pp. 226--262. Our main result is an asymptotic version of Kalai's conjecture for all tight trees $T$ of bounded trunk size. This follows from our upper bound on the size of a $T$-free $r$-uniform hypergraph $G$ in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight $r$-trees with at most four edges. In particular, for 3-uniform hypergraphs, our result on the tight path of length $4$ implies the intersection shadow theorem of Katona Acta Math. Acad. Sci. Hungar., 15 (1964), pp. 329--337.

The expansion $G^+$ of a graph $G$ is the 3-uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a new vertex disjoint from $V(G)$ such that distinct edges are enlarged by distinct vertices. Let ${ex}_3(n,F)$ denote the maximum number of edges in a 3-uniform hypergraph with $n$ vertices not containing any copy of a 3-uniform hypergraph $F$. The study of ${ex}_3(n,G^+)$ includes some well-researched problems, including the case that $F$ consists of $k$ disjoint edges, $G$ is a triangle, $G$ is a path or cycle, and $G$ is a tree. In this paper we initiate a broader study of the behavior of ${ex}_3(n,G^+)$. Specifically, we show $ {ex}_3(n,K_{s,t}^+) = \Theta(n^{3 - 3/s})$ whenever $t > (s - 1)!$ and $s \geq 3$. One of the main open problems is to determine for which graphs $G$ the quantity ${ex}_3(n,G^+)$ is quadratic in $n$. We show that this occurs when $G$ is any bipartite graph with Turán number $o(n^{\varphi})$ where $\varphi = \frac{1 + \sqrt{5}}{2}$, and in particular this shows ${ex}_3(n,G^+) = O(n^2)$ when $G$ is the three-dimensional cube graph.

We introduce and study adapted list coloring of graphs and hypergraphs. This is a generalization of ordinary list coloring and adapted coloring, and has more applications than these. We prove that the upper bounds on the adaptable choosability of graphs and uniform hypergraphs in terms of maximum degree are sufficiently stronger than those on the ordinary choosability, while the bounds in terms of degeneracy are the same. We also characterize simple graphs with adaptable choosability 2.

Given a fixed multigraph H, possibly containing loops, with $V(H) = \{h_1,\ldots,h_m\}$, we say that a graph G is H‐linked if for every choice of m vertices $v_1,\ldots,v_m$ in G, there exists a subdivision of H in G such that $v_i$ is the branch vertex representing $h_i$ (for all i). This generalizes the concept of k‐linked graphs (as well as a number of other well‐known path or cycle properties). In this paper we determine a sharp lower bound on $\delta(G)$ (which depends upon H) such that each graph G on at least $10(|V(H)|+|E(H)|)$ vertices satisfying this bound is H‐linked.

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. A d-degenerate graph is a graph G in which every subgraph has a vertex with degree at most d. A star S m with m rays is an example of a 1-degenerate graph with maximum degree m that needs at least 1+m/2 colors for an equitable coloring. Our main result is that every n-vertex d-degenerate graph G with maximum degree at most n/15 can be equitably k-colored for each $k \ge 16d$. The proof of this bound is constructive. We extend the algorithm implied in the proof to an O(d)-factor approximation algorithm for equitable coloring of an arbitraryd -degenerate graph. Among the implications of this result is an O(1)-factor approximation algorithm for equitable coloring of planar graphs with fewest colors. A variation of equitable coloring (equitable partitions) is also discussed.

Let G be a connected graph with maximum degree k (other than a complete graph or odd cycle), let W be a precolored set of vertices in G inducing a subgraph F, and let D be the minimum distance in G between components of F. If the components of F are complete graphs and $D\ge 8$ (for $k\ge 4$) or $D\ge 10$ (for k = 3), then every proper k-coloring of F extends to a proper k-coloring of G. If the components of F are single vertices and $Dge 8$, and the vertices outside W are assigned color lists of size k, then every k-coloring of F extends to a proper coloring of G with the color on each vertex chosen from its list. These results are sharp.