bluuebunny/crossref_metadata_2025 huggingface dataset:
Percepção docente sobre o uso do WhatsApp como ferramenta de comunicação no ensino remoto emergencial
Authors: Calderon Ivanilse , Valle Pedro , Oran Ana , Vilela Ricardo , Lima Rayfran , Garcia Renato , Silva Williamson , Feitosa Eduardo
Published: June 2023

Durante a pandemia causada pelo novo coronavírus (Sars-CoV-2), a educação precisou se adaptar e os espaços de aprendizagem passaram a ser exclusivamente remotos. Com isso, docentes começaram a adotar ferramentas interativas para facilitar a interação e a comunicação antes, durante e após as aulas. Uma das ferramentas adotadas foi o WhatsApp. Este artigo apresenta os resultados de um survey conduzido com 363 docentes de diferentes regiões do país. O survey caracterizou aspectos positivos e negativos do ponto de vista dos docentes sobre o uso do WhatsApp durante o ensino remoto emergencial. Como resultados, observou-se uma facilidade e agilidade da comunicação. Como consequência, houve uma perda de privacidade por parte dos docentes.
Acessibilidade para Pessoas Cegas: Avaliação de Compatibilidade do TalkBack com a ABNT NBR 17060
Authors: Silva Clemer dos S. , Oliveira Lucas L. de , Silva Matheus dos S. , Nogueira Tiago do C.
Published: June 2023

O frequente lançamento de atualizações e recursos de acessibilidade é uma característica marcante do Sistema Operacional (SO) Android. O Google TalkBack é um recurso que oferece navegação autônoma a pessoas cegas por meio de respostas audíveis. É importante a compatibilidade com diretrizes de acessibilidade. Para esta pesquisa, foi elaborado um checklist com quatro critérios baseados na ABNT NBR 17060 para avaliação do TalkBack comparativamente aos requisitos e recomendações previstos na norma brasileira. A abordagem metodológica considerou o levantamento feito em questionário direcionado a respondentes cegos e a experiência de uso em um Smartphone Motorola Moto G22, Android 12. O recurso apresentou compatibilidade com apenas dois dos critérios abordados. Os resultados deste trabalho devem servir de indicador de melhorias para o recurso analisado para garantir maior acessibilidade a pessoas cegas no uso de Smartphones Android.
Medienethische Kompetenzen für eine digitale Welt. Ein interdisziplinäres Prozessmodell
Authors: Endres Susanna
Published: June 2023

Medien sind von sozialisatorischer Bedeutung. Sie unterstützen die Entwicklung hin zum souveränen Subjekt. Medi- enkompetenz spielt in diesem Prozess eine wichtige Rolle, wobei deren ethische Dimension unter dem Eindruck der Digitalisierung an Relevanz gewinnt. Um diese Erkenntnis für die Praxis fruchtbar zu machen, untersucht der vorliegende Beitrag, wie bestehende Modelle von Medienkompetenz und ethischer Kompetenz zu einem Konzept medienethischer Kompetenz zusammengeführt werden können. Grundlage hierfür ist der Dreischritt „Sehen – Urteilen – Handeln“, anhand dessen ethische Fähigkeiten im Umgang mit digitalen Medienwelten diskutiert werden.
Politische Entscheidungen und Kommunikation in Krisensituationen
Authors: Kals Elisabeth , Maes Jürgen , Strubel Isabel T.
Published: June 2023

Politische Entscheidungsträger:innen in Demokratien sind darauf angewiesen, ihre Maßnahmen und Entscheidungen gut zu begründen und nachvollziehbar zu erklären, wenn sie die Akzeptanz, politische Unterstützung, Identifikation und Beteiligung der Bürger:innen behalten und stärken wollen. Am Beispiel der Covid-19-Pandemie argumentieren wir, dass gerechtigkeitspsychologische Erkenntnisse hilfreich sind, sowohl die Entscheidungen selbst, den Prozess der Entscheidungsfindung als auch die Kommunikation darüber so zu gestalten, dass die von den Verantwortlichen für notwendig gehaltenen Maßnahmen von Bürger:innen nachvollzogen, akzeptiert und beachtet werden. Dadurch wird die Eigenverantwortung der Bürger:innen gestärkt.
Interdependences between access to education and equal economic chances: legal issues and the example of Uganda.
Authors: Kembabazi Gloria
Published: June 2023

This paper examines interdependencies between access to education and equal economic chances with a focus on Uganda spotlighted through legal lenses. Interestingly, access to education does not only interact with equal economic chances as a cause-and-effect relationship but rather as an interdependency. This paper gives a full background of education as a sector in Uganda and then examines the legal framework before delving into some challenges culminating into a spotlight on the impact of COVID-19 pandemic on education in Uganda. The paper the looks at a way forward and makes a conclusion on what is pertinent.
Responsibility of the East African Community to Safeguard Physical Integrity and Freedom of the Citizens of its Member States
Authors: Sylister Magdalena
Published: June 2023

