A {em special four-cycle } $F$ in a triple system consists of four triples {em inducing } a $C_4$. This means that $F$ has four special vertices $v_1,v_2,v_3,v_4$ and four triples in the form $w_iv_iv_{i+1}$ (indices are understood $pmod 4$) where th
e $w_j$s are not necessarily distinct but disjoint from ${v_1,v_2,v_3,v_4}$. There are seven non-isomorphic special four-cycles, their family is denoted by $cal{F}$. Our main result implies that the Turan number $text{ex}(n,{cal{F}})=Theta(n^{3/2})$. In fact, we prove more, $text{ex}(n,{F_1,F_2,F_3})=Theta(n^{3/2})$, where the $F_i$-s are specific members of $cal{F}$. This extends previous bounds for the Turan number of triple systems containing no Berge four cycles. We also study $text{ex}(n,{cal{A}})$ for all ${cal{A}}subseteq {cal{F}}$. For 16 choices of $cal{A}$ we show that $text{ex}(n,{cal{A}})=Theta(n^{3/2})$, for 92 choices of $cal{A}$ we find that $text{ex}(n,{cal{A}})=Theta(n^2)$ and the other 18 cases remain unsolved.
A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cghs consisting of two disjoint triples. These were studied at length by Bra{ss} (2004) and b
y Aronov, Dujmovic, Morin, Ooms, and da Silveira (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of $n$ points in the plane.
The notion of cross intersecting set pair system of size $m$, $Big({A_i}_{i=1}^m, {B_i}_{i=1}^mBig)$ with $A_icap B_i=emptyset$ and $A_icap B_j eemptyset$, was introduced by Bollobas and it became an important tool of extremal combinatorics. His clas
sical result states that $mle {a+bchoose a}$ if $|A_i|le a$ and $|B_i|le b$ for each $i$. Our central problem is to see how this bound changes with the additional condition $|A_icap B_j|=1$ for $i e j$. Such a system is called $1$-cross intersecting. We show that the maximum size of a $1$-cross intersecting set pair system is -- at least $5^{n/2}$ for $n$ even, $a=b=n$, -- equal to $bigl(lfloorfrac{n}{2}rfloor+1bigr)bigl(lceilfrac{n}{2}rceil+1bigr)$ if $a=2$ and $b=nge 4$, -- at most $|cup_{i=1}^m A_i|$, -- asymptotically $n^2$ if ${A_i}$ is a linear hypergraph ($|A_icap A_j|le 1$ for $i e j$), -- asymptotically ${1over 2}n^2$ if ${A_i}$ and ${B_i}$ are both linear hypergraphs.
The distinguishing number of a graph $G$, denoted $D(G)$, is the minimum number of colors needed to produce a coloring of the vertices of $G$ so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment $L$ on a g
raph $G$ is a function that assigns each vertex of $G$ a set of colors. An $L$-coloring of $G$ is a coloring in which each vertex is colored with a color from $L(v)$. The list distinguishing number of $G$, denoted $D_{ell}(G)$ is the minimum $k$ such that every list assignment $L$ that assigns a list of size at least $k$ to every vertex permits a distinguishing $L$-coloring. In this paper, we prove that when and $n$ is large enough, the distinguishing and list-distinguishing numbers of $K_nBox K_m$ agree for almost all $m>n$, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
