6
votes
Accepted
How much can we "shrink" intersecting families
Counterexample. Let $X=\{1,2,3,\dots,n\}$ where $n\ge8$, and let
$$\mathcal S=\{\{1,2\},\ \{1,3\},\ \{2,3\}\}\cup\{\{2,3,x\}:3\lt x\le n\}\subset\mathcal P(X).$$
Then $\mathcal S$ is an intersecting ...
- 11.9k
5
votes
Accepted
Turán density of hypergraphs with very few edges
Seems, the answer is negative for $m=3$: consider $H = \{AB, BC, AC\}$ for disjoint $k$-element sets $A,B,C$. Then for $r=2k$ the is an $r$-graph $F$ which density is close to 0.5: consider only $r$-...
- 226
5
votes
Longest paths and cycles in Steiner triple systems
Im, Kim, Lee and Methuku have recently shown that one can find loose paths on $(1 - o(1))n$ vertices in any Steiner triple system on $n$ vertices. This is of course best possible up to the $o(1)$ term....
- 606
5
votes
Accepted
Pseudo-partitions of $\mathbb{N}$
Yes. Let $\mathcal{E} = \{\mathbb{N} \setminus \{0\}, \mathbb{N} \setminus \{1\}\} \cup \{\{0,n\} : n \in \mathbb{N}\}$. No subset of this is a partition of $\mathbb{N}$, because too many of the sets ...
- 1,411
5
votes
Set sizes in linear set systems on $\mathbb{N}$ containing some disjoint sets
Yes. Fix a partition $\left<A_n\right>_{n\leq\omega}$
of $\mathbb{N}$ such that $A_n$ is infinite for each $n<\omega$, and $A_\omega$ has cardinality 3.
For $n<\omega$ let $B_\ell=\...
- 8,752
5
votes
Accepted
Finite pair-splitting family of $\mathbb{N}$
$\newcommand\F{\mathfrak F}\newcommand\P{\mathfrak P}\newcommand\N{\mathbb N}\newcommand\om{\omega}$No. Let $\P$ be the partition of $\N$ generated by $\F$.
Detail: If $\F=\{S_1,\dots,S_n\}$, then the ...
- 118k
4
votes
Accepted
$\aleph_0$-uniform non-bipartite linear hypergraph
Every $\aleph_0$-uniform linear hypergraph is bipartite. More generally:
Theorem. If $H=(V,E)$ is an $\aleph_0$-uniform hypergraph, and if there is a number $n\lt\aleph_0$ such that $|\{e\in E:S\...
- 11.9k
4
votes
Accepted
Set sizes in linear set systems on $\mathbb{N}$ containing some disjoint sets
Yes. Let $[\mathbb N]^2=\{p_n:n\in\mathbb N\}$ with $p_1=\{1,2\}$. Define $e_n$ recursively as follows. $e_1=\{1,2,3,4\}$. For $n\gt1$, if $p_n\subseteq e_k$ for some $k\lt n$, let $e_n=e_k$; ...
- 11.9k
4
votes
How to get a partite minimum co-degree in a $k$-partite $k$-uniform hypergraph?
It is not always possible to do that.
Consider the following construction.
Let $V_1, V_2, V_3$ be disjoint $n$-sized sets.
Let $G$ be a random $3$-partite $2$-graph where every edge with endpoints in ...
- 606
4
votes
Accepted
Posets such that the collection of principal down-sets does not have property ${\bf B}$
Let $M$ be the ordered Mostowski model (T. Jech, The Axiom of Choice, Section 4.5). Its set of atoms, $A$, has a linear order $\prec$ that makes it isomorphic to the rationals. Let $S\in M$ be a ...
- 9,910
3
votes
Accepted
Possible chromatic numbers of a hypergraph on $\omega$ with a deck of edges
The answer is plainly negative for $k=1$ and positive for $k=2$. The answer is negative for $k\gt2$ because $(\omega,E)$ is $2$-colorable whenever the edge-set $E$ is a "deck," i.e., ...
- 11.9k
3
votes
Posets such that the collection of principal down-sets does not have property ${\bf B}$
The axiom of choice implies that for every partial order $P$ the
hypergraph $H_P$ has property $B$.
Let $(P,\le)$ be a partial order.
We first claim the following: for every $p\in P$ there is a $q\le ...
- 9,910
3
votes
Accepted
Counting $K_{2, 2, \,\ldots\,,2}$ in a $k$-partite $k$-uniform hypergraph
You can use the doubling method (a.k.a. Cauchy-Schwarz)
For simplicity, suppose we are working in the graph case. So, let $G$ be a graph with bipartition $X\cup Y$ with $|X|=|Y|=n$ and suppose that $e(...
- 56
3
votes
Accepted
Chromatic numbers realised by almost disjoint subsets of $\omega$
This question was answered affirmatively by Theorem 1.1 of Paul Erdős and Saharon Shelah, Separability properties of almost-disjoint families of sets, Israel J. Math. 12 (1972) 207–214 (pdf), ...
- 11.9k
2
votes
Accepted
Isomorphism of two regular hypergraphs
No. There are already multiple isomorphism classes of regular graphs. Consider two disjoint triangles (i.e., $\{12,23,31\}\cup \{45,56,64\}$), versus a cycle of length 6 ($\{12,23,34,45,56,61\}$).
- 3,413
2
votes
Constants for diagonal hypergraph Ramsey Theorem
The best source I know for bounds on Ramsey numbers, including hypergraph Ramsey numbers, is Radziszowski's article Small Ramsey Numbers, which constantly gets updated. Since the question didn't ...
- 29.8k
2
votes
Accepted
Is the chromatic number of hypergraphs downward continuous?
Fred Galvin had conjectured that the answer is "yes" for graphs in [1] (conjecture 2), in his paper he showed that the variation of the problem to induced graphs is consistently false: ...
- 1,643
2
votes
Hypergraph cartesian join operation (over same vertex set)
The problem of poly-time inversion of this kind of product was solved in 2014. See, for example,
Pavel Emelyanov and Denis Ponomaryov "The Complexity of AND-decomposition of Boolean Functions&...
- 21
1
vote
Accepted
The vertex-covering number of a particular hypergraph
I am afraid that $f(n)$ does not grow, even if you use only permutations of $(0,1,2)$.
I claim that the minimal size of $S$ is $3^{n-1}$. As an example, you may take all rows with first coordinate 0.
...
- 103k
Only top scored, non community-wiki answers of a minimum length are eligible