This paper looks at the responsibility that the East African Community (EAC) has in safeguarding the right of physical integrity and freedom among the citizens of the Community’s Partner States. It examines the extent in which the EAC has discharged that responsibility and what needs to be in response to any existing shortcomings. The first part of this work is the conceptual framework where the key concepts have been defined and explained. Those concepts are the right to bodily integrity and freedom. The next part is on the legal and institutional framework of the East African Community which deals with protection of the right of physical integrity and freedom. After that part, I have presented a number of incidents of violation of the right of physical integrity and freedom within the EAC region in order to use them as the basis for examining the performance of the EAC’s responsibility referred to herein. The main findings of this work are that EAC has an enormous responsibility to safeguard the right to physical integrity and freedom within its jurisdiction; and that so far, the EAC has underperformed that task. Most of what has been done is more of strategizing, planning and expression of commitments while very little work has been down on the ground. As a result, many citizens of EAC Partner States continue to suffer gross violations of their right of physical integrity as well as their freedoms both from governmental and non-governmental actors. In view of that, the paper has urged the EAC and its Partner States to be more proactive in discharging that significant responsibility.
Evaluation of the Most Common Viral Causes of Fever and Neutropenia in Children Hospitalized in Abuzar Children’s Medical Center in Ahvaz, Iran
Authors: Shamsizadeh Ahmad , Neisi Niloofar , Seyedsalehi Seyede Shabnam , Fathi Mohammadreza , Alisamir Mohsen , Mirkarimi Seyed Mohammadreza
Published: June 2023

Background: Viral infections are the most common cause of fever and neutropenia in children without underlying disease, and data are still limited in this regard. Objective: This study aimed to identify the most common viral causes of fever and neutropenia in pediatrics. Methods: This descriptive-analytical study was conducted on pediatric patients younger than 18 years old referred to the pediatric emergency ward with fever as the chief complaint and no underlying diseases; patients with neutropenia and no evidence of bacterial infections in terms of different cultures were included in the study. After obtaining parental consent, nasopharyngeal swab specimens were taken from patients during the coronavirus disease 2019 (COVID-19) pandemic, and blood samples were analyzed to detect viruses in each patient. Results: Fifty patients (54.3%) had mild neutropenia (absolute neutrophil count (ANC): 1000 - 1500/μL), 40 patients (43.5%) had moderate neutropenia (ANC: 1000 - 500/μL), and 2 cases (2.2%) had severe neutropenia (ANC < 500/μL). Among all the cases, 19 cases were positive in terms of virus examination, including adenovirus (6.5%), enterovirus (5.4%), cytomegalovirus (CMV) (3.3%), Epstein-Barr virus (EBV) (3.3%), and Herpes virus 6 (2.2%). A significant correlation was found between enterovirus and neutropenia (P = 0.005). Conclusions: The most common viruses found in neutropenic children hospitalized due to fever without any underlying disease were adenovirus and enterovirus, respectively. Considering the good general condition and relatively quick recovery, consideration of viral causes is recommended in this category of patients, and it is better to avoid prescribing broad-spectrum antibiotics, and careful follow-up should be carried out.
Partition Universality for Hypergraphs of Bounded Degeneracy and Degree
Authors: Allen Peter , Böttcher Julia , Cecchelli Domenico
Published: June 2023

We consider the following question. When is the random $k$-uniform hypergraph $\Gamma=G^{(k)}(N,p)$ likely to be $r$-partition universal for $k$-uniform hypergraphs of bounded degree and degeneracy? That is, for which~$p$ can we guarantee asymptotically almost surely that in any $r$-colouring of $E(\Gamma)$ there exists a colour $\chi$ such that in $\Gamma$ there are $\chi$-monochromatic copies of all $k$-uniform hypergraphs of maximum vertex degree $\Delta$, degeneracy at most $D$, and $cN$ vertices for some constant $c=c(D,\Delta)>0$. We show that if $\mu>0$ is fixed, then $p\ge N^{-1/D+\mu}$ suffices for a positive answer if $N$ is large. On the other hand, for $p=o(N^{-1/D})$ we show that $G^{(k)}(N,p)$ is likely not to contain some graphs of maximum degree $\Delta$ and degeneracy $D$ on $cN$ vertices at all. This improves the best upper bounds on the minimum number of edges required for a $k$-uniform hypergraph to be partition universal (even for $k=2$) and also for the size-Ramsey problem for most $k$-uniform hypergraphs of bounded degree and degeneracy.
Expander graphs, strong blocking sets and minimal codes
Authors: Alon Noga , Bishnoi Anurag , Das Shagnik , Neri Alessandro
Published: June 2023

