20
votes
Accepted
Does the hypergraph of subgroups determine a group?
In the comments to the question, I notice something which might be an error, or at least is an incomplete response. It is pointed out in the comments that there exist nonisomorphic groups with ...
- 10.4k
11
votes
Does the hypergraph of subgroups determine a group?
For large prime $p$, there are uncountably many non-isomorphic Tarski monsters of exponent $p$.
For these groups $G$, the subgroups lattice consists of basically a partition of $G\smallsetminus\{1\}$...
- 55.2k
11
votes
Accepted
Singular cardinal $\kappa$ with projective plane such that all edges have cardinality $<\kappa$
The answer is no. Let $\kappa$ be any infinite cardinal, regular or singular, and assume for a contradiction that there is a set $E\subseteq\mathcal P(\kappa)$ satisfying your conditions. I will call ...
- 9,221
10
votes
Accepted
Chromatic number of a connected Hausdorff space
The answer is no.
A space is called resolvable if it contains two disjoint dense subspaces. Clearly $X$ is resolvable if and only if $\chi(X)=2$. Lets prove by induction on $n \geq 2$ that if $\chi(X)...
9
votes
Accepted
Infinite projective plane with small edges
Update. Here is a new simpler answer that works for all regular
$\kappa$, including $\kappa=\omega$. And I have omitted the use
of Fodor's lemma, using instead merely the pigeon-hole principle.
...
- 206k
9
votes
Accepted
Subset of $[\omega]^\omega$ that can be "colored" with $3$, but not $2$ colors
Partition $\omega$ into three infinite subsets $A_0,A_1,A_2$. Let $S$ consists of subsets which intersects precisely two of the $A_i$ at infinitely many elements. It can obviously be $3$-colored. ...
- 25.3k
9
votes
n sets, each is large, the intersection of every three is small, what is the size of the union?
It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are ...
- 17.9k
9
votes
Accepted
Coloring the uncountable Lebesgue-measurable sets of $\mathbb{R}$
It is continuum. The coloring with continuum many colors is clear (all points may have different color). Assume that we have $\kappa<c$ colors. Consider the Cantor set $K$. All its subsets are ...
- 93.5k
8
votes
Accepted
Ramsey type theorem
Yes, your conjecture is true.
Suppose otherwise. Then there exists a counterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f(...
- 11.9k
8
votes
Accepted
Simple way to calculate the eigenvalues of a $2 \times 2 \times 2$ tensor
As explained in a previous MO question, there is no unique generalization of the eigenvalue of an $n\times n$ matrix to an $n\times n\times n$ tensor. One approach is to construct a higher-order ...
- 160k
7
votes
Accepted
Is it true that any $3$-uniform hypergraph that is not $k$-colorable must have $\Omega(k^3)$ edges?
The following paper of Alon shows that the quantity you're after, $m(k)$, the minimum number of edges of a $3$-uniform hypergraph which is not $k$-colourable, is indeed $\asymp k^3$.
More precisely, ...
- 6,353
7
votes
Non-isomorphic hypergraphs on $\omega$
Others have already answered, but I think the following counting argument is worth pointing out:
there are $2^{2^{\aleph_0}}$ hypergraphs on $\omega$ (since a hypergraph on $\omega$ is just a ...
- 25.4k
7
votes
Accepted
Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?
This is essentially done by the Bernstein set construction: if one has $\kappa$ many sets each of size $\kappa$, then order them into ordinal $\kappa$ and recursively choose 2 points from each, so ...
- 7,144
7
votes
Accepted
Intersecting subsets of $\{1,\ldots,n\}$
No, there isn't. This is essentially the dual version of the De Bruijn-Erdos theorem if the elements of $\mathcal C$ are the points, and the elements from $\{1,\ldots,n\}$ are the lines. The original ...
- 17.9k
7
votes
VC dimension of vector spaces
I will turn my comment above into a self-contained answer. Given a hypergraph $H=(V,E)$ and $X \subseteq V$, we say that $X$ is shattered if for all $X' \subseteq X$, there exists $e \in E$ such that $...
- 29.6k
7
votes
Accepted
Discrepancy of random bipartite graphs
The expected degree of a vertex is $k$, which we are keeping fixed as $n\to\infty$. As $n\to\infty$, the vertex degree distribution converges to Poisson($k$). In particular, a proportion roughly $e^{-...
- 3,626
6
votes
Accepted
A generalization of Erdős-Ko-Rado theorem
The case $s=1$ is Erdős hypergraph mathcing conjecture from
Paul Erdős (1965). A problem on independent $r$-tuples. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95.
users.renyi.hu/~...
- 2,926
6
votes
Accepted
Maximum intersecting set families of $\{1,\ldots,n\}$
The intersecting family in your example has $\binom{n-1}{\lfloor\frac{n-1}{2}\rfloor}$ members by Sperner's theorem. An example that achieves a larger value would be to take all the subsets of $[n]$ ...
- 83.2k
6
votes
Does the hypergraph of subgroups determine a group?
As @Keith Kearnes says, the negative answer ought to be somewhere in Roland Schmidt's book. Unless I'm mistaken, it suffices to find two non isomorphic groups with isomorphic coset lattices. Indeed, ...
- 3,227
6
votes
Accepted
Injective choice function for "lines" in an infinite cardinal
Observe that $|\mathcal L|\leq\lambda$, since mapping $k$ to the pair of its two smallest elements gives an injection $\mathcal L\to\lambda^2$.
Enumerate elements of $\mathcal L$ as $k_\alpha,\alpha&...
- 25.3k
6
votes
Accepted
Independence number of $4$-uniform regular hypergraph
In general no. Partition the vertices onto $n/k$ subsets (I call them classes) of size $k$, where $k$ grows as $n^{2/3}$. Take into your hypergraph all 4-edges with the vertices in the same class. It ...
- 93.5k
6
votes
Accepted
$1$-factorizability for "complete" finite hypergraphs
This is Baranyai's theorem. Other than in Baranyai's original paper you can also find a cool proof in the article "Uniform hypergraphs" by Brouwer and Schrijver which uses max-flow min-cut.
- 83.2k
6
votes
Accepted
A sequence of cardinal characteristics constructed with hypergraph coloring
The cardinals $\bf k_n$ ($2\le n\lt\omega$) are all equal.
Lemma. Let $\kappa$ be an infinite cardinal. Given a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt n$, we can ...
- 9,221
6
votes
Accepted
Strategies for bounding the spectral norm of a tensor?
I will show, with some non-rigorous steps, that a bound of this form that is valid for arbitrary tensors and useful for sparse tensors (fewer than $n^{k/2}$ nonvanishing entries) does not exist.
First ...
- 123k
6
votes
Accepted
n sets, each is large, the intersection of every three is small, what is the size of the union?
Let $m$ be chosen later, and let $A_1, A_2, \dots, A_n$ be independently chosen random subsets of $\{1,2,\dots m\}$, each having size $n$.
For a fixed $a+1$-tuple $(x_1, x_2, \dots, x_{a+1})$ of ...
- 5,671
6
votes
Accepted
Property ${\bf B}$ for families of large sets with small intersection
EDIT: I'll leave my previous answer up for now (at the end of this one), but here's an easier answer that doesn't need assumptions like CH that go beyond ZFC.
It's well-known that there is a family of ...
- 69.9k
5
votes
Accepted
Edge chromatic number of hypergraphs
This is equivalent reformulation of Erdös-Faber-Lovász conjecture, see Wikipedia page about it.
https://en.m.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Faber%E2%80%93Lov%C3%A1sz_conjecture
- 93.5k
5
votes
Proof that it's possible to colour all elements in set, that all subsets will be bicolored
Yes. Let $S$ be a family of finite subsets of some linearly ordered set $L.$ Suppose that each member of $S$ has at least two elements, and that no two members of $S$ form a "globally ordered pair". ...
- 9,221
5
votes
Class of hypergraphs that are always the neighborhood hypergraph of some simple graph
Here is another way of thinking about the problem. Suppose for simplicity that your hypergraph $\mathcal{H}$ has exactly $|V(\mathcal{H})|$ hyperedges (as was mentioned by Dominic, we can immediately ...
- 761
5
votes
Accepted
Is there a Degenerate Dependency Local Lemma?
Here is my intuition that it may not be possible.
I am guessing that as in the case of the original LLL, such an inequality would in turn imply a simpler inequality of the following form:
"If the ...
- 321
Only top scored, non community-wiki answers of a minimum length are eligible