Soukaina Zayat

Dr. Soukaina Zayat


Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
2 September 2022 in Journal of Graph Theory
Verified
Journal Article
Closed access
SZSoukaina Zayat
Soukaina Zayat
SGSalman Ghazal
Salman Ghazal

19 October 2023 in Discrete Mathematics
Verified
Journal Article
Closed access
SZSoukaina Zayat
Soukaina Zayat
SGSalman Ghazal
Salman Ghazal

4 April 2023 in Graphs and Combinatorics
Verified
Journal Article
Closed access
PDF file
SZSoukaina Zayat
Soukaina Zayat
SGSalman Ghazal
Salman Ghazal

10 August 2022 in arXiv
Verified
Preprint
Open access
PDF file
SZSoukaina Zayat
Soukaina Zayat
SGSalman Ghazal
Salman Ghazal
A celebrated unresolved conjecture of Erd\"{o}s and Hajnal states that for every undirected graph $H$ there exists $ \epsilon(H) > 0 $ such that every undirected graph on $ n $ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $ n^{\epsilon(H)} $. The conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ \epsilon(H) > 0 $ such that every $H-$free $n-$vertex tournament $T$ contains a transitive subtournament of order at least $ n^{\epsilon(H)} $. Both the directed and the undirected versions of the conjecture are known to be true for small graphs (tournaments). So far the conjecture was proved only for some specific families of prime tournaments, tournaments constructed according to the so$-$called substitution procedure allowing to build bigger graphs, and for all five$-$vertex tournaments. Recently the conjecture was proved for all six$-$vertex tournament, with one exception, but the question about the correctness of the conjecture for all seven$-$vertex tournaments remained open. In this paper we prove the correctness of the conjecture for several seven$-$vertex tournaments.

10 August 2022 in arXiv
Verified
Preprint
Open access
PDF file
SZSoukaina Zayat
Soukaina Zayat
SGSalman Ghazal
Salman Ghazal
The celebrated Erd\"{o}s-Hajnal conjecture states that for every undirected graph $H$ there exists $ \epsilon(H) > 0 $ such that every undirected graph on $ n $ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $ n^{\epsilon(H)} $. This conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ \epsilon(H) > 0 $ such that every $H$-free $n$-vertex tournament $T$ contains a transitive subtournament of order at least $ n^{\epsilon(H)} $. This conjecture is proved for few infinite families of tournaments. In this paper we construct a new infinite family of tournaments $-$ the family of so-called flotilla-galaxies and we prove the correctness of the conjecture for every flotilla-galaxy tournament.

8 August 2022 in arXiv
Verified
Preprint
Open access
PDF file
SZSoukaina Zayat
Soukaina Zayat
SGSalman Ghazal
Salman Ghazal
Erd\"{o}s-Hajnal conjecture states that for every undirected graph $H$ there exists $ \epsilon(H) > 0 $ such that every undirected graph on $ n $ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $ n^{\epsilon(H)} $. This conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ \epsilon(H) > 0 $ such that every $H-$free $n-$vertex tournament $T$ contains a transitive subtournament of order at least $ n^{\epsilon(H)} $. This conjecture is known to hold for a few infinite families of tournaments. In this paper we construct two new infinite families of tournaments - the family of so-called galaxies with spiders and the family of so-called asterisms, and we prove the correctness of the conjecture for these two families.