We give a new explicit construction of strong blocking sets in finite projective spaces using expander graphs and asymptotically good linear codes. Using the recently found equivalence between strong blocking sets and linear minimal codes, we give the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$ such that $n$ is at most a constant times $q k$. This solves one of the main open problems on minimal codes.
Moderate deviations of triangle counts – the lower tail
Authors: Alvarado José , Do Gabriel , Griffiths Simon
Published: June 2023

Two recent papers~\cite{GGS} and~\cite{NRS22} study the lower tail of triangle count deviations in random graphs $G(n,m)$ with positive density $t:=m/\binom{n}{2}\in (0,1)$. Let us write $D_{\triangle}(G)$ for the deviation of the triangle count from its mean. Results of~\cite{GGS} and~\cite{NRS22} determine the order of magnitude of the log probability $\log(\pr{D_{\triangle}(G(n,m)) \, < \, - \tau\binom{n}{3}})$ for the ranges $n^{-3/2}\ll \tau\ll n^{-1}$ and $n^{-3/4}\ll\tau\ll 1$ respectively. Furthermore, in~\cite{NRS22} it is proved that the log probability is at least $\Omega(\tau^2 n^{3})$ in the ``missing'' range $n^{-1}\ll \tau\ll n^{-3/4}$, and they conjectured that this result gives the correct order of magnitude. Our main contribution is to prove this conjecture.
Constructing Hamilton cycles and perfect matchings efficiently
Authors: Anastos Michael
Published: June 2023

Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$ edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a Hamiltonian graph with $(1+o(1))n$ edges within as few rounds as possible. We show that in this process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along the first $(0.5+o(1))n\log n$ rounds of the random graph process. This answers a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds is asymptotically optimal as the first $0.5n\log n$ edges do not span a Hamilton cycle w.h.p. The case $K=\Theta(\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+o(1))(1+(\log n)/2K) n$. This matches the $(1-o(1))(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=\Theta(\log n)$. We also show that in the above process one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2) \rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\log n)/2K) n$ rounds w.h.p. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle.
Cycles of every length and orientation in randomly perturbed digraphs
Authors: Araujo Igor , Balogh József , Krueger Robert , Piga Simón , Treglown Andrew
Published: June 2023

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$.
On the sizes of t-intersecting k-chain-free families
Authors: Balogh József , Linz William , Patkos Balazs
Published: June 2023

A set system $\cF$ is $t$-{\it intersecting}, if the size of the intersection of every pair of its elements has size at least $t$. A set system $\cF$ is $k$-{\it Sperner}, if it does not contain a chain of length $k+1$. Our main result is the following: Suppose that $k$ and $t$ are fixed positive integers, where $n+t$ is even and $n$ is large enough. If $\cF\subseteq 2^{[n]}$ is a $t$-intersecting $k$-Sperner family, then $\cF$ has size at most the size of the sum of $k$ layers, of sizes $(n+t)/2,\ldots, (n+t)/2+k-1$. This bound is best possible. The case when $n+t$ is odd remains open.
Independent dominating sets in planar triangulations
Authors: Botler Fábio , Fernandes Cristina , Gutiérrez Juan
Published: June 2023

In 1996, Matheson and Tarjan proved that every planar triangulation on \(n\) vertices contains a dominating set %, i.e., a set \(S\) that contains a neighbor of every vertex not in \(S\), of size at most \(n/3\), and conjectured that this upper bound can be reduced to \(n/4\) when $n$ is sufficiently large. In this paper, we consider the analogous problem for independent dominating sets: What is the minimum \(\eps\) for which every planar triangulation on \(n\) vertices contains an independent dominating set of size at most \(\eps n\)? We prove that \(2/7 \leq \eps \leq 3/8\).
Effective bounds for induced size-Ramsey numbers of cycles
Authors: Bradac Domagoj , Draganic Nemanja , Sudakov Benny
Published: June 2023

