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

#### Related Tags

hypergraph × 250co.combinatorics × 131

graph-theory × 90

infinite-combinatorics × 71

graph-colorings × 51

set-theory × 46

matching-theory × 17

reference-request × 14

pr.probability × 11

algorithms × 11

linear-algebra × 9

random-graphs × 8

perfect-matchings × 8

combinatorial-designs × 8

lo.logic × 7

covering × 7

bipartite-graphs × 5

discrepancy-theory × 5

gn.general-topology × 4

computational-complexity × 4

extremal-graph-theory × 4

extremal-combinatorics × 4

nt.number-theory × 3

ct.category-theory × 3

discrete-geometry × 3