M. Axenovich

Non-isomorphic graphs have distinct vertex-Ramsey classes

Maria Axenovich, Patrick Schmitteckert

For a graph $H$ , its $k$ -colour vertex Ramsey class is the set of all graphs $G$ such that any colouring of the vertices of $G$ in $k$ colours results in a monochromatic (induced)…

On high-girth layered graphs of large Turán density in a hypercube

Maria Axenovich, Marko Pejić

For a graph $H$ , let $ex (Q_{n}, H)$ be the largest number of edges in a subgraph of the hypercube $Q_{n}$ of dimension $n$ that contains no subgraph isomorphic to $H$ . W…

Vertex-Ramsey theorems for Cartesian powers of graphs

Nóra Almási, Maria Axenovich, Arsenii Sagdeev

For graphs $G, H$ and positive integers $r$ and $n$ we write $G^{□ n} r H$ if every $r$ -vertex-coloring of the Cartesian power $G^{□ n}$ of $G$ contains a…

Largest density of a layered subgraph of a hypercube

Maria Axenovich, Arsenii Sagdeev

Let $L (t)$ denote the largest number of edges induced by $t$ vertices from two vertex layers of a hypercube. We show that $$\frac14 t\log_2 t+\frac18 t\log_2\log_2 t-O(t) \leq L(t)…

A note on Ramsey numbers for minors

Maria Axenovich, Raphael Steiner

Let $R_{h} (k; ℓ)$ be the smallest integer $n$ such that any edge coloring of a complete graph on $n$ vertices in $ℓ$ colors results in a monochromatic $K_{k}$ -minor, in other wor…

Ramsey problems for graphs in Euclidean spaces and Cartesian powers

Maria Axenovich, Dingyuan Liu, Arsenii Sagdeev

Given a graph $H$ , let $χ_{H} (R^{n})$ be the smallest positive integer $r$ such that there exists an $r$ -coloring of $R^{n}$ with no monochromatic unit-copy of $H$ , tha…

Online Ramsey turnaround numbers

Nóra Almási, Maria Axenovich

The online Ramsey turnaround game is a game between two players, Builder and Painter, on a board of $n$ vertices using $3$ colors, for a fixed graph $H$ on at most $n$ vertices. Th…

An improved upper bound for the multicolour Ramsey number of odd cycles

Maria Axenovich, Wouter Cames van Batenburg, Oliver Janzer +2

We show that the $k$ -colour Ramsey number of an odd cycle of length $2 ℓ + 1$ is at most $(4 ℓ)^{k} \cdot k^{k / ℓ}$ . This proves a conjecture of Fox and is the first improvem…

Turán problems for simplicial complexes

Maria Axenovich, Dániel Gerbner, Dingyuan Liu +1

An abstract simplicial complex $F$ is a non-uniform hypergraph without isolated vertices, whose edge set is closed under taking subsets. The extremal number $\mathrm{ex}(n…

A note on the mutual-visibility coloring of hypercubes

Maria Axenovich, Dingyuan Liu

A subset $M$ of vertices in a graph $G$ is a mutual-visibility set if for any two vertices $u, v \in M$ there exists a shortest $u$ - $v$ path in $G$ that contains no elements of $M$ …

On hypercube statistics

Noga Alon, Maria Axenovich, John Goldwasser

Let $d \geq 1$ and $s \leq 2^{d}$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_{n}$ and $n \geq d$ , let $λ (n, d, s, A)$ denote the fraction of subcubes $Q_{d}$ o…

Faces in girth-saturated graphs on surfaces

Maria Axenovich, Leon Kießle, Arsenii Sagdeev +1

What is the maximum length $f_{max} (ℓ, Σ)$ of a facial cycle of an inclusion-maximal graph with girth at least $ℓ$ embedded on a given surface $Σ$ ? If $Σ=\mathcal{P…

Chromatic Ramsey numbers and two-color Turán densities

Maria Axenovich, Simon Gaa, Dingyuan Liu

Given a graph $G$ , its $2$ -color Turán number $ex^{(2)} (n, G)$ is the maximum number of edges in an $n$ -vertex graph, such that the edges can be colored with two colors avo…

Diagonal poset Ramsey numbers

Maria Axenovich, Christian Winter

A poset $(Q, \leq_{Q})$ contains an induced copy of a poset $(P, \leq_{P})$ if there exists an injective mapping $ϕ : P \to Q$ such that for any two elements $X, Y \in P$ , $X \leq_{P} Y$ if a…

math.CO2024★ 1 cited

Visibility in hypercubes

Maria Axenovich, Dingyuan Liu

A subset $M$ of vertices in a graph $G$ is a mutual-visibility set if any two vertices $u$ and $v$ in $M$ ``see'' each other in $G$ , that is, there exists a shortest $u, v$ -path in…

Induced Turán problem in bipartite graphs

Maria Axenovich, Jakob Zimmermann

The classical extremal function for a graph $H$ , $e x (K_{n}, H)$ is the largest number of edges in a subgraph of $K_{n}$ that contains no subgraph isomorphic to $H$ . Note that defining…

A note on multicolour Erdős-Hajnal conjecture

Maria Axenovich, Lea Weber

Informally, the Erdős-Hajnal conjecture (shortly EH-conjecture) asserts that if a sufficiently large host clique on $n$ vertices is edge-coloured avoiding a copy of some fixed edge…

A class of graphs of zero Turán density in a hypercube

Maria Axenovich

A graph is cubical if it is a subgraph of a hypercube. For a cubical graph $H$ and a hypercube $Q_{n}$ , $e x (Q_{n}, H)$ is the largest number of edges in an $H$ -free subgraph of $Q_{n}$ .…

Large cliques or co-cliques in hypergraphs with forbidden order-size pairs

Maria Axenovich, Domagoj Bradač, Lior Gishboliner +2

The well-known Erdős-Hajnal conjecture states that for any graph $F$ , there exists $ε > 0$ such that every $n$ -vertex graph $G$ that contains no induced copy of $F$ has a homogeneous…

Homogeneous sets in hypergraphs with forbidden order-size pairs

Maria Axenovich, Dhruv Mubayi, Lea Weber

The well-known Erdős-Hajnal conjecture states that for any graph $F$ , there exists $ε > 0$ such that every $n$ -vertex graph $G$ that contains no induced copy of $F$ has a homogeneous…

math.CO2023★ 1 cited

On graphs embeddable in a layer of a hypercube and their extremal numbers

Maria Axenovich, Ryan R. Martin, Christian Winter

A graph is cubical if it is a subgraph of a hypercube. For a cubical graph $H$ and a hypercube $Q_{n}$ , $e x (Q_{n}, H)$ is the largest number of edges in an $H$ -free subgraph of $Q_{n}$ .…