Ces derniers mois, j'ai commencé à m'exprimer sur le choix social, le théorème de la flèche et les résultats associés. Après avoir lu les résultats séminaux, je me suis demandé ce qui se passe avec les préférences d'ordre partiel, la réponse est dans l'article de Pini et al. : Agrégation de...
Le temps de trajet dans un graphique connecté est défini comme le nombre attendu d'étapes dans une marche aléatoire commençant à , avant que le nœud soit visité et que le nœud soit à nouveau atteint. Il s'agit essentiellement de la somme des deux temps de frappe et
J'ai déjà posté cette question il y a un certain temps sur MathOverflow , mais à ma connaissance, elle est toujours ouverte, donc je la republie ici dans l'espoir que quelqu'un en ait entendu parler. Énoncé du problème Soit , Q et R trois partitions en p parties non vides (désignées par P h , Q i...
Cette question est inspirée de la conjecture polynomiale de Hirsch (PHC). Étant donné un polytope à facettes P dans R d , l'écart spectral de son graphe bord-sommet (appelons-le G ) est-il limité par Ω ( 1 / p o l y ( n ) ) ? Notez que le graphique du cycle sur n sommets montre que, même pour d = 2...
En raisonnant un peu sur cette question , j'ai essayé d'identifier toutes les différentes raisons pour lesquelles un graphe peut ne pas être k colorable. Ce sont les 2 seules raisons que j'ai pu identifier jusqu'à présent:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk contient une clique de taille k + 1 ....
1- Existe-t-il des propriétés spécifiques pour la matrice d'adjacence lorsqu'un graphe est plan? 2- Y a-t-il quelque chose de spécial pour calculer la matrice permanente d'adjacence lorsqu'un graphe est
Shor a déclaré, dans son commentaire à la réponse d'un orignal anonyme à cette question Pouvez-vous identifier la somme de deux permutations en temps polynomial? , qu'il est complet d'identifier la différence de deux permutations. Malheureusement, je ne vois pas de réduction directe du problème de...
J'ai rencontré le résultat suivant lors de mes recherches. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 oùetsont choisis au hasard parmi.a1,⋯,am[n]m=ω(n−−√)m=ω(n)m=\omega(\sqrt...
Considérons l'ensemble des graphes planaires où toutes les faces internes sont des triangles. S'il y a un point intérieur de degré impair, le graphique ne peut pas être tricolore. Si chaque point intérieur a un degré égal, peut-il toujours être tricolore? Idéalement, je voudrais un petit...
Je viens de lire sur Wikipedia allemand qu'un graphe infini est un graphe avec un nombre infini de nœuds ou un nombre infini d'arêtes. Je ne connais que les applications et les algorithmes pour les graphes finis. À quoi servent les graphiques infinis? Quelles sont leurs applications? Je ne peux pas...
Est - il possible de construire un explicite 0 / 1 matrix avec N 1,5 ceux de telle sorte que tous les N 0,499 × N 0,499 sous - matrice contient moins de N 0,501 celles?N× NN×NN \times N 0 / 10/10/1N1,5N1.5N^{1.5}N0,499× N0,499N0.499×N0.499N^{0.499} \times N^{0.499}N0,501N0.501N^{0.501} Ou il est...
Je voudrais donner une conférence mathématique sur le système de contrôle de révision git . Il est maintenant largement utilisé en mathématiques ainsi que dans l'industrie informatique. Par exemple, la communauté HoTT (Homotopy Type Theory) l'utilise, et c'est le système de référence pour l'édition...
Soit un simple graphe sur sommets sans sommet de degré . Supposons que pour deux sommets de , il existe un sommet unique adjacent à chacun d'eux. Il s'agit d'un exercice de A Course in Combinatorics , van Lint et Wilson, pour prouver qu'un tel graphique est régulier.ggGnnn( n > 3 )(n>3)(n >...
Je m'intéresse aux modèles de graphes aléatoires similaires aux graphes de vrais réseaux informatiques. Je ne sais pas si le modèle commun bien étudié ( n sommets, chaque bord possible est sélectionné avec la probabilité p ) est bon pour étudier les réseaux informatiques réels...
Une propriété de base des espaces vectoriels est qu'un espace vectoriel V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n de dimension n−dn−dn-d peut être caractérisé par ddd contraintes linéaires linéairement indépendantes - c'est-à-dire qu'il existe ddd vecteurs linéairement indépendants...
La question est simple et directe: pour un fixe nnn, combien de langues (différentes) sont acceptées par un DFA de taille nnn (c'est-à-dire nnn états)? Je vais déclarer officiellement ceci: Définissez un DFA comme ( Q , Σ , δ, q0, F)(Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) , où tout est comme d'habitude...
Supposons que nous ayons un graphique pondéré non orienté (avec des poids non négatifs). Supposons que tous les chemins les plus courts dans G soient uniques. Supposons que nous ayons ces chemins (séquences d'arêtes non pondérées), mais ne connaissons pas lui-même. Pouvons-nous produire un qui...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Comment puis-je déterminer le nombre de chemins simples uniques dans un graphique non orienté? Soit pour une certaine longueur, soit pour une plage de longueurs acceptables. Rappelez-vous qu'un chemin simple est un chemin sans cycle, je parle donc de compter le nombre de chemins sans...
Soit une formule CNF satisfaisante avec n variables et m clauses. Soit S F 1 l'espace de solution de F 1 .F1F1F_1nnnmmmSF1SF1S_{F_1}F1F1F_1 Considérons le problème de déterminer, étant donné , une autre formule CNF F 2 avec le même ensemble de variables que F 1 , avec S F 2 = S F 1 (même espace de...