The induced size-Ramsey number $\hat{r}_\text{ind}^k(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have such that for any $k$-coloring of its edges, there exists a monochromatic copy of $H$ which is an induced subgraph of $G$. In 1995, in their seminal paper, Haxell, Kohayakawa and {\L}uczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $\hat{r}_\text{ind}^k(C_n)\leq Cn$ for some $C=C(k)$. The constant $C$ comes from the use of the regularity lemma, and has a tower type dependence on $k$. In this paper we significantly improve these bounds, showing that $\hat{r}_\text{ind}^k(C_n)\leq O(k^{102})n$ when $n$ is even, thus obtaining only a polynomial dependence of $C$ on $k$. We also prove $\hat{r}_\text{ind}^k(C_n)\leq e^{O(k\log k)}n$ for odd $n$, which almost matches the lower bound of $e^{\Omega(k)}n$. Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $\hat{r}^k(C_n)=e^{O(k)}n$ for odd $n$. This substantially improves the best previous result of $e^{O(k^2)}n$, and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.
Exact enumeration of graphs and bipartite graphs with degree constraints
Authors: Caizergues Emma , Panafieu Elie
Published: June 2023

We provide a new explicit formula enumerating graphs with constraints on their degrees, such as regular graphs, and extend it to bipartite graphs. It relies on generating function manipulations and Hadamard products.\\ \textbf{Keywords.} regular graphs, exact enumeration, D-finite, differentiably finite
A direct bijection between two-stack sortable permutations and fighting fish
Authors: Cioni Lapo , Ferrari Luca , Henriet Corentin
Published: June 2023

We define a bijection between \emph{two-stack sortable permutations} and \emph{fighting fish}, enriching the garden of bijections linking the numerous combinatorial classes counted by the sequence $A000139$ of the OEIS. Our bijection is (up to symmetry) the non-recursive version of the one of Fang (2018). Along the way, we encounter \emph{labeled sorting trees}, a new class of trees that appear to have nice properties that seem worth to explore.
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P4
Authors: Cook Linda , Masařík Tomáš , Pilipczuk Marcin , Reinald Amadeus , Souza Uéverton
Published: June 2023

An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is \emph{$H$-free} if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega(G)$ has chromatic number at most $f(\omega(G))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The \emph{dichromatic number} of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker, Charbit, and Naserasr's $\dichi$-boundedness conjecture states that for every oriented forest $F$, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega(D))$, where $\omega(D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr's $\dichi$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices.
Dispersion on the Complete Graph
Authors: Ambroggio Umberto , Makai Tamas , Panagiotou Konstantinos
Published: June 2023

We consider a synchronous process of particles moving on the vertices of a graph~$G$, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially,~$M$ particles are placed on one vertex of~$G$. At the beginning of each time step, for every vertex inhabited by at least two particles, each of these particles moves independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than one particle. Cooper et al.~showed that when the underlying graph is the complete graph on~$n$ vertices, then there is a phase transition when the number of particles $M = n/2$. They showed that if $M0$, then the process finishes in a logarithmic number of steps, while if $M>(1+\varepsilon)n/2$, an exponential number of steps are required with high probability. In this paper we provide a thorough analysis of the distribution of the dispersion time in the barely critical regime, where $\varepsilon =o(1)$, and describe the fine details of the transition between logarithmic and exponential time. As a consequence of our results we establish, for example, that the dispersion time is in probability and in expectation $\Theta(n^{1/2})$ when $|\varepsilon| = O(n^{-1/2})$, and provide qualitative bounds for its tail behavior.
The root cluster after percolation on preferential attachment trees
Authors: Desmarais Colin , Holmgren Cecilia , Wagner Stephan
Published: June 2023

The class of linear preferential attachment trees includes recursive trees, plane-oriented recursive trees, binary search trees, and increasing $d$-ary trees. Bond percolation with parameter $p$ is performed by considering every edge in a graph independently, and either keeping the edge with probability $p$ or removing it otherwise. The resulting connected components are called clusters. In this extended abstract, we demonstrate how to use methods from analytic combinatorics to compute limiting distributions, after rescaling, for the size of the cluster containing the root. These results are part of a larger work on broadcasting induced colorings of preferential attachment trees.
Cycles through two edges in signed graphs
Authors: DeVos Matt , Nurse Kathryn
Published: June 2023

We give a characterization of when a signed graph $G$ with a pair of distinguished edges $e_1, e_2 \in E(G)$ has the property that all cycles containing both $e_1$ and $e_2$ have the same sign. This answers a question of Zaslavsky.
Powers of planar graphs, product structure, and blocking partitions
Authors: Distel Marc , Hickingbotham Robert , Seweryn Michał , Wood David
Published: June 2023

We show that there exist a constant \(c\) and a function \(f\) such that the \(k\)-power of a planar graph with maximum degree \(\Delta\) is isomorphic to a subgraph of \(H \boxtimes P \boxtimes K_{f(\Delta, k)}\) for some graph \(H\) with treewidth at most \(c\) and some path \(P\). This is the first product structure theorem for \(k\)-powers of planar graphs, where the treewidth of \(H\) does not depend on \(k\). We actually prove a stronger result, which implies an analogous product structure theorem for other graph classes, including \(k\)-planar graphs (of arbitrary degree). Our proof uses a new concept of blocking partitions which is of independent interest. An \(\ell\)-blocking partition of a graph \(G\) is a partition of the vertex set of \(G\) into connected subsets such that every path in \(G\) of length greater than \(\ell\) contains two vertices in one set of the partition. The key lemma in our proof states that there exists a positive integer \(\ell\) such that every planar graph of maximum degree \(\Delta\) has an \(\ell\)-blocking partition with parts of size bounded in terms of \(\Delta\).
Chvátal-Erdős condition for pancyclicity
Authors: Draganić Nemanja , Correia David , Sudakov Benny
Published: June 2023

An $n$-vertex graph is \emph{Hamiltonian} if it contains a cycle that covers all of its vertices and it is \emph{pancyclic} if it contains cycles of all lengths from $3$ up to $n$. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph $G$ with $\kappa(G) > (1+o(1)) \alpha(G)$ is pancyclic. This extends the famous Chv\'atal-Erd\H{o}s condition for Hamiltonicity and proves asymptotically a $30$-year old conjecture of Jackson and Ordaz.
Precoloring extension in planar near-Eulerian-triangulations
Authors: Dvořák Zdeněk , Moore Benjamin , Seifrtová Michaela , Šámal Robert
Published: June 2023

We consider the 4-precoloring extension problem in \emph{planar near-Eulerian- triangulations}, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors.
Tangled Paths: A Random Graph Model from Mallows Permutations
Authors: Enright Jessica , Meeks Kitty , Pettersson William , Sylvester John
Published: June 2023

We introduce the random graph $\mathcal{P}(n,q)$ which results from taking the union of two paths of length $n\geq 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0 <q(n)\leq 1$. This random graph model, the tangled path, goes through an evolution: if $q$ is close to $0$ the graph bears resemblance to a path, and as $q$ tends to $1$ it becomes an expander. In an effort to understand the evolution of $\mathcal{P}(n,q)$ we determine the treewidth and cutwidth of $\mathcal{P}(n,q)$ up to log factors for all $q$. We also show that the property of having a separator of size one has a sharp threshold. In addition, we prove bounds on the diameter, and vertex isoperimetric number for specific values of $q$.\blfootnote{Supported by EPSRC project EP/T004878/1: Multilayer Algorithmics to Leverage Graph Structure.}
Sharp threshold for embedding balanced spanning trees in random geometric graphs
Authors: Díaz Alberto , Lichev Lyuben , Mitsche Dieter , Wesolek Alexandra
Published: June 2023

Consider the random geometric graph $\mathcal{G}(n,r)$ obtained by independently assigning a uniformly random position in $[0,1]^2$ to each of the $n$ vertices of the graph and connecting two vertices by an edge whenever their Euclidean distance is at most $r$. We study the event that $\mathcal{G}(n,r)$ contains a spanning copy of a balanced tree $T$ and obtain sharp thresholds for these events. Our methods provide a polynomial-time algorithm for finding a copy of such trees $T$ above the threshold.
On the structure and values of betweenness centrality in dense betweenness-uniform graphs
Authors: Ghanbari Babak , Hartman David , Jelínek Vít , Pokorná Aneta , Šámal Robert , Valtr Pavel
Published: June 2023

Betweenness centrality is a network centrality measure based on the amount of shortest paths passing through a given vertex. A graph is betweenness-uniform (BUG) if all vertices have an equal value of betweenness centrality. In this contribution, we focus on betweenness-uniform graphs with betweenness centrality below one. We disprove a conjecture about the existence of a BUG with betweenness value $\alpha$ for any rational number $\alpha$ from the interval $(\sfrac{3}{4}, \infty)$ by showing that only very few betweenness centrality values below $\sfrac{6}{7}$ are attained for at least one BUG. Furthermore, among graphs with diameter at least three, there are no betweenness-uniform graphs with a betweenness centrality smaller than one. In graphs of smaller diameter, the same can be shown under a uniformity condition on the components of the complement.
Hamilton cycles in pseudorandom graphs
Authors: Glock Stefan , Correia David , Sudakov Benny
Published: June 2023

Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any $d$-regular $n$-vertex graph $G$ whose second largest eigenvalue in absolute value $\lambda(G)$ is at most $d/C$, for some universal constant $C>0$, has a Hamilton cycle. We obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree $d$ is at least a small power of $n$. Secondly, in the general case we show that $\lambda(G) \leq d/ C(\log n)^{1/3}$ implies the existence of a Hamilton cycle, improving the 20-year old bound of $d/ \log^{1-o(1)} n$ of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust P\'osa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications, giving best bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lov\'asz. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups.
Refined list version of Hadwiger’s Conjecture
Authors: Gu Yangyan , Jiang Yiting , Wood David , Zhu Xuding
Published: June 2023

Assume $\lambda=\{k_1,k_2, \ldots, k_q\}$ is a partition of $k_{\lambda} = \sum_{i=1}^q k_i$. A $\lambda$-list assignment of $G$ is a $k_\lambda$-list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into $|\lambda|= q$ sets $C_1,C_2,\ldots,C_q$ such that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. We say $G$ is \emph{$\lambda$-choosable} if $G$ is $L$-colourable for any $\lambda$-list assignment $L$ of $G$. The concept of $\lambda$-choosability is a refinement of choosability that puts $k$-choosability and $k$-colourability in the same framework. If $|\lambda|$ is close to $k_\lambda$, then $\lambda$-choosability is close to $k_\lambda$-colourability; if $|\lambda|$ is close to $1$, then $\lambda$-choosability is close to $k_\lambda$-choosability. This paper studies Hadwiger's Conjecture in the context of $\lambda$-choosability. Hadwiger's Conjecture is equivalent to saying that every $K_t$-minor-free graph is $\{1 \star (t-1)\}$-choosable for any positive integer $t$. We prove that for $t \ge 5$, for any partition $\lambda$ of $t-1$ other than $\{1 \star (t-1)\}$, there is a $K_t$-minor-free graph $G$ that is not $\lambda$-choosable. We then construct several types of $K_t$-minor-free graphs that are not $\lambda$-choosable, where $k_\lambda - (t-1)$ gets larger as $k_\lambda-|\lambda|$ gets larger.
Colouring complete multipartite and Kneser-type digraphs
Authors: Harutyunyan Ararat , i Gil
Published: June 2023

The dichromatic number of a digraph $D$ is the smallest $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs, and the dichromatic number of an undirected graph is the maximum dichromatic number over all its orientations. We present bounds for the dichromatic number of Kneser graphs and Borsuk graphs, and for the list dichromatic number of certain classes of Kneser graphs and complete multipartite graphs. The bounds presented are sharp up to a constant factor. Additionally, we give a directed analogue of Sabidussi's theorem on the chromatic number of graph products.
The hitting time of clique factors
Authors: Heckel Annika , Kaufmann Marc , Müller Noela , Pasch Matija
Published: June 2023

In \cite{kahn2022hitting}, Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let $r \ge 3 $ and let $n$ be divisible by $r$. Then, in the random $r$-uniform hypergraph process on $n$ vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: At the time that the last vertex joins a copy of the complete graph $K_r$, the random graph process contains a $K_r$-factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the $s$-uniform hypergraph process ($s \ge 3$).
Fractionally Isomorphic Graphs and Graphons
Authors: Hladký Jan , Hng Eng
Published: June 2023

Fractional isomorphism is a well-studied relaxation of graph isomorphism with a very rich theory. Grebík and Rocha [Combinatorica 42, pp 365--404 (2022)] developed a concept of fractional isomorphism for graphons and proved that it enjoys an analogous theory. In particular, they proved that if $G_1,G_2,\ldots$ converge to a graphon $U$, $H_1,H_2,\ldots$ converge to a graphon $W$ and each $G_i$ is fractionally isomorphic to $H_i$, then $U$ is fractionally isomorphic to $W$. Answering the main question from \emph{ibid}, we prove the converse of the statement above: If $U$ and $W$ are fractionally isomorphic graphons, then there exist sequences of graphs $G_1,G_2,\ldots$ and $H_1,H_2,\ldots$ which converge to $U$ and $W$ respectively and for which each $G_i$ is fractionally isomorphic to $H_i$. As an easy but convenient corollary of our methods, we get that every regular graphon can be approximated by regular graphs.
Cops and Robber on Hyperbolic Manifolds
Authors: Iršič Vesna , Mohar Bojan , Wesolek Alexandra
Published: June 2023

The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pursuit-evasion games. One of the outstanding open problems about the game on graphs is to determine which graphs embeddable in a surface of genus $g$ have largest cop number. It is known that the cop number of genus $g$ graphs is $O(g)$ and that there are examples whose cop number is $\tilde\Omega(\sqrt{g}\,)$. The same phenomenon occurs when the game is played on geodesic surfaces. In this paper we obtain a surprising result when the game is played on a surface with constant curvature. It is shown that two cops have a strategy to come arbitrarily close to the robber, independently of the genus. For special hyperbolic surfaces we also give upper bounds on the number of cops needed to catch the robber. Our results generalize to higher-dimensional hyperbolic manifolds.
How connectivity affects the extremal number of trees
Authors: Jiang Suyun , Liu Hong , Salia Nika
Published: June 2023

The Erd\H{o}s-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree $T$, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$.
Avoiding intersections of given size in finite affine spaces AG(n,2)
Authors: Kovács Benedek , Nagy Zoltán
Published: June 2023

We study the set of intersection sizes of a $k$-dimensional affine subspace and a point set of size $m \in [0, 2^n]$ of the $n$ dimensional binary affine space $\mathrm{AG}(n,2)$.
Cycle Partition of Dense Regular Digraphs and Oriented Graphs
Authors: Lo Allan , Patel Viresh , Yildiz Mehmet
Published: June 2023

Magnant and Martin~\cite{PathCover} conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter~\cite{GruslysLetzter} verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all $\alpha>0$, there exists $n_0=n_0(\alpha)$ such that every $d$-regular digraph on $n$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles. Moreover if $G$ is an oriented graph, then $n/(2d+1)$ cycles suffice. This also establishes Jackson's long standing conjecture~\cite{JacksonConjecture} for large $n$ that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian.
Kneser graphs are Hamiltonian
Authors: Merino Arturo , Namrata  , Namrata
Published: June 2023

For integers~$k\geq 1$ and $n\geq 2k+1$, the Kneser graph~$K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph~$K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph~$J(n,k,s)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two sets whose intersection has size exactly~$s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lov\'asz' conjecture on Hamilton cycles in vertex-transitive graphs from~1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway's Game of Life, and to analyze this system combinatorially and via linear algebra.
Product-free sets in the free group
Authors: Ortega Miquel , Rué Juanjo , Serra Oriol
Published: June 2023

We prove that product-free sets of the free group over a finite alphabet have maximum density $1/2$ with respect to the natural measure that assigns total weight one to each set of irreducible words of a given length. This confirms a conjecture of Leader, Letzter, Narayanan and Walters. In more general terms, we actually prove that strongly $k$-product-free sets have maximum density $1/k$ in terms of the said measure. The bounds are tight.
The Rado Multiplicity Problem in Vector Spaces over Finite Fields
Authors: Rué Juanjo , Spiegel Christoph
Published: June 2023

We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in $2$-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al.~\cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf~\cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov~\cite{razborov2007flag}.
On universal singular exponents in equations with one catalytic parameter of order one
Authors: Schaeffer Gilles
Published: June 2023

{\tmem{Equations with one catalytic variable and one univariate unkown}}, also known as {\tmem{discrete difference equations of order one}}, form a familly of combinatorially relevant functional equations first discussed in full generality by Bousquet-M{\'e}lou and Jehanne (2006) who proved that their power serie solutions are algebraic. Drmota, Noy and Yu (2022) recently showed that in the non linear case the singular expansions of these series have a universal dominant term of order 3/2, as opposed to the dominant square root term of generic $\mathbb{N}$-algebraic series. Their direct analysis of the cancellation underlying this behavior is a tour de force of singular analysis. We show that the result can instead be given a straightforward explanation by showing that the derivative of the solution series conforms to the standard square root singular behavior. Consequences also include an atypical, but generic in this situation, $n^{^{5 / 4}}$ asymptotic behavior for the cumulated values of the underlying catalytic parameter.
Investigating Effects of Co-creation on Outcomes of Public Service Innovation – A Comparative Analysis at the National and Local Government Level in Norway
Authors: Gesierich Stefanie
Published: June 2023

Co-creation in public service innovation is a prominent research field, but few have empirically investigated its effect on the outcomes of innovation. This paper contributes with empirical-based knowledge on the effect of participatory user involvement and other user-oriented methods on public innovation outcomes in different contexts. By employing qualitative comparative analysis (QCA) based on a survey of innovation activities of Norwegian public administration agencies, this article identifies several configurations for local and national authorities that lead to successful service innovations. The main finding suggests a positive relationship between user input and positive effects on service outcomes. However, local and national government levels differ regarding the use of input factors and methods of user involvement. The study contributes to our understanding of the effect of co-creation in different contexts and provides insights into when and how co-creation with users is a useful tool in public service innovation.
A Broken Process – The Swedish Health Care System Asks for Expert Advice
Authors: Svallfors Stefan , Falkenström Erica , Höglund Anna T.
Published: June 2023

This paper analyses the process in which expert reports on health care governance are commissioned, produced and received in a Swedish setting. Based on an empirical analysis of interviews with commissioners and producers of such reports, the paper argues that the typical process in which expert reports on health governance come about is fraught with quite deficient ways of producing expert knowledge. The analysis contributes to the literature on the role of expertise in governance and policymaking. In contrast to most other analyses in this field, the paper focuses not on the content of expert reports nor on their political uptake but on the process in which they are produced.
Why Do Associations Run Independent Schools in Sweden, and Why Does It Matter?
Authors: Hallonsten Olof , Sevelin Ellika
Published: June 2023

The Swedish school system was radically reformed in the 1990s, and went from one of the world’s most uniform and egalitarian, to one of the world’s most deregulated and marketized. In recent years, the political controversy has heated over the for-profit corporations that operate independent schools and allegedly make major profits off the public purse. A majority of independent schools in Sweden are operated by limited liability companies, but hundreds of schools are also operated by non-profit foundations and associations. The latter category are of interest in this article. With the help of a thorough legal historical analysis of the corporate law on associations in Sweden, and how the two forms of associations – economic associations and non-profit associations – are defined in the law, we discuss how well the law matches the purposes and needs of elementary schools in Sweden. The article concludes that the ambiguities and confusion around the law on economic associations in this specific case, and the essential lack of legislation for nonprofit associations, warrants a fundamental questioning of whether it is at all appropriate for independent schools in Sweden to be operated by economic and nonprofit associations.
Remembering George Lamming (1927–2022), with Thoughts on In the Castle of My Skin
Authors: Gordon Lewis R. ,   Philosophy Documentation Center
Published: June 2023

The first part of this memoriam essay focuses on the author’s relationship with the famed Bajan intellectual George Lamming during his years at Brown University. The second part explores Lamming’s most famous work, In the Castle of My Skin (1953), which offers important tropes in Black existential thought that are synchronous with Frantz Fanon’s Peau noir, masques blancs (1952), but with a more detailed exploration of the concept of political complicity through Lamming’s portrait of the phenomenon of slime and its correlate, the slimy individual. The author also discusses Lamming’s treatment of the Fanonian motif of colonizing notions of normative development.
Ijtihad Imam Asy-Syafi'i (Analsis Kritis terhadap Qaul Qadim dan Qaul Jadid)
Authors: Ubaidillah Ubaidillah
Published: June 2023

Abstract Ijtihad is the gateway to Islamic progress. The rise and fall of Islam is closely linked to the ebb and flow of ijtihad activities. Because the activities of ijtihad make sense in digging into the pearls of knowledge stored in the Qur'an and al-Hadith. The Asi-Shaykh priest was one of the initiators of the sect to establish his own method of legal practice in issuing his fatwa. Some of its Islamic activities are in two different places, Iraq and Egypt. The fatwas that he produced during his reign in Iraq were known as the qaul qadim, while the fatwas he produced in Egypt were known as the qaul qadim. In this study the researchers used a bibliographie research approach and their data collection procedure using editing, coding and tabulating. So the result is that finding qaul qadim can be demonstrated in the case of the ability of a guardian to replace the fasting left by the deceased due to the inclusion of shaheh hadith. Whereas in other cases qaul jadid is featured because it reinforces the quality of the arguments.
Penerapan Proses Rehabilitasi pada Penyalahguna Narkotika sebagai Upaya Pemulihan
Authors: Nugroho Bastianto , Rahayu Siti , Roesli M. , Yeremia Reinhard
Published: June 2023

Abstract Narcotics are substances or drugs that are very useful and necessary for the treatment of certain diseases. However, if it is misused or used not in accordance with the standard of treatment it can have very detrimental consequences for individuals or society, especially the younger generation. This will be more detrimental if accompanied by the abuse and illicit trafficking of narcotics which can result in a greater danger to the life and cultural values of the nation which in turn can weaken national resilience. In its development, Law No. 22/1997 on Narcotics is deemed unable to answer the many aspects of the narcotics problem. One of them is recognizing the negative impact on public health who are in the position of perpetrators, users, and victims of narcotics abuse. In response to this, the Government then established Law Number 35 of 2009 concerning Narcotics. The law aims to find a balance point between the public health approach and the implementation of criminal instruments in overcoming narcotics crime. This research is a normative juridical research, namely research that describes in detail the social phenomena that are the main problems in everyday life associated with the applicable positive criminal law regulations. A normative legal research is intended to provide data as accurate as possible on the crime of narcotics abuse.
Los alcances de las tecnologías de la información y comunicación
Authors: Ariza Verónica , Valenzuela Erika
Published: June 2023

A inicios de esta década, las tecnologías de la información se han adaptado a distintas áreas como la educación, los negocios y la comunicación, desarrollado e incorporado nuevas herramientas que permiten una participación más activa en la construcción y transmisión del conocimiento. Se han generado servicios y herramientas que han transformado la red en una plataforma dialógica social, los negocios a una adaptación dentro de un espacio virtual, y la educación en un nuevo concepto conocido como educación a distancia.
Un acercamiento de la Antropología Social al Diseño
Authors: De La Barrera Medina Mónica Susana
Published: June 2023

A modo de reflexión personal, la vinculación del diseño con la antropología social, su incidencia y algunas de las posibilidades para su estudio.