Search

One of the major problems in combinatorics is to determine the number of $r$-uniform hypergraphs ($r$-graphs) on $n$ vertices which are free of certain forbidden structures. This problem dates back to the work of Erd\H{o}s, Kleitman and Rothschild, who showed that the number of $K_r$-free graphs on $n$ vertices is $2^{\text{ex}(n,K_r)+o(n^2)}$. Their work was later extended to forbidding graphs as induced subgraphs by Pr\"omel and Steger. Here, we consider one of the most basic counting problems for $3$-graphs. Let $E_1$ be the $3$-graph with $4$ vertices and $1$ edge. What is the number of induced $\{K_4^3,E_1\}$-free $3$-graphs on $n$ vertices? We show that the number of such $3$-graphs is of order $n^{\Theta(n^2)}$. More generally, we determine asymptotically the number of induced $\mathcal{F}$-free $3$-graphs on $n$ vertices for all families $\mathcal{F}$ of $3$-graphs on $4$ vertices. We also provide upper bounds on the number of $r$-graphs on $n$ vertices which do not induce $i \in L$ edges on any set of $k$ vertices, where $L \subseteq \big \{0,1,\ldots,\binom{k}{r} \big\}$ is a list which does not contain $3$ consecutive integers in its complement. Our bounds are best possible up to a constant multiplicative factor in the exponent when $k = r+1$. The main tool behind our proof is counting the solutions of a constraint satisfaction problem., Comment: 18 pages

A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $c\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvo\v{r}\'ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masa\v{r}\'ik and show that planar graphs without $K_4^-$ are $\varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $\varepsilon$-flexible for list size $5$., Comment: 18 pages, 4 figures

An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path P n to be the monotone increasing path with n edges. The ordered size Ramsey number r ( P r , P s ) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of P r or a blue copy of P s . For 2 ≤ r ≤ s , we show 1 8 r 2 s ≤ r ( P r , P s ) ≤ C r 2 s ( log s ) 3 , where C > 0 is an absolute constant. This problem is motivated by the recent results of Bucic et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.

The Erdős–Szekeres Theorem stated in terms of graphs says that any red–blue coloring of the edges of the ordered complete graph K r s + 1 contains a red copy of the monotone increasing path with r edges or a blue copy of the monotone increasing path with s edges. Although r s + 1 is the minimum number of vertices needed for this result, not all edges of K r s + 1 are necessary. We characterize the subgraphs of K r s + 1 with this coloring property as follows: they are exactly the subgraphs that contain all the edges of a graph we call the circus tent graph C T ( r , s ) . Additionally, we use similar proof techniques to improve upon the bounds on the online ordered size Ramsey number of a path given by Perez-Gimenez, Pralat, and West.