Balázs Patkós

The Kneser cube $$Kn_n$$ K n n has vertex set $$2^{[n]}$$ 2 [ n ] and two vertices $$F,F'$$ F , F ′ are joined by an edge if and only if $$F\cap F'=\emptyset $$ F ∩ F ′ = ∅ . For a fixed graph G , we are interested in the most number $$\textrm{vex}(n,G)$$ vex ( n , G ) of vertices of $$Kn_n$$ K n n that span a G -free subgraph in $$Kn_n$$ K n n . We show that the asymptotics of $$\textrm{vex}(n,G)$$ vex ( n , G ) is $$(1+o(1))2^{n-1}$$ ( 1 + o ( 1 ) ) 2 n - 1 for bipartite G and $$(1-o(1))2^n$$ ( 1 - o ( 1 ) ) 2 n for graphs with chromatic number at least 3. We also obtain results on the order of magnitude of $$2^{n-1}-\!\textrm{vex}(n,G)$$ 2 n - 1 - vex ( n , G ) and $$2^n-\!\textrm{vex}(n,G)$$ 2 n - vex ( n , G ) in these two cases. In the case of bipartite G , we relate this problem to instances of the forbidden subposet problem.

A family $\mathcal{G}$ of sets is a copy of a poset $(P,\leqslant)$ if $(\mathcal{G},\subseteq)$ is isomorphic to $(P,\leqslant)$. The forbidden subposet problem asks for determining $La^*(n,P)$, the maximum size of a family $\mathcal{F}\subseteq 2^{[n]}$ that does not contain any copy of $P$. We study the rainbow version of this problem: what is the maximum size $La_R^*(n,P)$ of a family $\mathcal{F}=\cup_{i=1}^mA^i$ such that all $A^i$ are antichains and there is no copy of $P$ with all sets coming from distinct $A^i$ or equivalently $\mathcal{F}$ admits a proper coloring (sets $F\subset F'$ must receive different colors) with no rainbow copy of $P$. A poset $(Q,\leqslant')$ rainbow forces $(P,\leqslant)$ if any proper coloring $c$ of $Q$ ($q\leqslant' q'$ or $q'\leqslant' q$ implies $c(q)\neq c(q')$) admits a rainbow copy of $P$. We establish connection between the $La^*$ and the $La^*_R$ functions via poset rainbow forcing, determine the asymptotics of $La_R^*(n,T)$ for all tree posets and obtain further exact or asymptotic results for antichains and complete bipartite posets.

A classical result of Kleitman determines the maximum number f ( n , s ) of subsets in a family $${{\mathcal {F}}}\subseteq 2^{[n]}$$ F ⊆ 2 [ n ] of sets that do not contain distinct sets $$F_1,F_2,\dots ,F_s$$ F 1 , F 2 , ⋯ , F s that are pairwise disjoint in the case $$n\equiv 0,-1$$ n ≡ 0 , - 1 (mod s ). Katona and Nagy determined the maximum size of a family of subsets of an n -element set that does not contain $$A_1,A_2,\dots ,A_t,B_1,B_2,\dots ,B_t$$ A 1 , A 2 , ⋯ , A t , B 1 , B 2 , ⋯ , B t with $$\bigcup _{i=1}^t A_i$$ ⋃ i = 1 t A i and $$\bigcup _{i=1}^t B_i$$ ⋃ i = 1 t B i being disjoint. In this paper, we consider the problem of finding the maximum number $$\textrm{vex}(n,K_{s\times t})$$ vex ( n , K s × t ) in a family $${{\mathcal {F}}}\subseteq 2^{[n]}$$ F ⊆ 2 [ n ] without sets $$F^1_1,\dots ,F^1_t,\dots ,F^s_1,\dots ,F^s_t$$ F 1 1 , ⋯ , F t 1 , ⋯ , F 1 s , ⋯ , F t s such that $$G_j=\bigcup _{i=1}^tF^j_i$$ G j = ⋃ i = 1 t F i j $$j=1,2,\dots ,s$$ j = 1 , 2 , ⋯ , s are pairwise disjoint. We determine the asymptotics of $$2^n-\textrm{vex}(n,K_{s\times t})$$ 2 n - vex ( n , K s × t ) if $$n\equiv -1$$ n ≡ - 1 (mod s ) for all t , and if $$n\equiv 0$$ n ≡ 0 (mod s ), $$t\ge 3$$ t ≥ 3 and show that in this latter case the asymptotics of the $$t=2$$ t = 2 subcase is different from both the $$t=1$$ t = 1 and $$t\ge 3$$ t ≥ 3 subcases.

We start a systematic investigation concerning bipartite Turán number for trees. For a graph $F$ and integers $1 \leq a \leq b$ we define: $(i)$\quad $ex_b(a, b, F)$ is the largest number of edges that an $F$-free bipartite graph can have with part sizes $a$ and $b$. We write $ex_b(n, F)$ for $ex_b(n, n, F)$. $(ii)$\quad $ex_{b,c}(a, b, F)$ is the largest number of edges that an $F$-free connected, bipartite graph can have with part sizes $a$ and $b$. We write $ex_{b,c}(n, F)$ for $ex{b,c}(n, n, F)$. Both definitions are similar for a family $\mathcal{F}$ of graphs. We prove general lower bounds depending on the maximum degree of $F$, as well as on the cardinalities of the two vertex classes of $F$. We derive upper and lower bounds for $ex_b(n,F)$ in terms of $ex(2n,F)$ and $ex(n, F)$, the corresponding classical (not bipartite) Turán numbers. We solve both problems for various classes of graphs, including all trees up to six vertices for any $n$, for double stars $D_{s ,t}$ if $a \geq f(s,t )$, for some families of spiders, and more. We use these results to supply an answer to a problem raised by L. T. Yuan and X. D. Zhang [{\it Graphs and Combinatorics}, 2017] concerning $ex_b( n, \mathcal{T}_{k,\ell} )$, where $\mathcal{T}_{k,\ell}$ is the family of all trees with vertex classes of respective cardinalities $k$ and $\ell$. The asymptotic worst-case ratios between Turán-type functions are also inverstigated.

A classical result of Kleitman determines the maximum number $f(n,s)$ of subsets in a family $\mathcal{F}\subseteq 2^{[n]}$ of sets that do not contain distinct sets $F_1,F_2,\dots,F_s$ that are pairwise disjoint in the case $n\equiv 0,-1$ (mod $s$). Katona and Nagy determined the maximum size of a family of subsets of an $n$-element set that does not contain $A_1,A_2,\dots,A_t,B_1,B_2,\dots,B_t$ with $\bigcup_{i=1}^t A_i$ and $\bigcup_{i=1}^t B_i$ being disjoint. In this paper, we consider the problem of finding the maximum number $vex(n,K_{s\times t})$ in a family $\mathcal{F}\subseteq 2^{[n]}$ without sets $F^1_1,\dots,F^1_t,\dots,F^s_1,\dots,F^s_t$ such that $G_j=\bigcup_{i=1}^tF^j_i$ $j=1,2,\dots,s$ are pairwise disjoint. We determine the asymptotics of $2^n-vex(n,K_{s\times t})$ if $n\equiv -1$ (mod $s$) for all $t$, and if $n\equiv 0$ (mod $s$), $t\ge 3$ and show that in this latter case the asymptotics of the $t=2$ subcase is different from both the $t=1$ and $t\ge 3$ subcases.

A 1-removed subgraph $$G_f$$G f of a graph $$G=(V,E)$$G = ( V , E ) is obtained by (i) selecting at most one edge f(v) for each vertex $$v\in V$$v ∈ V , such that $$v\in f(v)\in E$$v ∈ f ( v ) ∈ E (the mapping $$f:V\rightarrow E \cup \{\varnothing \}$$f : V → E ∪ { ∅ } is allowed to be non-injective), and (ii) deleting all the selected edges f(v) from the edge set E of G. Proper vertex colorings of 1-removed subgraphs proved to be a useful tool for earlier research on some Turán-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as $$\chi _1(G)$$χ 1 ( G ) . This invariant is defined as the minimum chromatic number $$\chi (G_f)$$χ ( G f ) among all 1-removed subgraphs $$G_f$$G f of G. We also examine other standard graph invariants in a similar manner.